I am a newbie in binary strings and generating series. I have a problem of enumeration which can be transformed to the following: find the number of binary strings of exactly $n$ ones which do not contain three consecutive ones or three consecutive zeros. The answer can be given as a coefficient of a generating series.
I don't know how to begin with. Thanks for any help!
On
For these kinds of problems, I like to start with the part of the language that can be repeated and worry about fixing the ends of the strings afterwards. Here, the repeating part of the language is $(\{0,00\}\{1,11\})^*$. I.e. you can have one or two $0$s followed by one or two $1$s and just repeat that over and over again.
However, such strings will always start with a $0$ and end with a $1$ whereas we need to allow them to start with a $1$ or end with a $0$ as well. Therefore, at the beginning, we allow also $\{\epsilon, 1, 11\}$ and at the end, $\{\epsilon, 0, 00\}$. That finally gives
$$\{\epsilon, 1, 11\}(\{0,00\}\{1,11\})^*\{\epsilon, 0, 00\}.$$
This gives the generating function
$$ (1 + x + x^2) \frac{1}{1 - (1 + 1)(x + x^2)} (1 + 1 + 1).$$
We can simplify this to
$$\frac{3(1 + x + x^2)}{1 - 2x - 2x^2}.$$
The following approach may be an overkill, but it's systematic and can easily get answer to many other similar problems.
Consider the de Bruijn graph on $4$ vertices representing elements of $\{0,1\}^2$ (ie., $00$, $01$, $10$, and $11$), where edges represent elements of $\{0,1\}^3$. Remove edges corresponding to $000$ and $111$, and assign an algebraic weight $x$ to any edge leading to vertex $*1$, and weight $x^0=1$ to any edge leading to $*0$, and call the resulting graph $G$. Let $A$ be the (weighted) adjacency matrix of $G$ (with the same order of rows/columns as in the list of vertices above), that is
$$A = \begin{bmatrix} 0 & x & 0 & 0 \\ 0 & 0 & 1 & x \\ 1 & x & 0 & 0 \\ 0 & 0 & 1 & 0 \end{bmatrix}$$
Any binary string of length $\ell\geq 2$ without $000$ and $111$ represents a walk of length $\ell-2$ in $G$, and the power of $x$ in the weight of such a walk accounts for number of ones. More precisely, the number of binary strings of length $\ell\geq 2$ with exactly $n$ ones but without $000$ and $111$ is given by the coefficient $x^n$ in $$[1,x,x,x^2]\cdot A^{\ell-2}\cdot [1,1,1,1]^T.$$ Summing over all $\ell\geq 2$, we get $$[1,x,x,x^2]\cdot (I-A)^{-1}\cdot [1,1,1,1]^T = \frac{1 + 6x + 9x^2 + 2x^3}{1 - 2x - 2x^2}.$$ It remains to add the terms corresponding to $\ell=0$ and $\ell=1$ to get the generating function: $$\frac{1 + 6x + 9x^2 + 2x^3}{1 - 2x - 2x^2} + 1 + (1+x) = 3\frac{1 + x + x^2}{1 - 2x - 2x^2}.$$
For more details on this approach, see Section 4.7 The Transfer-matrix Method in Stanley's Enumerative Combinatorics book. Also, in this paper a similar approach is applied to a generalization of Menage Problem.