Counting elements in cartesian power with plurality + pattern constraints

Question

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:

1. 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).
2. one letter at one position is fixed (two cases: an $A$ or another letter)
3. 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:

1. 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.

2. 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.

   1. 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$).

   2. With $k=4$, the 7 possible outcomes are:

      • $BAAABBCA$
      • $BAAABCCA$
      • $BAABBCAA$
      • $BAABCCAA$
      • $BBABCAAA$
      • $BBAABCAA$
      • $BBAAABCA$
   3. 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

1. Fix the interval for the fixed $A$. Number of possibilities: $$p_A$$
2. 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}]$$

3. 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}]$$

4. 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$$

Answer 1

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$.