Suppose a word is $l$ letters long, and it contains $k$ A's. (The specific letter is irrelevant) Is there a general formula to count how many permutations contain at least $n$ consecutive A's? (Assume $n \leq k$)
In a word containing $k$ A’s, how many permutations place at least $n$ A’s consecutively
combinationscombinatoricscombinatorics-on-wordspermutations
Best Answer
It is a little easier to count permutations which do not contain $n$ consecutive $A's$. For now, assume that all the letters not equal to $A$ are the same, say they are all $B$.
There are $l-k$ $B$'s. These divide the string into $l-k+1$ blocks of $A$'s. In each of these blocks there are between zero and $n-1$ $A$'s. Therefore, the number of permutations is equal to the number of integer solutions to the following equations and inequalities: $$ x_1+x_2+\dots+x_{l-k+1}=k,\\ 0\le x_i<n\quad\text{ for }1\le i \le l-k+1 $$ Using the generating function method, this is equal to the coefficient of $t^k$ in $(1+t+t^2+\dots+t^{n-1})^{l-k+1}=(1-t^n)^{l-k+1}(1-t)^{-l+k-1}$, which can be found to be $$ {\sum_{i=0}^{\lfloor k/n\rfloor} (-1)^i\binom{l-k+1}{i}\binom{l-ni}{l-k}} $$ Recall, this is the number of permutations without any $n$ $A$'s in a row. The complementary count is given by subtracting from $\binom{l}k$, resulting in $$ \boxed{\sum_{i=1}^{\lfloor k/n\rfloor} (-1)^{i+1}\binom{l-k+1}{i}\binom{l-ni}{l-k}} $$ If the letters besides $A$ are not all the same, say there are $r$ other varities of letter and $m_i$ letters in the $i^{th}$ variety, then you have to multiply the above quantity by the number of ways to permute the letters, which is the multinomial coefficient $$ \binom{l-k}{m_1,m_2,\dots,m_r}=\frac{(l-k)!}{m_1!\times m_2!\times \dots\times m_r!} $$