Generalized repetitions of letters with limited amount of adjacent letters

Question

Say I have the first $x$ letters of the alphabet, and I want to generate a sequence of length $y$, such that there are no more than $z$ adjacent repeated letters. For example, if $x = 2$, $y = 3$ and $z = 2$, here are all the valid sequences:

AAB ABA ABB BAA BAB BBA

How many total possible sequences are there?

Without the restriction of z, the question devolves to $x^y$, but I am stuck as to how to proceed further.

The case I have described earlier is also not too hard, I think it is $x^y-x$ since $z = y-1$.

Would it be better to count all cases and subtract (like I did for the $z = y-1$ case) or should I try and count upwards?

To be clear, you are allowed to repeat letters as many times as you want so long as they never lie next to each other more than $z$ times.

Thanks for the help!

Answer 1

The following answer is based upon the Goulden-Jackson Cluster Method which provides a convenient technique to solve problems of this kind. We consider the set of words of length $y\geq 0$ built from an alphabet $$\mathcal{V}=\{A_1,A_2,\ldots A_x\}$$ and the set $B=\{A_1^{z+1},A_2^{z+1},\ldots,A_x^{z+1}\}$ of bad words each of length $z+1$, which are not allowed to be part of the words we are looking for. We derive a generating function $f(t)$ with the coefficient of $t^y$ being the number of wanted words of length $y$.

According to the paper (p.7) the generating function $f(t)$ is \begin{align*} f(t)=\frac{1}{1-xt-\text{weight}(\mathcal{C})}\tag{1} \end{align*} with $x=|\mathcal{V}|$ the size of the alphabet and $\mathcal{C}$ the weight-numerator of bad words with \begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[A_1^{z+1}])+\text{weight}(\mathcal{C}[A_2^{z+1}]) +\cdots+\text{weight}(\mathcal{C}[A_x^{z+1}])\tag{2} \end{align*}

We calculate according to the paper for $1\leq j\leq x$: \begin{align*} \text{weight}(\mathcal{C}[A_j^{z+1}])&=-t^{z+1}-(t+t^2+\cdots+t^{z})\text{weight}(\mathcal{C}[A_j^{z+1}])\tag{3}\\ \end{align*} where the long expression at the right-hand side of (3) accounts for overlappings of $A_{j}^{z+1}$ with itself. We obtain from (3): \begin{align*} \text{weight}(\mathcal{C}[A_j^{z+1}])&=-\frac{t^{z+1}}{1+t+\cdots t^{z}}\\ &=-\frac{t^{z+1}(1-t)}{1-t^{z+1}}\qquad\qquad 1\leq j \leq x\\ \end{align*} It follows from (1) - (3): \begin{align*} \color{blue}{f(t)}&=\frac{1}{1-xt-\text{weight}(\mathcal{C})}\\ &=\frac{1}{1-xt+x\frac{t^{z+1}(1-t)}{1-t^{z+1}}}\\ &\,\,\color{blue}{=\frac{1-t^{z+1}}{1-xt-(1-x)t^{z+1}}}\tag{4} \end{align*} and conclude the number of valid words of length $y\geq 0$ is the coefficient of $t^y$ in (4). We use the coefficient of operator $[t^y]$ to denote the coefficient of $y^n$ of a series. Applying standard techniques to extract the coefficient $[t^y]$ from $f(t)$ we obtain \begin{align*} [y^t]f(t)&=\sum_{k=0}^{\left\lfloor\frac{y}{z}\right\rfloor}\binom{y-zk}{k}(1-x)^kx^{y-(z+1)k}\\ &\qquad- \sum_{k=0}^{\left\lfloor\frac{y-z-1}{z}\right\rfloor}\binom{y-z-1-zk}{k}(1-x)^kx^{y-z-1-(z+1)k}\tag{5} \end{align*}

Example: $x=2,y=3,z=2$

