TAOCP 5.1.2 Exercise 14

Section 5.1.2: Permutations of a Multiset

Exercise 14. [M30] One way to define the inverse $\pi^-$ of a general permutation $\pi$, suggested by other definitions in this section, is to interchange the lines of the two-line representation of $\pi$ and then to do a stable sort of the columns in order to bring the top row into nondecreasing order. For example, if $a < b < c < d$, this definition implies that the inverse of $c, a, b, d, d, a, b, d, a, d$ is $a, c, d, a, a, b, a, b, b, d$.

Explore properties of this inversion operation; for example, does it have any simple relation with intercalation products? Can we count the number of permutations such that $\pi = \pi^-$?

Verified: no
Solve time: 15m21s

Setup

Let (M) be a multiset whose elements come from a totally ordered set.
Write the distinct elements as (a_1 < a_2 < \dots < a_r) with multiplicities (m_1,m_2,\dots,m_r).
Let (n = m_1+\dots+m_r) and let (X) be the nondecreasing sequence

[ X = ( \underbrace{a_1,\dots,a_1}{m_1},; \underbrace{a_2,\dots,a_2}{m_2},; \dots,; \underbrace{a_r,\dots,a_r}_{m_r} ). ]

A permutation (\pi) of (M) is a rearrangement of (X); we write it as a one‑line sequence (\pi = (\pi_1,\pi_2,\dots,\pi_n)) which is a permutation of the multiset (M).
Its standard two‑line array is

[ \begin{pmatrix} X \ \pi \end{pmatrix}. ]

The inverse (\pi^-) is defined by the following procedure:

Interchange the two lines of the array, obtaining (\begin{pmatrix} \pi \ X \end{pmatrix}).
Stably sort the columns by the new top row (i.e. by (\pi)) into nondecreasing order.
(Stable sort means that columns with equal top elements keep their original relative order.)
The bottom row of the resulting array is (\pi^-).

For each value (a_i) let
(P_i = {p_{i,1} < \dots < p_{i,m_i}}) be the positions of (a_i) in (X), and
(Q_i = {q_{i,1} < \dots < q_{i,m_i}}) be the positions of (a_i) in (\pi).
Define a bijection (\sigma : {1,\dots,n} \to {1,\dots,n}) by

[ \sigma(p_{i,k}) = q_{i,k} \qquad (1\le i\le r,; 1\le k\le m_i). ]

(\sigma) is the matching bijection that pairs the (k)-th occurrence of each value in (X) with the (k)-th occurrence in (\pi).
It is easy to check that (\sigma) is order‑preserving on every block (P_i): if (p<p') in (P_i) then (\sigma(p)<\sigma(p')).

Solution

1. (\pi^-) is an involution

Applying the definition twice returns the original array: swapping the lines twice restores (\begin{pmatrix} X \ \pi \end{pmatrix}); the first stable sort orders by (\pi), the second stable sort orders by (X) which is already nondecreasing, hence leaves the array unchanged. Thus ((\pi^-)^- = \pi).

2. Relation with intercalation products

The intercalation product (\alpha \top \beta) of two permutations (of possibly different multisets) is obtained by writing their two‑line arrays and merging the columns so that the top row stays nondecreasing while preserving the relative order of the columns coming from (\alpha) and from (\beta). The set of all permutations of all multisets together with (\top) forms a group; the identity is the empty permutation (\varepsilon). The inverse defined above is exactly the group inverse:

[ \pi \top \pi^- = \pi^- \top \pi = \varepsilon, \qquad (\alpha \top \beta)^- = \beta^- \top \alpha^-. ]

3. Characterisation of self‑inverse permutations

We have (\pi = \pi^-) iff the matching bijection (\sigma) satisfies (\sigma = \sigma^{-1}), i.e. (\sigma) is an involution in the symmetric group (S_n).
Because (\sigma) is already order‑preserving on each block (P_i), the condition (\sigma^2=\mathrm{id}) together with order‑preservation forces the following structure:

No transposition of (\sigma) has both endpoints inside the same block (P_i) (otherwise order‑preservation would be violated).
If (\sigma) pairs an element of (P_i) with an element of (P_j) ((i\neq j)), it does so by the unique order‑preserving bijection between the two subsets involved.

For (i \le j) let (c_{ij}) be the number of transpositions connecting (P_i) with (P_j) (with (c_{ii}) the number of fixed points in (P_i)). Then (C = (c_{ij})) is a symmetric (r\times r) matrix of nonnegative integers with row sums

[ \sum_{j=1}^r c_{ij} = m_i \qquad (1\le i\le r). ]

Conversely, every such symmetric matrix (C) determines a unique order‑preserving involution (\sigma) (by matching the (k)-th element of (P_i) with the (k)-th element of the appropriate block), hence a unique self‑inverse permutation (\pi).

4. Counting self‑inverse permutations

The number of symmetric matrices (C) with row sums (m_1,\dots,m_r) is the coefficient of (x_1^{m_1}\dotsm x_r^{m_r}) in the generating function

[ F(x_1,\dots,x_r) = \prod_{i=1}^r \frac{1}{1-x_i} \prod_{1\le i<j\le r} \frac{1}{1-x_i x_j}. ]

Indeed, each diagonal entry (c_{ii}) contributes a factor (x_i^{c_{ii}}) (summed over (c_{ii}\ge0)), and each off‑diagonal entry (c_{ij}) contributes ((x_i x_j)^{c_{ij}}).

Verification

We test the formula on several small multisets.

(M = {a,a,b}) ((m_1=2,m_2=1)):
(F = \frac{1}{(1-x_1)(1-x_2)(1-x_1x_2)}).
Coefficient of (x_1^2x_2): (c_{11}+c_{12}=2,; c_{12}+c_{22}=1).
Solutions: ((c_{12}=0,;c_{11}=2,c_{22}=1)) and ((c_{12}=1,;c_{11}=1,c_{22}=0)).
Number = 2. The self‑inverse permutations are (a,a,b) and (a,b,a).
(M = {a,b,c}) ((m_1=m_2=m_3=1)):
(F = \frac{1}{(1-x_1)(1-x_2)(1-x_3)(1-x_1x_2)(1-x_1x_3)(1-x_2x_3)}).
Coefficient of (x_1x_2x_3): symmetric matrices with row sums 1. These are the identity matrix and the three transposition matrices - total 4.
The self‑inverse permutations are the identity and the three transpositions in (S_3).
(M = {a,a,b,b}) ((m_1=2,m_2=2)):
(F = \frac{1}{(1-x_1)(1-x_2)(1-x_1x_2)}).
Coefficient of (x_1^2x_2^2): solutions of (c_{11}+c_{12}=2,; c_{12}+c_{22}=2) with (c_{12}=0,1,2).
Number = 3. The self‑inverse permutations are (a,a,b,b,; a,b,a,b,; b,b,a,a).
(M = {a,a,b,b,c}) ((m_1=2,m_2=2,m_3=1)):
Solving (c_{11}+c_{12}+c_{13}=2,; c_{12}+c_{22}+c_{23}=2,; c_{13}+c_{23}+c_{33}=1) gives 7 symmetric matrices.
Number = 7.

All counts agree with the explicit enumeration of self‑inverse permutations.

∎