Calculate the number of strings of length n containing Xs and Ys, knowing that p adjacent Xs are not allowed

Question

Suppose we have a string of length N, containing only Xs and Ys, (example of a string of length 5: XYXYX).

How can we calculate the number of strings of length N that do not contain P consecutive Xs ( P <= N) ?

I found this in a programming problem, and I wonder if it can be solved mathematically, I found the answer for a pretty similar problem here in Stack Exchange, about a bit string that does not contain 2 adjacent 0s, but I can't find the tip to adjust it to my problem, could anyone help me with this? Thank you !!!

Answer 1

I would tackle this question using symbolic dynamics, and in particular subshifts of finite type. The shift of finite type $X_{\mathcal{F}}$ over alphabet $\mathcal{A} = \{X,Y\}$ with set of forbidden words $\mathcal{F} = \{\underbrace{XX \cdots XX}_{P\text{ times}}\}$ is what you want to consider.

Form the associated transition matrix to this SFT $M$ and then calculate $M^N$. This matrix encodes the number of length-$N$ words in $X_{\mathcal{F}}$, with the entry $M^N_{i,j}$ being the number of length-$N$ words that begin with $i$ and end with $j$. Hence, taking the total sum of entries $p(N) = \sum_{i,j} M^N_{i,j}$ is the value you're looking for.

The sequence of integers $p(N)$ is known as the complexity function of the subshift.

Answer 2

For the generating function we get more or less by inspection that it is given by

$$F_P(x, y) = (1+y+y^2+\cdots) \\ \times \sum_{q\ge 0} (x+x^2+\cdots+x^{P-1})^q (y+y^2+\cdots)^q \\ \times (1+x+x^2+\cdots+x^{P-1}) \\ = (1+y+y^2+\cdots) \\ \times \sum_{q\ge 0} y^q x^q (1+x+\cdots+x^{P-2})^q (1+y+\cdots)^q \\ \times (1+x+x^2+\cdots+x^{P-1}) .$$

This is

$$F_P(x, y) = \frac{1}{1-y} \frac{1}{1-yx(1-x^{P-1})/(1-x)/(1-y)} \frac{1-x^{P}}{1-x} \\ = \frac{1-x^{P}}{(1-y)(1-x)-yx(1-x^{P-1})} \\ = \frac{1-x^P}{1-y-x+yx^P}.$$

Now as we no longer need to distinguish between the two variables we may write

$$G_P(z) = \frac{1-z^P}{1-2z+z^{P+1}}.$$

Extracting coefficients we find

$$[z^N] \frac{1}{1-2z+z^{P+1}} = [z^N] \frac{1}{1-z(2-z^P)} = [z^N] \sum_{q=0}^N z^q (2-z^P)^q \\ = \sum_{q=0}^N [z^{N-q}] (2-z^P)^q = \sum_{q=0}^N [z^q] (2-z^P)^{N-q} = \sum_{q=0}^{\lfloor N/P\rfloor} [z^{Pq}] (2-z^P)^{N-Pq} \\ = \sum_{q=0}^{\lfloor N/P\rfloor} [z^q] (2-z)^{N-Pq} = \sum_{q=0}^{\lfloor N/P\rfloor} {N-Pq\choose q} (-1)^q 2^{N-(P+1)q}.$$

Collecting the two contributions we get

$$\bbox[5px,border:2px solid #00A000]{ \sum_{q=0}^{\lfloor N/P\rfloor} {N-Pq\choose q} (-1)^q 2^{N-(P+1)q} - \sum_{q=0}^{\lfloor N/P\rfloor - 1} {N-P(q+1)\choose q} (-1)^q 2^{N-P-(P+1)q}.}$$

We get for $P=3$ the sequence

$$2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, \ldots$$

which points to OEIS A000073 where these data are confirmed. We get for $P=4$ the sequence

$$2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, \ldots$$

pointing to OEIS A000078, where we find confirmation once more. Lastly, $P=6$ yields

$$2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, \ldots$$

pointing to OEIS A001592, also for confirmation.

Note that numerator and denominator of $G_P(z)$ are multiples of $1-z$, which yields the alternate form

$$G_P(z) = \frac{1+z+\cdots+z^{P-1}}{1-z-z^2-\cdots-z^P}.$$

It is now immediate that the recurrence for the numbers appearing here is of the Fibonacci, Tetranacci, Quadranacci etc. type.