4
$\begingroup$

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

$\endgroup$
13
  • 2
    $\begingroup$ You have three quite different problems here, the second one being the easiest to solve. I think it would be better to post two or three different questions. $\endgroup$ Feb 20, 2015 at 17:39
  • 1
    $\begingroup$ Are there more constraints that stop BAAAABCA from being in your solution set? Why does it include words without any majority letter? $\endgroup$ Feb 23, 2015 at 19:36
  • 1
    $\begingroup$ @Antonin Actually with this pattern constraint, you're going to go back from exponential generating functions to ordinary generating functions. The egf only helps when you have a lot of freedom in re-ordering letters. In this case the word is "almost" determined by the pattern - you just have to assign the counts of individual letters to the letters in the pattern, subject to (e.g.) forcing the third letter to be an A, which in general will split into $k$ possibilities if there are $k$ A's in the pattern. Will check in later, but I think that will work. $\endgroup$
    – Tad
    Feb 24, 2015 at 12:32
  • 1
    $\begingroup$ Okay a few things wrong with your solution to (1,2,3). First, there are a few typos under the bullet point 3. Also, if $k-1$ is the number of total $A$'s, you need to single out the coefficient $[x^{k-1}]$. I believe the end of 3. should look like this $$p_A \left[t^{m-k}\right] \sum_{k \geq 0} \left[t^{k-1}\right] \frac{t^{p_A-1}}{(1-t)^{p_A}} [(k-1) \times \text{ other letters}]$$ It's not hard to simplify $\left[t^{k-1}\right] \frac{t^{p_A-1}}{(1-t)^{p_A}}$. $\endgroup$ Feb 26, 2015 at 5:04
  • 1
    $\begingroup$ However, it's still wrong because you can't just multiply by $p_A$. The number of sequences depends not only on which interval of $A$ you choose to fix, but also where it is being fixed (both are inherent to constraint (3)). Also, you can make 4. a lot easier to read if you use $\mid p\! \mid \, = \sum p_L$. $\endgroup$ Feb 26, 2015 at 5:12

1 Answer 1

1
+50
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ Thank you so much for your answer! Few questions: in the first line of the development for (1,3), what do you mean by "given (1)"? From a computational standpoint, why is the result for (1,3) not useful? (again, in the case when $n=8, m=24$). I'm reading your answer and I'll probably have more questions. $\endgroup$
    – Antonin
    Feb 26, 2015 at 10:47
  • $\begingroup$ In order to decompose the first line in (1,3), can we say: first step : $(x+x^2+...)^{p_A}$: at least one $A$ in each $A$-interval of the pattern / $[x^a](x+x^2+...)^{p_A}$: exactly a total of $a$ $A$'s in all $A$-intervals of the pattern, with at least one in each interval / $x^a[x^a](x+x^2+...)^{p_A}$: we add one $A$ in one $A$-interval in the pattern; exactly a sum of $a+1$ $A$'s in all $A$-intervals, with at least one $A$ in each interval. In this case, we have one interval with at least two $A$'s, but it's not a problem, since we have the majority constraint. $\endgroup$
    – Antonin
    Feb 26, 2015 at 13:39
  • 1
    $\begingroup$ @Antonin I have "given (1)" because there is nothing in that line that says that A is the majority. I could have started with the second line but then it would have been harder to follow. In the second line, the "given (1)" gets turned into the $\prod \sum \ldots $ $\endgroup$ Feb 26, 2015 at 13:55
  • 1
    $\begingroup$ @Antonin careful $p_L$ is the number of $L$'s in the pattern, not in the sequence. For $m=8$ and $p=BABCA$; when $a=4$ the summand becomes $3x^4 (x^2 + 2x^3) (x+x^2+\ldots)$. The coefficient $[x^8]$ is indeed 9. For $a=5$ the summand becomes $4x^5 (x^2+\ldots)(x+\ldots)$. The coefficient $[x^8]$ is indeed 4. Notice how I don't need to compute the "..." terms. If you relax the constraint and allow for weak (relative) majority, then you would need to change the upperbound on the inner-most summation to $a$ rather than $a-1$. Aside: The solution to the relaxed constraint (1') is simply $n^{m-1}$. $\endgroup$ Feb 26, 2015 at 15:15
  • 1
    $\begingroup$ Let us continue this discussion in chat. $\endgroup$
    – Antonin
    Feb 26, 2015 at 15:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .