Counting elements in cartesian power with plurality + pattern constraints 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$$
 A: We are given $n$ letters and a pattern $p$ to make an $m$ letter word satisfying any combination of the constraints (1), (2), (3). Whenever we consider (1), we let letter $A$ be the (relative) strict majority. Let $p_L$ be the number of $L$'s in the pattern $p$ (not the word). Let $L_i$ be the location of the $i$th occurrence of $L$ in $p$.  Let $e_k$ be the exponential sum function. I use square brackets $[x^k] \mathcal{f}$ precisely to denote the coefficient of $x^k$ in the formal power series of $\mathcal{f}$. The compiled solutions:
$\qquad$ (1) $\qquad$ $\left[\frac{x^{m}}{m!}\right]\sum_{k\ge0} \frac{x^k}{k!}\,(e_{k-1})^{n-1}$
$\qquad$ (2) $\qquad$ $n^{m-1} $
$\qquad$ (3) $\qquad$ ${ m-1 \choose \mid p\mid-1 } $
$\qquad$ (1,2)
$ \qquad \qquad \qquad \text{Fix } A \qquad \left[\frac{x^{m-1}}{(m-1)!}\right]
\sum_{k\ge0} \frac{x^{k-1}}{(k-1)!} \,(e_{k-1})^{n-1}$
$ \qquad \qquad \qquad \text{Fix } B \qquad \left[\frac{x^{m-1}}{(m-1)!}\right]
\sum_{k\ge0} \frac{x^{k}}{k!} \; (e_{k-1})^{n-2} \,e_{k-2}$
$\qquad$ (1,3) 
$ \qquad \qquad \qquad \left[ x^m \right] \sum_{a=p_A}^m {a-1 \choose p_A - 1} x^a \prod_{L\neq A} \sum_{i=p_L}^{a-1} {i - 1 \choose p_L - 1} x^i $
$\qquad$ (2,3) 
$\qquad \qquad \qquad \text{Fix } L \text{ at } k \qquad \sum_{i=1}^{p_L} {k-1 \choose L_i-1} {m-k \choose |p| - L_i}$
$\qquad$ (1,2,3) ? $\tiny{\text{ see special case below}}\\$

Once you realize (3) you get (2,3) by splitting up the sequence [1..k][k..m] and putting the $i$th interval of $L$ at position $k$. We can solve (1,3) by using ordinary generating functions.
(1,3)
$$
\begin{array} (
& \displaystyle \left[ x^m \right]_{\text{given (1)}} \sum_{a=1}^{m} x^a \left[ x^a \right] \left( x+x^2+\ldots \right)^{p_A} \prod_{L \neq A} \left( x + x^2 + \ldots \right)^{p_L} \\
= & \displaystyle \left[ x^m \right] \sum_{a=1}^{m} x^a \left[ x^a \right] \left( \frac{x}{1-x} \right)^{p_A} \prod_{L \neq A} \sum_{i=0}^{a-1} x^i \left[ x^i \right]  \left( \frac{x}{1-x} \right)^{p_L} \\
= & \displaystyle \left[ x^m \right] \sum_{a=p_A}^m {a-1 \choose p_A - 1} x^a \prod_{L \neq a} \sum_{i=p_L}^{a-1} {i -1 \choose p_L - 1} x^i \\
\end{array}
$$
Note the upper bound of the outer sum can be taken as $m-|p|+p_A$ and the upper bound of the inner sum can be taken as $\min\{a-1, m-a-\mid \!p\! \mid+ \, p_A+p_L\}$.

The formula above isn't very useful from a computational standpoint. We can however find a usable formula if we add another constraint. Let 3' be the  special case of constraint 3 where no letter appears more than once in $p$. Define 
$$ 
\begin{array} (
\mathcal{I}_{(\kappa,\mu,\eta)} 
& \displaystyle = \left[ x^{\eta} \right] \left( x + \ldots + x^{\mu-1} \right)^{\kappa} \\
& \displaystyle = \sum_{i=0}^{ \min\left\{\kappa, \left\lfloor \frac{\eta-\kappa}{\mu} \right\rfloor \right\}} (-1)^i {\kappa \choose i} {\eta - 1 - i\,\mu \choose \kappa-1} 
\end{array}
$$
Combinatorially I like to think of this as the number of integer solutions to $\sum_{i=1}^{\kappa} x_i = \eta $ where $1 \leq x_i < \mu$. The reason we define $\mathcal{I}$ is because we can frame our problem in such terms. For example, (3) = $\mathcal{I}_{(\mid p \mid, m, m)}$. Finally, let $\pi_L$ denote the position of $L$ in $p$. Then we have
$\qquad$ (1,3')
$$ 
\begin{align}
& \left[ x^m \right] \sum_{a=1}^{m} x^{a} \, (x + \ldots + x^{a-1})^{\mid p \mid-1} \\
& = \sum_{a = 1}^m \mathcal{I}_{\left(\mid p \mid - 1,\; a,\; m - a \right)}
\end{align}
$$
$\qquad$ (1,2,3')
$$ 
\begin{array} (
& \text{Fix } A \text{ at } k & \;
    & \displaystyle \sum_{a = 1}^m \sum_{\ell = 1}^{a} 
           \mathcal{I}_{\left( \pi_A - 1, \; a , \; k - \ell \right)} \; 
           \mathcal{I}_{\left( \mid p \mid - \pi_A, \; a, \; m - k - 
           a + \ell \right)} \\
& \text{Fix } B \text{ at } k, \; \pi_B < \pi_A & \;
    & \displaystyle \sum_{a = 1}^m \sum_{b = 1}^{a - 1} 
      \sum_{\ell = 1}^{b} 
           \mathcal{I}_{\left( \pi_B - 1, \; a , \; k - \ell \right)} \; 
           \mathcal{I}_{\left( \mid p \mid - \pi_B - 1, \; a, \; m - k - 
           a - b + \ell \right)} \\
& \text{Fix } B \text{ at } k, \; \pi_B > \pi_A & \;
    & \displaystyle \sum_{a = 1}^m \sum_{b = 1}^{a - 1} 
      \sum_{\ell = 1}^{b} 
           \mathcal{I}_{\left( \pi_B - 2, \; a , \; k - a - \ell \right)} \; 
           \mathcal{I}_{\left( \mid p \mid - \pi_B , \; a , \; m - k - 
           b + \ell \right)} \\ & \\
\end{array}
$$
Note that I use the variables $a,b$ to specify the number of $A$'s and $B$'s in the final sequence. When fixing letter $L$ at $k$, the $\ell$ iterate specifies the number of $L$'s left of position $k$ (inclusive). Finally, notice how (1,3) reduces to (1,3') when $p_L = 1$ for all $L$ in $p$.
