A Solution to Kata Fifteen
Friday, 22 August 2003
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?
Flexing the "proofs" part of my brain for the first time in long while, I think I've got both the solution and a proof for this. I've developed this solution independently, so there are probably more elegant proofs available.
Spoiler Warning: If you'd like to work this Kata yourself, beware, spoilers follow. I'll leave some blank space first.
Definitions and Notation
First, let's define some terms.
By inspection, it's easy to work out the first few values of f(n). Note that when n=0, we can count the empty sequence.
To make the proof a little bit easier, I'll introduce some additional notation.
Let concat(a,b) be a
function that maps a pair of sequences to a new sequence by prefixing the first to the second. For example,
Let CONCAT(a,B) be
function that maps a sequence and a set of sequences to a new set of sequences obtained by prefixing the sequence
a to each sequence in the set B. In other words,
If you're familiar with it, it is easy to recognize f(n) to be the Fibonacci Sequence, at least for small values of n. So here it is in theorem form: If f(n) is the number of binary sequences of length n that do not contain two consecutive 1 bits, then:
f(0) = 1 f(1) = 2 f(n) = f(n-1) + f(n-2) for all n > 1
Note that the set
Sn = CONCAT(0,Sn-1) union CONCAT(1,Sn-1)
CONCAT(1,Sn-1) = CONCAT(11,Sn-2) union CONCAT(10,Sn-2)
Sn = CONCAT(0,Sn-1) union CONCAT(11,Sn-2) union CONCAT(10,Sn-2)
For convenience, let's name each of those three sets:
Let A = CONCAT(0,Sn-1) Let B = CONCAT(11,Sn-2) Let C = CONCAT(10,Sn-2) Sn = A union B union C
Since the sets A, B and C represent a proper partitioning of
How many sequences in A are in
How many sequences in B are in
How many sequences in C are in
Fn = CONCAT(0,Fn-1) union CONCAT(10,Fn-2)
f(n) = |Fn| = |CONCAT(0,Fn-1)| + |CONCAT(10,Fn-2)| = f(n-1) + f(n-2)
For some reason, I had initially thought I'd be clever and reverse the problem. Why count the number of sequences that don't meet some condition, but instead count those that do? This yields the sequence 0, 0, 1, 3, 8, 19, .... Other that starting with the Fibonacci-like 0, 0, it didn't seem recognizable at all to me. (More generally, this sequence is