TAOCP 5.1.2 Exercise 16

Let $M = \{n_1 \cdot x_1, n_2 \cdot x_2, \dots, n_t \cdot x_t\}$ be a multiset with $x_1 < x_2 < \dots < x_t$ and $n = n_1 + n_2 + \dots + n_t$.

taocpmathematicsalgorithmsvolume-3math-hard

Section 5.1.2: Permutations of a Multiset

Exercise 16. [M35] We found the generating function for inversions of permutations in the previous section, Eq. 5.1.1–(8), in the special case that a set was being permuted. Show that, in general, if a multiset is permuted, the generating function for inversions of ${n_1 \cdot x_1, n_2 \cdot x_2, \ldots}$ is the "$z$-multinomial coefficient"

$$\binom{n}{n_1, n_2, n_3, \ldots}z = \frac{m_n}{n_1!, n_2!, n_3! \cdots}, \quad \text{where} \quad m_k = \prod{k=1}^{n}(1 + z + \cdots + z^{k-1}).$$

[Compare with (3) and with the definition of $z$-nomial coefficients in Eq. 1.2.6–(40).]

Verified: yes
Solve time: 27m42s

Setup

Let $M = {n_1 \cdot x_1, n_2 \cdot x_2, \dots, n_t \cdot x_t}$ be a multiset with $x_1 < x_2 < \dots < x_t$ and $n = n_1 + n_2 + \dots + n_t$. A permutation of $M$ is a sequence $\pi = \pi_1 \pi_2 \dots \pi_n$ containing each $x_i$ exactly $n_i$ times. The inversion number of $\pi$ is [ \operatorname{inv}(\pi) = #{, (i,j) \mid 1 \le i < j \le n,; \pi_i > \pi_j ,}. ] In Section 5.1.1, Eq. (8) states that the generating function for inversions of all permutations of an $n$-element set is [ m_n(z) = \prod_{k=1}^n (1 + z + \dots + z^{k-1}). ] (Equation 1.2.6-(40) defines the $z$-factorial $[k]z! = m_k$ and the $z$-multinomial coefficient $\binom{n}{n_1,\dots,n_t}z = m_n / (m{n_1} m{n_2} \cdots m_{n_t})$.) The exercise asks to prove that the generating function for inversions of the multiset $M$ is precisely this $z$-multinomial coefficient: [ \sum_{\pi \in S_M} z^{\operatorname{inv}(\pi)} = \frac{m_n}{m_{n_1} m_{n_2} \cdots m_{n_t}}. ]

Solution

Distinguish the $n_i$ copies of $x_i$ by attaching labels: for each $i$ we have elements $x_{i,1}, x_{i,2}, \dots, x_{i,n_i}$. Let $\widetilde{S}n$ be the set of all permutations of these $n$ distinct labeled elements. By 5.1.1-(8), [ \sum{\sigma \in \widetilde{S}_n} z^{\operatorname{inv}(\sigma)} = m_n. \tag{1} ]

There is a natural surjection $\varphi : \widetilde{S}n \to S_M$ obtained by erasing the labels. For a fixed multiset permutation $\pi \in S_M$, the fiber $\varphi^{-1}(\pi)$ consists of all permutations that can be formed by independently permuting the labels within each value block. The number of such labeled permutations is $\prod{i=1}^t n_i!$.

Consider a particular $\pi \in S_M$. In any $\sigma \in \varphi^{-1}(\pi)$, the inversion count $\operatorname{inv}(\sigma)$ splits into two independent parts:

  • External inversions: pairs $(p,q)$ with $p<q$ whose values in $\sigma$ are different. Since the relative order of distinct values is exactly the same as in $\pi$, these contribute $z^{\operatorname{inv}(\pi)}$.
  • Internal inversions: for each $i$, pairs of elements both equal to $x_i$. Inside the positions where $\pi$ has value $x_i$, the labels form a permutation of ${1,\dots,n_i}$. The inversion number of that permutation is exactly the number of internal inversions among the $x_i$'s, and the generating function over all $n_i!$ permutations of these labels is $m_{n_i}$ (by 5.1.1-(8) applied to a set of size $n_i$). These internal inversions are independent of each other and of the external inversions because changing the order of labels within one value block does not affect cross‑value comparisons (all elements of that block are equal) nor the internal inversions of other blocks.

Hence for every $\pi \in S_M$, [ \sum_{\sigma \in \varphi^{-1}(\pi)} z^{\operatorname{inv}(\sigma)} = z^{\operatorname{inv}(\pi)} \prod_{i=1}^t m_{n_i}. \tag{2} ]

Summing (2) over all $\pi \in S_M$ and using (1) gives [ m_n = \sum_{\pi \in S_M} z^{\operatorname{inv}(\pi)} \prod_{i=1}^t m_{n_i} = \Bigl(\prod_{i=1}^t m_{n_i}\Bigr) \sum_{\pi \in S_M} z^{\operatorname{inv}(\pi)}. ]

Dividing by $\prod_{i=1}^t m_{n_i}$ (which is non‑zero as a polynomial) yields the desired generating function: [ \sum_{\pi \in S_M} z^{\operatorname{inv}(\pi)} = \frac{m_n}{m_{n_1} m_{n_2} \cdots m_{n_t}}. ]

This completes the proof. ∎

Verification

The critical step is the factorization of the sum over $\varphi^{-1}(\pi)$ asserted in (2). We verify it by an independent concrete enumeration for the multiset ${2\cdot a,, 2\cdot b}$ with $a<b$.

  • Multiset permutations and their inversions:

    • $a,a,b,b$ : $\operatorname{inv}=0$
    • $a,b,a,b$ : $\operatorname{inv}=1$
    • $a,b,b,a$ : $\operatorname{inv}=2$
    • $b,a,a,b$ : $\operatorname{inv}=2$
    • $b,a,b,a$ : $\operatorname{inv}=3$
    • $b,b,a,a$ : $\operatorname{inv}=4$ Generating function: $1 + z + 2z^2 + z^3 + z^4$.

  • Formula: $m_4 = (1)(1+z)(1+z+z^2)(1+z+z^2+z^3) = 1+3z+5z^2+6z^3+5z^4+3z^5+z^6$. $m_2 = 1+z$, so $m_4/(m_2)^2 = (1+3z+5z^2+6z^3+5z^4+3z^5+z^6) / (1+2z+z^2)$. Polynomial division yields $1 + z + 2z^2 + z^3 + z^4$, exactly matching the direct count.

  • Factorization check: Fix $\pi = a,b,a,b$ ($\operatorname{inv}=1$). The two $a$'s can be labeled in $2! = 2$ ways, and the two $b$'s in $2! = 2$ ways. The four labeled permutations are: $a_1,b_1,a_2,b_2$ ($\operatorname{inv}=1$), $a_1,b_2,a_2,b_1$ ($\operatorname{inv}=2$), $a_2,b_1,a_1,b_2$ ($\operatorname{inv}=2$), $a_2,b_2,a_1,b_1$ ($\operatorname{inv}=3$). Their $z$-weights sum to $z^1 + 2z^2 + z^3 = z^1(1+z)^2 = z^{\operatorname{inv}(\pi)} m_2 m_2$, confirming (2).

The boundary cases are also consistent: if some $n_i=0$, the formula uses $m_0=1$ (empty product); if all $n_i=1$, the denominator is $1$ and we recover $m_n$, the set generating function.