How many 12-digit binary sequences exist with no two ones(11) neighboring each other?.
How many 12-digit binary sequences exist with no 3 ones(111) neighboring each other?.
Leading zeros allowed.
Building up to a 12-digit sequence it becomes clear the the first case is Fibonnacci.
1-digit has 2 ways: 0, 1
2-digits has 3 ways: 00, 01, 10
3 digits has 5 ways: put a 0 at the end of the 2-digit ways and a 01 at the end of the 1-digits ways. 3+2=5
n-digits has the sum of the n-1 and n-2-digit ways: put a 0 at the end of the n-1 digit ways and a 01 at the end of the n-2 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 n-1 (append 0) the n-2 (append 01) and the n-3 (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 2010-04-23 13:31:07