Earlier today I saw a question about binary sequences of length $n$ that contain no $3$ consecutive $1$s or $0$s. I want to generalize the problem a little and count the number of sequences that contain no $k$ consecutive $1$s or $0$s. First I made some observations:
- Because of symmetry, exactly half of the sequences end with $0$ and the other half with $1$
- If the sequence of length $n$ ends with $k-1$ consecutive $1$s then these consecutive $1$s must be preceded by a sequence of length $n-k+1$ that ends with $0$
- If the sequence of length $n$ ends with $1$ then this last digit must be preceded by a sequence of length $n-1$ that does not end with $k-1$ consecutive $1$s
Based on these observations and by defining $f_{n}$ as the number of binary sequences of length $n$ that contain no $k$ consecutive $1$s or $0$s we get the following recurrence relation:
$$
f_{n}=2f_{n-1}-f_{n-k}
$$
I want to know if the relation I got is correct and I am also interested if there's other way to count the number of sequences.
Best Answer
Well , generally the best method for finding recurrence relation is Goulden-Jackson -Cluster Method. It is very powerful tool to find any recurrence relations. (I want to especially thank to @Markus Scheuer for this beautiful method)
I am putting a link for you : https://arxiv.org/abs/math/9806036 ,you can learn more about it.
Now , i will get in the solution to show you another method.
According to the article , our bad words are $000,111$.
Then , our alphabet is $V= \{0,1\}$
$$A(x)= \frac{1}{1-dx-weight(C)}$$ with $d=|V|=2$ and $weight(C) = weight(C[000])+ weight(C[111])$
Then , we said that $weight(C) = weight(C[000])+ weight(C[111])$ .Hence , $$weight(C) = \frac{-2x^3}{1+x+x^2} $$
Then , $$A(x) = \frac{1}{1-2x -\frac{-2x^3}{1+x+x^2}} = \frac{1+x+x^2}{1-x-x^2}$$
Now , we will turn this fraction into recurrence relation. See for instance theorem 4.1.1 in Enumerative Combinatorics, Vol. I by R. P. Stanley. (https://www.maa.org/press/maa-reviews/enumerative-combinatorics-vol-i)
According to the book , $$\frac{1+x+x^2}{1-x-x^2}= a_n= a_{n-1} + a_{n-2}$$
Moreover , $$\frac{1+x+x^2}{1-x-x^2}=1+2x+4x^2 +6x^3 + \color{blue}{10x^4} + 16x^5+...$$
This sequence says that there are $10$ binary strings of lenght $4$ that do not contain $3$ zeros or $3$ ones.
You can see the sequence by exapnding wolfram-alpha such that https://www.wolframalpha.com/input/?i=expanded+form+of+%281%2Bx%2Bx%5E2%29%2F%281-x-x%5E2%29
When we come to neither $k$ zeros nor $k$ ones. The system turned out to be
$$A(x) = \frac{1}{1-2x - \frac{-2x^k}{1+x+x^2 +...+x^{k-1}}}$$
where
So , $$A(x) = \frac{1+x+x^2+..x^{k-1}}{1-x-x^2 - ...-x^{k-1}}$$
Then , by the same method ; $$a_{n+k-1}-a_{n+k-2}-a_{n+k-3}-...-a_{k-1}=0$$
Then , for example , if $k=5$ , then $$a_{n+4}-a_{n+3}-a_{n+2}-...-a_{n}=0$$
So , $$a_n=a_{n-1}+a_{n-2}+a_{n-3}+a_{n-4}$$
As a result , for any $k >1 $ ,the number of binary strings that do contain neither $k$ zeros nor $k$ ones is : $$a_n=a_{n-1}+a_{n-2}+...+a_{n-k+1}$$