Sequences of 0 and 1

[Guest]

How many sequences of length n compiled of 0s and 1s exist so that there is 2+ 0s between every 1
For example:
00000000
10010010
10000001
I need general formula for n or general way of solving this with explanation

[Guest]

The easiest way to solve this is probably by using recurrence relations.

Let [tex]x_n[/tex] be the number of sequences of length [tex]n[/tex]. Let us consider the left most digit in an [tex]n[/tex] digit valid sequence.

If the left most digit is [tex]0[/tex], the remaining [tex]n-1[/tex] digits can be any valid sequence of [tex]n-1[/tex] digits.
So there are [tex]x_{n-1}[/tex] sequences which begin with [tex]0[/tex].

If the left most digit is [tex]1[/tex], then the three left most digits must be [tex]100[/tex] (otherwise it is not valid). The remaining [tex]n-3[/tex] digits can be any valid sequence.
So there are [tex]x_{n-3}[/tex] sequences which begin with [tex]1[/tex].

This means [tex]x_n = x_{n-1}+x_{n-3}[/tex], by considering the first few cases manually, we can easily determine that [tex]x_1=2, x_2=3, x_3=4[/tex], which gives us enough information to calculate [tex]x_n[/tex] for [tex]n\geq 1[/tex]. For example:
[tex]x_4 = x_3+x_1 = 4+2= 6[/tex],
[tex]x_5 = x_4+x_2 = 6+3= 9[/tex],
[tex]x_6 = x_5+x_3 = 9+4= 13[/tex]

You can create an exact closed form solution for the recurrence relation. It is not difficult to do, but the formula that drops out in this particular case is very ugly and involves complex numbers and cube roots. To see it in all its hideous glory go to
http://www.cs.unipr.it/cgi-bin/purrs_rr ... -3%29&i_c=
If we explicitly evaluate the expressions to 12 significant figures, we can get an approximate version of the formula:
[tex]x_n = 1.31342305985 \times
1.46557123188^n+[/tex]
[tex](-0.156711529924 - 0.00134033362014 i) \times
(-0.232785615938 + 0.792551992515 i)^n+[/tex]
[tex](-0.156711529924 + 0.00134033362014 i) \times
(-0.232785615938 - 0.792551992515 i)^n[/tex]
which is a bit nicer.

Hope this helped,

R. Baber.

[Guest]

In fact the dominant term in the approximate solution is [tex]1.31342305985\times 1.46557123188^n[/tex], so we can come up with an exact solution which looks like:
[tex]x_n = \left[\left(\frac{a^2+a+1}{3a^2-2a}\right)a^n\right][/tex]
where
[tex]a = \frac{1}{6}\left(2+\sqrt[3]{116+12\sqrt{93}}+\sqrt[3]{116-12\sqrt{93}}\right)[/tex]
and the square bracket operator means "the nearest integer to the value inside the parenthesis" (e.g. [tex][3.6]=4[/tex], [tex][3.1]=3[/tex]). (The value inside the square brackets will never be exactly halfway between two integers in our case, so we don't need to worry about this case.)

See
https://en.wikipedia.org/wiki/Fibonacci ... y_rounding
for an example of the Fibonacci sequence written in this form.

Hope this helped,

R. Baber.

[Guest]

Thank you