We look at OPs example where the alphabet $\mathcal{V}=\{A,B\}$ consists of two characters. Invalid words are those containing substrings which are elements from the set of $\{AAA,BBB\}$ of bad words. According to (4) the generating function is given as

\begin{align*} f(t)&=\left.\frac{1-t^{z+1}}{1-xt-(1-x)t^{z+1}}\right|_{x=2,z=2}\\ &=\frac{1-t^3}{1-2t+t^3}\\ &=1 + 2 t + 4 t^2 + 6t^3 + \color{blue}{10} t^4 + 16 t^5\\ &\qquad + 26 t^6 + 42t^7 + 68 t^8 +\cdots\\ \end{align*}

The last line was calculated with some help of Wolfram Alpha. Note, the coefficient $6$ of $t^{3}$ according to the six valid words stated by OP. The blue marked coefficient of $t^4$ is $10$ and the $2^4-10=6$ invalid words are \begin{align*} &\rm{\color{blue}{aaa}a}&\rm{a\color{blue}{bbb}}\\ &\rm{\color{blue}{aaa}b}&\rm{b\color{blue}{bbb}}\\ &\rm{b\color{blue}{aaa}}&\rm{\color{blue}{bbb}a}\\ \end{align*}

Applying (5) we find \begin{align*} \color{blue}{[t^3]f(t)}&=\sum_{k=0}^1\binom{3-2k}{k}(-1)^k2^{3-3k}-\sum_{k=0}^0\binom{0-2k}{k}(-1)^k2^{0-3k}\\ &=\binom{3}{0}(-1)^02^3+\binom{1}{1}(-1)^12^0-\binom{0}{0}(-1)^02^0\\ &=8-1+1\\ &\,\,\color{blue}{=6}\\ \\ \color{blue}{[t^4]f(t)}&=\sum_{k=0}^2\binom{4-2k}{k}(-1)^k2^{4-3k}-\sum_{k=0}^0\binom{0-2k}{k}(-1)^k2^{1-2k}\\ &=\binom{4}{0}(-1)^02^4+\binom{2}{1}(-1)^12^1+\binom{0}{2}(-1)^22^{-2}-\binom{0}{0}(-1)^02^1\\ &=16-4+0-2\\ &\,\,\color{blue}{=10} \end{align*}

in accordance with the results above.

Answer 2

Partial Answer (assuming $2z \geq y$ and $x \geq 2$)

First note that if $z \geq y$, there is no restriction on which letters can be placed where. If $P$ denotes the number of possible sequences, this is to say $P = x^y$ in this case.

Now suppose $z < y$. We can use the subtraction principle as you alluded to. We need to find the number of sequences that have more than $z$ adjacent letters. Let's call this number $R$. In order to construct $R$, we will need to form a sum, each term being all possible "bad" sequences of a fixed number of repeating letters more than $z$. I find an example illustrative.

