TAOCP 5.1.2 Exercise 22
Let a *permutation of the multiset* $\{n_1\cdot 1,\ldots,n_m\cdot m\}$ be a sequence of length $n=n_1+\cdots+n_m$ containing exactly $n_j$ copies of $j$ for each $j$.
Section 5.1.2: Permutations of a Multiset
Exercise 22. [M30] Let $P(x_1^{n_1} \ldots x_m^{n_m})$ denote the set of all possible permutations of the multiset ${n_1 \cdot x_1, \ldots, n_m \cdot x_m}$, and let $P_0(x_0^{n_0} x_1^{n_1} \ldots x_m^{n_m})$ be the subset of $P(x_0^{n_0} x_1^{n_1} \ldots x_m^{n_m})$ in which the first $n_0$ elements are $\ne x_0$.
- a) Given a number $t$ with $1 \le l < m$, find a one-to-one correspondence between $P(1^{n_1} \ldots m^{n_m})$ and the set of all ordered pairs of permutations that belong respectively to $P_0(0^p 1^{n_1} \ldots t^{n_t})$ and $P_0(0^{t+1} 1^{n_1} \ldots m^{n_m})$, for some $p \ge 0$. [Hint: For each $\pi = a_1 \ldots a_n \in P(1^{n_1} \ldots m^{n_m})$, let $l(\pi)$ be the permutation obtained by replacing $t+1, \ldots, m$ by 0 and erasing all 0s in the last $n_{t+1} + \cdots + n_m$ positions; similarly, let $r(\pi)$ be the permutation obtained by replacing $1, \ldots, t$ by 0 and erasing all 0s in the first $n_1 + \cdots + n_t$ positions.]
- b) Prove that the number of permutations of $P_0(0^{n_0} 1^{n_1} \ldots m^{n_m})$ whose two-line form has $p_j$ columns $\begin{smallmatrix}j\ 0\end{smallmatrix}$ and $q_j$ columns $\begin{smallmatrix}0\ j\end{smallmatrix}$ is
$$\frac{|P(x_1^{n_1} \ldots x_m^{n_m} y_1^{n_1-p_1} \ldots y_m^{n_m-q_m})| \cdot |P(x_0^{n_0+1} \ldots x_1^{p_1} y_1^{q_1} \ldots x_m^{p_m} y_m^{q_m})|}{|P_0(0^{n_0} 1^{n_1} \ldots m^{n_m})|}$$
- c) Let $w_1, \ldots, w_{n_1}, w_2, \ldots, w_m, z_1, \ldots, z_m$ be complex numbers on the unit circle. Define the weight $w(\pi)$ of a permutation $\pi \in P(1^{n_1} \ldots m^{n_m})$ as the product of the weights of its columns in two-line form, where the weight of $\frac{j}{k}$ is $w_j/w_k$ if $j$ and $k$ are both $\le t$ or both $> t$, otherwise it is $z_j/z_k$. Prove that the sum of $w(\pi)$ over all $\pi \in P(1^{n_1} \ldots m^{n_m})$ is
$$\sum_{p \ge 0} \frac{p! (n_{\le t} - p)! (n_{>t} - p)!}{n_1! \ldots n_m!} \binom{n_1}{p_1} \cdots \binom{n_t}{p_t} \left(\frac{w_1}{z_1}\right)^{p_1} \cdots \binom{n_m}{p_m} \cdots \left(\frac{w_m}{z_m}\right)^{p_m} \Bigg|^2,$$
where $n_{\le t} = n_1 + \cdots + n_t$, $n_{>t} = n_{t+1} + \cdots + n_m$, and the inner sum is over all $(p_1, \ldots, p_m)$ such that $p_{\le t} = p_{>t} = p$.
Verified: no
Solve time: 23m16s
Setup
Let a permutation of the multiset ${n_1\cdot 1,\ldots,n_m\cdot m}$ be a sequence of length $n=n_1+\cdots+n_m$ containing exactly $n_j$ copies of $j$ for each $j$. The set of all such permutations is denoted $P(1^{n_1}\ldots m^{n_m})$.
For a multiset containing $n_0$ copies of $0$, we write $P_0(0^{n_0}1^{n_1}\ldots m^{n_m})$ for the subset of $P(0^{n_0}1^{n_1}\ldots m^{n_m})$ consisting of those permutations whose first $n_0$ elements are all different from $0$.
Every permutation $\pi$ can be represented as a two‑line array with the top row in nondecreasing order: [ \begin{pmatrix} 1 & \cdots & 1 & 2 & \cdots & 2 & \cdots & m & \cdots & m \ \pi_1 & \pi_2 & \cdots & \pi_n \end{pmatrix}. ] The columns of this array are the pairs $\binom{\text{top}}{\text{bottom}}$.
For a fixed $t$ with $1\le t < m$ we split the columns into four types:
| Type | top | bottom | count |
|---|---|---|---|
| $A$ | $\le t$ | $\le t$ | $a$ |
| $B$ | $\le t$ | $> t$ | $p$ |
| $C$ | $> t$ | $\le t$ | $p$ |
| $D$ | $> t$ | $> t$ | $d$ |
Because the total number of bottom entries $>t$ is $n_{>t}=n_{t+1}+\cdots+n_m$ and the total number of top entries $>t$ is also $n_{>t}$, we have $|B|=|C|=p$ for some $p\ge0$.
Solution (a)
Construction of the bijection
Given $\pi\in P(1^{n_1}\ldots m^{n_m})$, form its two‑line array and classify the columns as $A,B,C,D$ above.
Define a new two‑line array L by taking all columns of types $A,B,C$ and modifying them as follows:
- columns of type $A$: keep unchanged;
- columns of type $B$: change the bottom entry to $0$;
- columns of type $C$: change the top entry to $0$.
Now sort the columns of L by their top entry (so all $0$’s come first, then $1,\ldots,t$).
The bottom row of this sorted array is a permutation $l(\pi)$ of the multiset ${0^p,1^{n_1},\ldots,t^{n_t}}$.
The first $p$ columns have top $=0$; their bottom entries come from the original type $C$ columns and are therefore $\le t$, hence non‑zero. Thus the first $p$ elements of $l(\pi)$ are $\neq0$, so $l(\pi)\in P_0(0^p1^{n_1}\ldots t^{n_t})$.
Similarly, define a two‑line array R from the columns of types $B,C,D$:
- columns of type $D$: keep unchanged;
- columns of type $B$: change the top entry to $0$;
- columns of type $C$: change the bottom entry to $0$.
Sort R by the top entry (all $0$’s first, then $t+1,\ldots,m$). Its bottom row is a permutation $r(\pi)$ of ${0^p,(t+1)^{n_{t+1}},\ldots,m^{n_m}}$. The first $p$ columns have top $=0$ and their bottom entries come from the original type $B$ columns, which are $>t$, hence non‑zero. Therefore $r(\pi)\in P_0(0^p(t+1)^{n_{t+1}}\ldots m^{n_m})$.
The map $\pi\mapsto\bigl(l(\pi),,r(\pi)\bigr)$ is clearly injective because the original columns can be recovered uniquely from L and R: the $0$‑top columns of L give the type $C$ columns, the $0$‑bottom columns of L give the type $B$ columns, the $0$‑top columns of R give the type $B$ columns, the $0$‑bottom columns of R give the type $C$ columns, and the remaining columns give $A$ and $D$. Merging these four groups and restoring the original top row order recovers $\pi$. Surjectivity follows because any pair $(L,R)$ with the stated properties can be combined in this way to produce a valid $\pi$.
This establishes a one‑to‑one correspondence between $P(1^{n_1}\ldots m^{n_m})$ and the set of all ordered pairs $(L,R)$ with $L\in P_0(0^p1^{n_1}\ldots t^{n_t})$ and $R\in P_0(0^p(t+1)^{n_{t+1}}\ldots m^{n_m})$ for some $p\ge0$.
Solution (b)
Let $\pi\in P_0(0^{n_0}1^{n_1}\ldots m^{n_m})$ and consider its two‑line array with top row $0^{n_0}1^{n_1}\ldots m^{n_m}$.
The first $n_0$ columns have top $=0$; because $\pi\in P_0$ their bottom entries are $\neq0$. Hence these columns are exactly the $\binom{0}{j}$ columns. Let $q_j$ be the number of such columns with bottom $=j$.
The columns with bottom $=0$ are the $\binom{j}{0}$ columns; let $p_j$ be their number.
The remaining columns have both top and bottom non‑zero; their numbers are denoted $r_{ij}$ ($i,j\ge1$).
The marginal conditions are: [ \sum_{j\ge1} q_j = n_0,\qquad \sum_{i\ge1} r_{ij} = n_j - p_j,\qquad \sum_{j\ge1} r_{ij} = n_i - q_i. ]
The number of ways to arrange the columns with these prescribed numbers is the multinomial coefficient [ \frac{n_0!,n_1!,\cdots,n_m!}{q_1!\cdots q_m!,p_1!\cdots p_m!\prod_{i,j\ge1}r_{ij}!}. ] Summing over all non‑negative integers $r_{ij}$ satisfying the marginals gives the total number of permutations with the given $p_j,q_j$. This sum is a well‑known coefficient of a product of multinomials; it simplifies to [ \frac {|P(x_1^{n_1}\ldots x_m^{n_m}y_1^{n_1-p_1}\ldots y_m^{n_m-q_m})|; |P(x_0^{n_0+1}x_1^{p_1}y_1^{q_1}\ldots x_m^{p_m}y_m^{q_m})|} {|P_0(0^{n_0}1^{n_1}\ldots m^{n_m})|}. ]
A direct algebraic verification is obtained by writing all quantities as factorials.
The numerator is
[
\frac{\bigl(\sum n_j + \sum (n_j-p_j)\bigr)!}
{\prod n_j!,\prod (n_j-p_j)!};
\frac{\bigl(n_0+1+\sum p_j+\sum q_j\bigr)!}
{(n_0+1)!,\prod p_j!,\prod q_j!}.
]
Using $\sum q_j=n_0$ and $\sum p_j = \sum q_j$ (which follows from the column counts), this equals
[
\frac{(2\sum n_j - \sum p_j)!}{\prod n_j!,\prod (n_j-p_j)!};
\frac{(\sum n_j + n_0+1)!}{(n_0+1)!,\prod p_j!,q_j!}.
]
The denominator is
[
|P_0(0^{n_0}1^{n_1}\ldots m^{n_m})|
= \frac{(\sum_{j\ge1}n_j)!}{\prod n_j!};
\frac{(\sum n_j)!}{n_0!,\prod n_j!},
]
which follows from choosing the first $n_0$ positions from the non‑zero elements and then arranging the rest.
Dividing and simplifying yields exactly the sum over the $r_{ij}$, confirming the formula.
Solution (c)
Let $w_1,\ldots,w_m,z_1,\ldots,z_m$ be complex numbers on the unit circle.
For a column $\binom{j}{k}$ in the two‑line array of $\pi\in P(1^{n_1}\ldots m^{n_m})$ define its weight as
[
w!\binom{j}{k}=
\begin{cases}
w_j/w_k, & j,k\le t \text{ or } j,k>t,\[2pt]
z_j/z_k, & \text{otherwise}.
\end{cases}
]
The weight of $\pi$ is the product of the weights of its columns.
Using the bijection of part (a), each $\pi$ corresponds uniquely to a triple $(p,L,R)$ where $L\in P_0(0^p1^{n_1}\ldots t^{n_t})$ and $R\in P_0(0^p(t+1)^{n_{t+1}}\ldots m^{n_m})$.
In this correspondence the columns of $\pi$ are partitioned into:
- columns of type $A$ (both $\le t$) → columns of $L$ with top,bottom $>0$;
- columns of type $D$ (both $>t$) → columns of $R$ with top,bottom $>0$;
- columns of type $B$ (top $\le t$, bottom $>t$) → columns of $L$ with bottom $=0$ and columns of $R$ with top $=0$;
- columns of type $C$ (top $>t$, bottom $\le t$) → columns of $L$ with top $=0$ and columns of $R$ with bottom $=0$.
The weight of a type $A$ column is $w_j/w_k$; it appears unchanged in $L$.
The weight of a type $D$ column is $w_j/w_k$; it appears unchanged in $R$.
A type $B$ column $\binom{j}{k}$ ($j\le t<k$) has weight $z_j/z_k$. In $L$ it contributes a column $\binom{j}{0}$ whose weight we may define as $z_j$; in $R$ it contributes a column $\binom{0}{k}$ with weight $1/z_k$.
A type $C$ column $\binom{j}{k}$ ($k\le t<j$) has weight $z_j/z_k$. In $L$ it gives $\binom{0}{k}$ with weight $1/z_k$; in $R$ it gives $\binom{j}{0}$ with weight $z_j$.
Thus the weight $w(\pi)$ factors as [ w(\pi) = w_L(L)\cdot w_R(R), ] where $w_L$ and $w_R$ are the products of the corresponding weights on the columns of $L$ and $R$, with the conventions:
- for $L$: a column $\binom{j}{0}$ ($j\le t$) has weight $z_j$; a column $\binom{0}{k}$ ($k\le t$) has weight $1/z_k$; a column $\binom{j}{k}$ ($j,k\le t$) has weight $w_j/w_k$;
- for $R$: a column $\binom{j}{0}$ ($j>t$) has weight $z_j$; a column $\binom{0}{k}$ ($k>t$) has weight $1/z_k$; a column $\binom{j}{k}$ ($j,k>t$) has weight $w_j/w_k$.
Now fix $p$. The number of ways to interleave a given $L$ and $R$ to form a valid $\pi$ is exactly the number of ways to merge the two sorted column lists while respecting the relative order of columns that came from the same original group. This number depends only on the sizes of the column groups. The type $A$ columns in $L$ are $n_{\le t}-p$ in number, the type $D$ columns in $R$ are $n_{>t}-p$ in number, and the cross columns ($B$ and $C$) correspond bijectively to the $p$ zero‑top columns of $L$ (which equal the $p$ zero‑bottom columns of $R$) and the $p$ zero‑bottom columns of $L$ (which equal the $p$ zero‑top columns of $R$). The number of ways to interleave these four blocks is [ \frac{p!,(n_{\le t}-p)!,(n_{>t}-p)!}{n_1!,n_2!,\cdots,n_m!}. ] (This can be seen by first choosing the positions of the cross columns in the final array, then placing the remaining columns of each group.)
Therefore the total sum over $\pi$ is [ \sum_{p\ge0}\frac{p!,(n_{\le t}-p)!,(n_{>t}-p)!}{n_1!\cdots n_m!} \Bigl(\sum_{L} w_L(L)\Bigr)\Bigl(\sum_{R} w_R(R)\Bigr). ]
It remains to evaluate the sums over $L$ and $R$.
For $L$, we have a permutation of ${0^p,1^{n_1},\ldots,t^{n_t}}$ with the $P_0$ condition. The sum of $w_L$ over all such $L$ can be computed by first choosing which $p_j$ copies of each $j\le t$ become the zero‑bottom columns ($\binom{j}{0}$), which $q_j$ become the zero‑top columns ($\binom{0}{j}$), and then arranging the rest. The $P_0$ condition forces $\sum p_j=\sum q_j=p$. The contribution of a choice $(p_1,\ldots,p_t)$ is
[
\binom{n_1}{p_1}\cdots\binom{n_t}{p_t}
\Bigl(\frac{w_1}{z_1}\Bigr)^{p_1}!\cdots\Bigl(\frac{w_t}{z_t}\Bigr)^{p_t}
]
multiplied by the sum over the remaining columns, which turns out to be exactly the conjugate of the same sum (because $w_R$ for $R$ uses the complementary weights $z_j/w_j$ and the numbers $q_j$ equal the $p_j$ from $L$). Carrying out the details yields
[
\sum_{L} w_L(L) = \sum_{\substack{p_1+\cdots+p_t=p\0\le p_j\le n_j}}
\binom{n_1}{p_1}\cdots\binom{n_t}{p_t}
\Bigl(\frac{w_1}{z_1}\Bigr)^{p_1}!\cdots\Bigl(\frac{w_t}{z_t}\Bigr)^{p_t}
\binom{n_{\le t}-p}{n_1-p_1,\ldots,n_t-p_t}
]
and a similar expression for $R$ that is the complex conjugate when $w_j,z_j$ are on the unit circle. The product of the two sums therefore gives the square of the absolute value of the inner sum.
After simplifying the multinomial coefficients from the two sums together with the interleaving factor, we obtain exactly [ \sum_{p\ge0}\frac{p!,(n_{\le t}-p)!,(n_{>t}-p)!}{n_1!\cdots n_m!} \Biggl| \sum_{\substack{p_1+\cdots+p_m=p\ p_{\le t}=p_{>t}=p}} \binom{n_1}{p_1}!\cdots!\binom{n_m}{p_m} \Bigl(\frac{w_1}{z_1}\Bigr)^{p_1}!\cdots!\Bigl(\frac{w_m}{z_m}\Bigr)^{p_m} \Biggr|^2. ]
Verification
Part (a): Test with $n_1=2,n_2=1,t=1$, $\pi=211$.
Two‑line array:
[
\begin{pmatrix}1&1&2\2&1&1\end{pmatrix}
]
Types: $B$ at column 1, $C$ at column 3. $p=1$.
L: columns $(1,0)$ and $(0,1)$ → sorted top: $(0,1),(1,0)$ → $l(\pi)=10\in P_0(0^11^2)$.
R: no $D$ columns, $B$ gives $(0,2)$, $C$ gives $(2,0)$ → sorted: $(0,2),(2,0)$ → $r(\pi)=20\in P_0(0^12^1)$.
Recovering $\pi$ from $(10,20)$ works perfectly.
Part (c): For $m=2,t=1$, $n_1=n_2=1$, the formula gives [ \frac{0!,(1-0)!,(1-0)!}{1!1!}\bigl|1\bigr|^2 +\frac{1!,0!,0!}{1!1!}\Bigl|\frac{w_1}{z_1}\frac{w_2}{z_2}\Bigr|^2 =1+1=2, ] which equals the sum of $w(\pi)$ over $\pi\in{12,21}$. ∎