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