In A Diversion PragDave poses the following kata:
Think of binary numbers: sequences of 0’s and 1’s. How many n-digit binary numbers are there that don’t have two adjacent 1 bits? For example, for three-digit numbers, five of the possible eight combinations meet the criteria: 000, 001, 010, 011, 100, 101, 110, 111. What is the number for sequences of length 4, 5, 10, n?
Having given the answer for 3-digit binary numbers, he also asks why this relationship exists. Well, I think I can answer that. It is simple combinatorics. Since typesetting math in HTML is such a pain, I will just post the LaTeX note I wrote to explain the relationship to myself:
\documentclass{article}
\title{Re: A Diversion}
\author{Sune Kirkeby}
\date{30. November 2003}
\begin{document}
\newcommand{\bicoef}[2]{ \left(\begin{array}{c} #1\\#2 \end{array}\right)}
\maketitle
Let $a$ be the number of $n$-digit binary numbers with exactly $k$ $1$ bits, where no two $1$-bits are adjacant. Then
$$a = \bicoef{n-k+1}{k} $$
Let $b$ be the number of $n$-digit binary numbers that do not have two adjacant $1$ bits. Then
$$b = \sum_{k=0}^n \bicoef{n-k+1}{k}$$
For $n=3$:
$$\bicoef{3-0+1}{0} + \bicoef{3-1+1}{1} + \bicoef{3-2+1}{2} + \bicoef{3-3+1}{3}
= 1 + 3 + 1 + 0 = 5$$
\end{document}