Suppose $x =3$, $y= 6$, and $z = 3$. Then any sequence with 4 or more adjacent letters is "bad" and we need to include it in $R$. One such sequence, given this $x,y,z$, is: $$ AAAABB . $$ We note there are a few ways to "place" the block of $A$'s within the length 6 sequence, in this case $3$. In general, if our string of adjacent letters has length $L \leq y$, the number of ways to place the block is $y-L + 1$. Moreover, this block of adjacent letters could be any of $x$ letters, so we multiply the term by $x$. In our example, we could have: $$ CCCCBB. $$ Finally, we want to count the number of ways the slots unoccupied by the block of adjacent letters could be chosen. We want to be careful not to double count. In the example above, notice the last two slots are the unoccupied ones. Since we are summing over length of adjacent letter blocks, $L$, notice if we let slot $5$ be $C$ we would double count when we increased $L$ to $5$ (currrently $L = 4$). So we allow slot $5$ to be any of the $x-1$ remaining letters, in this case $A$ or $B$. On the contrary, slot $6$ can be any of the $x$ letters, $A$,$B$, or $C$ in this case. Let $j$ denote the number of adjacent positions to the block of $L$ letters. We see in any case that $j \in \{0,1,2\}$. For example, $j = 0$ for: $$ AAAAAA, $$ while $j = 2$ for: $$ BAAAAB. $$ A key is that the number of slots which can have $x - 1$ letters as opposed to $x$ letters is dependent on the placement of the $L$ adjacent blocks. To account for this, define the sequence: $$ S_L = \begin{cases} (1, 2, \dots, 2, 1) & y - L -1 \geq 0, \\ (0) & y - L - 1 < 0 \end{cases} $$ where the number of $2$'s is equal to $y - L - 1$, in the top case. We stated earlier the number of ways to place the block of $L$ adjacent letters is $y - L +1$, and observe this is precisely the length of $S_L$ in each case. Moreover, the terms in $S_L$ are precisely the number of slots adjacent to the block of $L$ letters, i.e. slots that can have only $x-1$ letters as options. We can imagine this as placing the block of $L$ letters as far to the left as possible, and consider sliding it over one slot at a time until it reaches the right hand side. In context of our example, we have $L = 4$, so we have $y - L + 1 = 3$ options for where to place a block of $L$ letters ($A$'s in this example): $$ AAAA \: \_\_ \: \_\_ \; , \; \_\_ \: AAAA \: \_\_ \; , \; \_\_ \: \_\_ \:AAAA $$ The sequence that corresponds to this is $S_L = (1,2,1)$, since $y - L - 1 = 1$, so we have one $2$, which corresponds to the two adjacent slots for the middle placement above (and the $1$'s are of course the number of adjacent slots for the first and last placements of the $A$'s).

With this, we can write down the sum (it will actually be a double sum, accounting for the slots adjacent to the $L$ letter block in each placement). The number of invalid sequences of letters for given $x,y,z$ are: $$ R = \sum_{L = z+1}^{y} \sum_{j \in S_L} x(x-1)^{j}x^{y-L-j}. $$ By subtraction principle, we have $P = x^y - R$, which is to say, the number of sequences of length $y$ from an $x$ letter alphabet with no more than $z$ adjacent repeating letters is: $$ P = x^y - \sum_{L = z+1}^{y} \sum_{j \in S_L} x(x-1)^{j}x^{y-L-j}. $$

Note: this formula agrees with your given example of $x = 2, y = 3, z =2$, as this forces $L = 3$, so that $S_L = 0$ and: $$ P = x^y - x(x-1)^0 x^{y-y-0} = x^y - x. $$

Answer 3

If $z = 1$, you can pick any of the $x$ letters to be first in the sequence. At each step, you have to use a different letter than the one you just used, so you have $x-1$ choices, for a total of

$$x(x-1)^{y-1}$$

options.

When $z \geq 2$, the analysis is complicated by the fact that the blocks are not of equal sizes. So let's find the answer in the case where we know exactly how many blocks of each size there are. Suppose there are:

• $B_1$ blocks of length 1
• $B_2$ blocks of length 2
• $B_3$ blocks of length 3...

and so on, up to $B_z$ blocks of size $z$. Since the total length of the string is $y$, the only restriction on these block sizes is $0 \leq B_i$ for each $1 \leq i \leq z$, and

$$B_1 + 2B_2 + ... + zB_z = y.$$

There are

$$\frac{(B_1 + B_2 + ... + B_z)!}{B_1! B_2! ... B_z!}$$

ways that we can order the blocks within the sequence, and adjacent blocks must use different letters. So we can pick the first block to be any of the $x$ letters, and each new block must use a different letter from the preceding block, of which there are $(x-1)$. Since the total number of blocks is $B_1 + ... + B_z$, we thus have, for a specific sequence of blocks, that there are

$$x(x-1)^{B_1 + ... + B_z - 1}$$

ways to pick the letter for each block. So if I know the block sizes $B_1$ through $B_z$, the number of possible sequences with those block sizes is given by

$$\frac{(B_1 + B_2 + ... + B_z)!}{B_1! B_2! ... B_k!} * x(x-1)^{B_1 + ... + B_z - 1},$$

and the answer to OP's question is then the sum

$$\sum_{B_1 + 2B_2 + ... + zB_z = y} \frac{(B_1 + B_2 + ... + B_z)!}{B_1! B_2! ... B_k!} * x(x-1)^{B_1 + ... + B_z - 1}$$

over all tuples of nonnegative integers $(B_1, ..., B_z)$ satisfying the condition $B_1 + 2B_2 + ... + zB_z = y$.

Answer 4

The following are actually some complementary notes to the approach proposed by Rivers , too long for a comment.
The problem is quite interesting to deserve t be analyzed under many perspectives

Let's start and exemplify the method by taking the ternary word $[a,a,c,c,c,b]$ of length $6$ and building the following prospect $$ \begin{array}{c|cccccc} {{\rm char}{\rm .}\,{\rm position}} & & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline {{\rm word}} & & a & a & c & c & c & b \\ \hline {{\rm No}{\rm .}\;{\rm repet}{\rm .}} & & 1 & 2 & 1 & 2 & 3 & 1 \\ \hline {{\rm block n}{\rm .}} & & {} & {\left. {1\;} \right|} & {} & {} & {\left. {2\;} \right|} & {\left. {3\;} \right|} \\ \hline {{\rm max rep}{\rm .}\,{\rm /}\,{\rm block}} & & {} & {\left. {2\;} \right|} & {} & {} & {\left. {3\;} \right|} & {\left. {1\;} \right|} \\ \end{array} $$

We count sequentially the number of contiguous repeated characters, and individuate the relevant blocks and the respective lengths.

At this point allow me to change your notation into a better mnemonic one and consider

• words from alphabet $\{1,2, \cdots, a\}$,
• of length $n$,
• with $b$ blocks of adjacent repeated characters,
• each block containing max $ r$ repetitions of the same character.
  the four parameters being positive integers.

Clearly the number of characters in the various blocks represent a composition of $n$ into $b$ parts each not grater than $r$, that is $$ \eqalign{ & {\rm No}{\rm .}\,{\rm of}\,{\rm solutions}\,{\rm to}\;\left\{ \matrix{ {\rm 1} \le {\rm integer}\;x_{\,j} \le r \hfill \cr x_{\,1} + x_{\,2} + \; \cdots \; + x_{\,b} = n \hfill \cr} \right.\quad \Rightarrow \cr & \Rightarrow \quad {\rm No}{\rm .}\,{\rm of}\,{\rm solutions}\,{\rm to}\; \left\{ \matrix{ {\rm 0} \le {\rm integer}\;y_{\,j} \le r - 1 \hfill \cr y_{\,1} + y_{\,2} + \; \cdots \; + y_{\,b} = n - b \hfill \cr} \right.\quad = \cr & = N_{\,b} (n - b,r - 1,b) = \cr & = \left[ {b \le n} \right]\left[ {1 \le r} \right]\left[ {0 \le b} \right] \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,{{n - b} \over r}\, \le \,b} \right)} {\left( { - 1} \right)^k \left( \matrix{ b \hfill \cr k \hfill \cr} \right) \left( \matrix{ n - 1 - kr \cr n - b - kr \cr} \right)} \cr} $$ the formula for $N_{\,b}$ being explained in this post and other related.
(the suffix $b$ to $N$ is not related to the parameter $b$ herewith and is kept for congruence with previous posts).
Here $[P]$ denotes the Iverson bracket.

