How many 12digit binary sequences exist with no two ones(11) neighboring each other?.
How many 12digit binary sequences exist with no 3 ones(111) neighboring each other?.
Leading zeros allowed.
Building up to a 12digit sequence it becomes clear the the first case is Fibonnacci.
1digit has 2 ways: 0, 1
2digits has 3 ways: 00, 01, 10
3 digits has 5 ways: put a 0 at the end of the 2digit ways and a 01 at the end of the 1digits ways. 3+2=5
ndigits has the sum of the n1 and n2digit ways: put a 0 at the end of the n1 digit ways and a 01 at the end of the n2 digit ways.
The sequence (starting with n=0) goes 1,2,3,5,8,13,21,34,55,89,144,233,337
The second case is similar.
This time the n term is the sum of the n1 (append 0) the n2 (append 01) and the n3 (append 011) terms.
The sequence goes 1,2,4,7,13,24,44,81,149,274,504,927,1705
If we want to exclude 1111 the sequence is 1,2,4,8,15,29,56,108,208,401,777,1490,2872

Posted by Jer
on 20100423 13:31:07 