Calculate the number of strings of length n containing Xs and Ys, knowing that p adjacent Xs are not allowed 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 !!!
 A: 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.
A: 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.