Now we have $a$ choices as for the character in the first block, while from the second block on we have to put a character different from the precedent block, and so $a-1$ choices.

Thus the number of good words we are looking for is $$ G_{\,1} (n,a,r) = \sum\limits_{1\, \le \,b\, \le \,n} {N_{\,b} (n - b,r - 1,b)a\left( {a - 1} \right)^{\,b - 1} } $$ when all the parameters are positive. If we include the empty word $n=0$, for which $r=0$ is allowed, and the empty alphabet $a=0$, for which only the empty word is included we get $$ \bbox[lightyellow] { G(n,a,r) = \left[ {0 = n} \right] + \sum\limits_{1\, \le \,b\, \le \,n} {N_{\,b} (n - b,r - 1,b)a\left( {a - 1} \right)^{\,b - 1} } \tag {1} }$$

The connection with Rivers's answer comes from the fact that one of the expressions of $N_{\,b}$ is $$ \eqalign{ & N_{\,b} (n - b,r - 1,b) = \sum\limits_{\;\left\{ {\matrix{ {\;k_{\,0} + \,k_{\,1} + \,\,k_{\,2} \, + \,\,\, \cdots \, + \,\,\,k_{\,r - 1} = \;b\;} \cr {\,0k_{\,0} + 1k_{\,1} + 2k_{\,2} + \, \cdots \, + \left( {r - 1} \right)k_{\,r - 1} = \,n - b} \cr } } \right.\;} {\left( \matrix{ b \cr k_{\,0} ,k_{\,1} ,\,\,k_{\,2} \,,\,\,\, \cdots \,,\,\,\,k_{\,r - 1} \cr} \right)} = \cr & = \sum\limits_{\;\left\{ {\matrix{ {\;\,k_{\,1} + \,\,k_{\,2} \, + \,\,\, \cdots \, + \,\,\,k_{\,r} = \;b\;} \cr {\,1k_{\,1} + 2k_{\,2} + \, \cdots \, + rk_{\,r} = \,n} \cr } } \right.\;} {\left( \matrix{ b \cr k_{\,1} ,\,\,k_{\,2} \,,\,\,\, \cdots \,,\,\,\,k_{\,r} \cr} \right)} \cr} $$

