# Number of bit strings

How many bit string of lenght 28

• having at least one consecutive 000?
• without consecutive 000?

I'm using ti nspire, can i do it with nCr function.

I tried to do it but i did not found a way.

thank you.

but it did not help me.

Let $a_n$ be a bit string of length n without 000, then it can be

$a_{(n-3)}$ with 100 added at end,

or $a_{(n-2)}$ with 10 added at end,

or $a_{(n-1)}$ with 1 added at end.

So $a_n = a_{(n-1)} +a_{(n-2)} + a_{(n-3)}$

starting with $a_0 = 1, a_1=2, a_2 = 4$

The ending of any successful chain can be categorised as 1(111,101,011,001) 10(110,010) or 100.

1 can be added to any successful chain of length (n-1) no matter what it ended with.

10 can be added to any successful chain of length (n-2) no matter what it ended with.

100 can be added to any successful chain of length (n-3) no matter what it ended with.

• i'm beginning with discrete mathematics, could you give me a little bit more advice on what you wrote. Thank – Pierre-Luc Bolduc Jul 13 '15 at 4:03
• Further explanation added. – true blue anil Jul 13 '15 at 6:28
• thank you, i did a recurence and i found 29 249 425 without consecutive 000 and to have at least one consecutive 000 i have to do 2^28 - 29 249 425. Does it seams to be good? – Pierre-Luc Bolduc Jul 13 '15 at 19:57
• You're welcome ! Look up Tribonacci numbers on OEIS to check your figures. – true blue anil Jul 14 '15 at 4:07
• Thank :) and could you explain me how did you find a0 =1 a1=1 a2=4 – Pierre-Luc Bolduc Jul 14 '15 at 15:22