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 !!!


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.


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.


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.