The connection with Markus's answer comes instead from the fact that the double ogf for $N_{\,b}$ is $$ F_{\,b} (x,r,z) = \sum\limits_{0\, \le \,s,\,m} {N_{\,b} (s,r,m)\;x^{\,s} \;z^{\,m} } = {1 \over {1 - z{{1 - x^{\,r + 1} } \over {1 - x}}}} $$ and therefore $$ \eqalign{ & F(x,a,r) = \sum\limits_{0\, \le \,n} {G(n,a,r)x^{\,n} } = \cr & = \sum\limits_{0\, \le \,n} {\left[ {0 = n} \right]\;x^{\,n} } + \sum\limits_{1\, \le \,b} {\sum\limits_{b\, \le \,n} {N_{\,b} (n - b,r - 1,b)\;x^{\,n} \;a\left( {a - 1} \right)^{\,b - 1} } } = \cr & = 1 + \sum\limits_{0\, \le \,b} {\sum\limits_{0\, \le \,n - 1 - b} {N_{\,b} (n - 1 - b,r - 1,b + 1)\;x^{\,n} \;a\left( {a - 1} \right)^{\,b} } } = \cr & = 1 + ax\sum\limits_{0\, \le \,b} {\sum\limits_{0\, \le \,n - 1 - b} {N_{\,b} (n - 1 - b,r - 1,b + 1)\;x^{\,n - 1 - b} \;\left( {\left( {a - 1} \right)x} \right)^{\,b} } } = \cr & = 1 + ax\sum\limits_{0\, \le \,b} {\left( {{{1 - x^{\,r} } \over {1 - x}}} \right)^{\,b + 1} \; \left( {\left( {a - 1} \right)x} \right)^{\,b} } = \cr & = 1 + ax\left( {{{1 - x^{\,r} } \over {1 - x}}} \right) {1 \over {1 - \left( {a - 1} \right)x{{1 - x^{\,r} } \over {1 - x}}}} = \cr & = 1 + {{ax\left( {1 - x^{\,r} } \right)} \over {1 - x - \left( {a - 1} \right)x\left( {1 - x^{\,r} } \right)}} = \cr & = {{1 - x^{\,r + 1} } \over {1 - ax + \left( {a - 1} \right)x^{\,r + 1} }} \cr} $$