1
$\begingroup$

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.

i saw this post : Number of binary strings of length 8 that contain either three consecutive 0s or four consecutive 1s

and this one : http://www.techtud.com/doubt/combinatorics-how-many-bit-string-length-eight-contai

but it did not help me.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ i'm beginning with discrete mathematics, could you give me a little bit more advice on what you wrote. Thank $\endgroup$ – Pierre-Luc Bolduc Jul 13 '15 at 4:03
  • $\begingroup$ Further explanation added. $\endgroup$ – true blue anil Jul 13 '15 at 6:28
  • $\begingroup$ 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? $\endgroup$ – Pierre-Luc Bolduc Jul 13 '15 at 19:57
  • $\begingroup$ You're welcome ! Look up Tribonacci numbers on OEIS to check your figures. $\endgroup$ – true blue anil Jul 14 '15 at 4:07
  • $\begingroup$ Thank :) and could you explain me how did you find a0 =1 a1=1 a2=4 $\endgroup$ – Pierre-Luc Bolduc Jul 14 '15 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.