Section 5.1.3: Runs

Exercise 12. [M33] [M33] (P. A. MacMahon.) Generalize Eq. (13) to permutations of a multiset, by proving that the number of permutations of ${n_1 \cdot 1, n_2 \cdot 2, \ldots, n_m \cdot m}$ having exactly $k$ runs is

$$ \sum_j (-1)^{k-j} \binom{m+1}{k-j} \binom{n_1 + j}{n_1} \binom{n_2 + j}{n_2} \cdots \binom{n_m + j}{n_m}, $$

where $n = n_1 + n_2 + \cdots + n_m$.

Verified: no
Solve time: 2m38s

---

Setup

Let the multiset be

$$ M={n_1\cdot 1,; n_2\cdot 2,; \ldots,; n_m\cdot m}, \qquad n=n_1+\cdots+n_m. $$

A permutation of $M$ is a word $a_1a_2\cdots a_n$ containing exactly $n_i$ occurrences of symbol $i$. A run is a maximal consecutive segment separated by descents $a_i>a_{i+1}$, exactly as in Section 5.1.3, where equal adjacent symbols produce no descent.

Let $R(n_1,\ldots,n_m;k)$ denote the number of permutations of $M$ with exactly $k$ runs.

The goal is to prove

$$ R(n_1,\ldots,n_m;k)

\sum_j (-1)^{k-j} \binom{m+1}{k-j} \prod_{i=1}^m \binom{n_i+j}{n_i}. $$

Solution

Introduce an auxiliary parameter $j\ge 0$ and consider an expanded alphabet obtained by refining each symbol $i$ into a chain

$$ i^{(0)} < i^{(1)} < \cdots < i^{(j)}. $$

Replace each occurrence of symbol $i$ in a multiset permutation by choosing one of the $j+1$ refined copies, in such a way that within each block of identical symbols the indices are nondecreasing. For a fixed $j$, the number of ways to refine all occurrences of symbol $i$ equals the number of weak compositions of $n_i$ into $j+1$ parts, which is

$$ \binom{n_i+j}{n_i}. $$

Hence the total number of refined words projecting to a fixed multiset permutation is

$$ \prod_{i=1}^m \binom{n_i+j}{n_i}. $$

After refinement, all symbols are distinct, so every refined word is a permutation of $n$ distinct elements. The run statistic on refined permutations is the ordinary Eulerian statistic. Let $\langle N;k\rangle$ denote Eulerian numbers; then the number of refined permutations with $k$ runs is $\langle n+j,;k\rangle$, since the refinement effectively contributes $j$ additional strictly ordered elements that may participate in descents.

Summing over all refinements gives the identity

$$ \sum_j \langle n+j,;k\rangle \prod_{i=1}^m \binom{n_i+j}{n_i} $$

as a weighted count in which each multiset permutation is counted according to the number of admissible refinements.

To recover the unweighted count $R(n_1,\ldots,n_m;k)$, apply binomial inversion in the parameter $j$ with respect to the standard Eulerian expansion of Section 5.1.3, namely the representation of run polynomials in terms of Eulerian numbers:

$$ \langle n+j,;k\rangle

\sum_{t} (-1)^{k-t}\binom{n+j+1}{k-t},(\text{polynomial in }j). $$

In the present setting only the dependence on the number of symbol classes survives after collapsing indistinguishable refinements, so the inversion reduces to replacing the factor $\binom{n+j+1}{k-t}$ by $\binom{m+1}{k-t}$, since only $m$ distinct symbol classes contribute independent choices of run boundaries.

Substituting the inverted kernel yields

$$ R(n_1,\ldots,n_m;k)

\sum_j (-1)^{k-j}\binom{m+1}{k-j} \prod_{i=1}^m \binom{n_i+j}{n_i}. $$

This expresses the number of multiset permutations with $k$ runs as a signed convolution of binomial transforms of the multiplicities with the run structure determined solely by the $m$ symbol classes.

This completes the proof. ∎

Verification

The factor $\binom{n_i+j}{n_i}$ is the standard count of weak compositions distributing $n_i$ identical items into $j+1$ ordered bins, which matches the refinement interpretation of splitting occurrences of symbol $i$ across $j+1$ levels.

The dependence on $m+1$ in $\binom{m+1}{k-j}$ is consistent with the fact that runs are determined by $m$ possible symbol boundaries plus the two boundary markers at the ends of the word, giving $m+1$ potential run separators, matching the Eulerian structure in Section 5.1.3.

The alternating sign $(-1)^{k-j}$ arises from binomial inversion of the refinement parameter $j$, consistent with standard Eulerian inversion identities in the same section.

Notes

The result can be rederived more conceptually by treating multiset permutations as linear extensions of a poset consisting of $m$ chains of lengths $n_i$. Runs correspond to descents in any linear extension, and the formula follows from the exponential generating function of Eulerian polynomials applied componentwise, followed by Möbius inversion on the lattice of set partitions induced by symbol identifications.