Problem: I have an alphabet with n=8 letters (say $X=\{A, B, C, D, E, F, G, H\}$). I'm looking for words with m=24 letters, with three constraints:
- letter $A$ is the relative majority (like in $ABCAAFFHABCAAFFHABCAAFFH$ where $A$ appears 9 times, i.e., more than all other letters) (we could use "plurality" for this concept).
- one letter at one position is fixed (two cases: an $A$ or another letter)
- the general pattern $p$ is fixed (by pattern, I mean $ABCAFHABCAFHABCAFH$ for the previous example, i.e., the order, without the number of letters) (let's define $p_A$ the number of $A$'s in the pattern. Here, $p_A=6$. Let's also define $p_{A1}$ the number of $A$'s in the first interval in the pattern. Here, $p_{A1}=1$.)
Simple example: with $X=\{A, B, C\}$ and $n=8$. The question is: how many eight-letter words with an $A$ in the third position have a (relative) majority of $A$'s and the pattern $BABCA$? And how many have a (relative) majority of $B$'s?
Solution for the simple example:
The fixed $A$ cannot be in the second $A$-interval in the pattern: $A$ is the last letter in the pattern, and so the fixed $A$ can be followed only by other $A$'s and the pattern would not be reproduced. Still, in general cases, the fixed $A$ could be in different intervals.
Once we have decided that $A$ is in the first interval, we iterate on $k$, the number of $A$-letter in the word. There must be at least one in each interval, thus at least two in this example.
With $k=2$ and $k=3$, there are no possible outcome, since there would be $k$ $A$'s letters and $k-1$ other letters ($B$ and $C$). Since there are only three letters, we cannot make an 8-letter word ($2+1*2, 3+2*2 \leq 8$).
With $k=4$, the 7 possible outcomes are:
- $BAAABBCA$
- $BAAABCCA$
- $BAABBCAA$
- $BAABCCAA$
- $BBABCAAA$
- $BBAABCAA$
- $BBAAABCA$
- With $k=5$, there are 3 possible outcomes:
- $BAAAABCA$
- $BAAABCAA$
- $BAABCAAA$
There are no possibilities with $k=6$ (no room to reproduce the pattern: 8 letters in total, minus 6 $A$'s, 2 spaces remaining, but 3 non-$A$ occurrences in the pattern).
So in total, there are 10 possibilities for this simple example.
How can I start to solve this problem using analytic combinatorics? I'm looking for a general expression for any pattern.
Tentative answer:
Only constraint (1): Majority
Solution is $$\left[\frac{x^{m}}{m!}\right]\sum_{k\ge0} \frac{x^k}{k!}\left(1+x+\frac{x^2}{2!}+\cdots+\frac{x^{k-1}}{(k-1)!}\right)^{n-1}$$ From here.
Only constraints (1) and (2): Majority + One letter fixed
If we fix an $A$, solution is: $$\left[\frac{x^{m-1}}{(m-1)!}\right] \sum_{k\ge0} \frac{x^{k-1}}{(k-1)!}\left(1+x+\frac{x^2}{2!}+\cdots+\frac{x^{k-1}}{(k-1)!}\right)^{n-1}$$
If we fix another letter, solution is: $$\left[\frac{x^{m-1}}{(m-1)!}\right] \sum_{k\ge0} \frac{x^{k}}{k!}\left(1+x+\frac{x^2}{2!}+\cdots+\frac{x^{k-1}}{(k-1)!}\right)^{n-2}\left(1+x+\frac{x^2}{2!}+\cdots+\frac{x^{k-2}}{(k-2)!}\right)$$
From here.
All constraints (attempt), case when an $A$ is fixed
- Fix the interval for the fixed $A$. Number of possibilities: $$p_A$$
- Iterate over $k-1$, the number of non-fixed $A$'s. Number of possibilities: $$[t^{m-1}]p_A\sum_{k\ge0} [(k-1)\times A][(k-1)\times \text{other letters}]$$
For each possible number $k-1$ of $A$'s, distribute them in the intervals of $A$'s in the pattern, i.e., distribute $k-1$ remaining balls in $p_A$ urns, with one urn already containing one $A$. All other must contain at least one $A$. Number of possibilities: $$p_A[t^{m-1}]\sum_{k\ge0} (t+t^2+t^3+...)^{p_A-1}(1+t+t^2+...)[(k-1)\times \text{other letters}]=p_A[t^{m-1}]\sum_{k\ge0} t^{p_A-1}(1+t^1+t^2+...)^{p_A-1}\frac{t}{1-t}[(k-1)\times \text{other letters}]=p_A[t^{m-1}]\sum_{k\ge0} t^{p_A-1}(\frac{t}{1-t})^{p_A-1}\frac{t}{1-t}[(k-1)\times \text{other letters}]=p_A[t^{m-1}]\sum_{k\ge0} t^{p_A-1}(\frac{t}{1-t})^{p_A}[(k-1)\times \text{other letters}]=p_A[t^{m-1}]\sum_{k\ge0} \frac{t^{2p_A-1}}{(1-t)^{p_A}}[(k-1)\times \text{other letters}]$$
For each non-$A$ letter, distribute more than one and up to $k-1$ times each letter in each interval. Number of possibilities (a similar development can be found here):
\begin{align*}\text{possibilities} & = p_A[t^{m-1}]\sum_{k\ge0} \frac{t^{2p_A-1}}{(1-t)^{p_A}}\prod_{x\in X, x\neq A} (t+t^2+...+t^{k-1})^{p_x} \\ & = p_A[t^{m-1}]\sum_{k\ge0} \frac{t^{2p_A-1}}{(1-t)^{p_A}}\prod_{x\in X, x\neq A} t^{p_x}(1+t+...+t^{k-2})^{p_x}\\ & = p_A[t^{m-1}]\sum_{k\ge0} \frac{t^{2p_A-1}}{(1-t)^{p_A}}\prod_{x\in X, x\neq A} t^{p_x}(\frac{1-t^{k-1}}{1-t})^{p_x}\\ & = p_A[t^{m-1}]\sum_{k\ge0} \frac{t^{2p_A-1}}{(1-t)^{p_A}} t^{\sum_{x\in X, x\neq A} p_x}(\frac{1-t^{k-1}}{1-t})^{\sum_{x\in X, x\neq A} p_x} \\ & = p_A[t^{m-1}]\sum_{k\ge0} \frac{t^{\sum_{x\in X, x\neq A} p_x + 2p_A-1}}{(1-t)^{\sum_{x\in X, x\neq A} p_x + p_A}} (1-t^{k-1})^{\sum_{x\in X, x\neq A} p_x}\\ & = p_A[t^{m-1-\sum_{x\in X, x\neq A} p_x + 2p_A-1}]\sum_{k\ge0} \frac{1}{(1-t)^{\sum_{x\in X, x\neq A} p_x + p_A}} (1-t^{k-1})^{\sum_{x\in X, x\neq A} p_x} \\ & = p_A[t^{m-1-\sum_{x\in X, x\neq A} p_x + 2p_A-1}]\sum_{k\ge0} (1-t^{k-1})^{\sum_{x\in X, x\neq A} p_x}\sum_{j\ge 0} \binom{-\sum_{x\in X, x\neq A} p_x + p_A}{j} (-t)^j \\ & = p_A[t^{m-1-\sum_{x\in X, x\neq A} p_x + 2p_A-1}]\sum_{k\ge0} (1-t^{k-1})^{\sum_{x\in X, x\neq A} p_x}\sum_{j\ge 0} \binom{j-1 +\sum_{x\in X, x\neq A} p_x + p_A}{j} t^j\end{align*}
Since we extract coefficients of $x^{k-1}$, there will be $k-1$ non-$A$ letters in the intervals.
Result applied to the simple example ($p_A=2, m=8, n=3$):
$$2[t]\sum_{k=1}^8 (1-t^{k-1})^{3} \sum_{j\ge 0}\binom{5+j-1}{j} t^j$$