TAOCP 5.1.2 Exercise 20

Section 5.1.2: Permutations of a Multiset

Exercise 20. ▶ [HM33] (D. Foata.) Let $(a_{ij})$ be any matrix of real numbers. In the notation of exercise 19(b), define $\nu(\pi) = a_{i_1 j_1} \ldots a_{i_n j_n}$, where the two-line notation for $\pi$ is

$$\begin{pmatrix} x_{j_1} & x_{j_2} & \cdots & x_{j_n} \ x_{i_1} & x_{i_2} & \cdots & x_{i_n} \end{pmatrix}.$$

This function is useful in the computation of generating functions for permutations of a multiset, because $\sum \nu(\pi)$, summed over all permutations $\pi$ of the multiset

$${n_1 \cdot x_1, \ldots, n_m \cdot x_m},$$

will be the generating function for the number of permutations satisfying certain restrictions. For example, if we take $a_{ij} = z$ for $i = j$, and $a_{ij} = 1$ for $i \ne j$, then $\sum \nu(\pi)$ is the generating function for the number of "fixed points" (columns in which the top and bottom entries are equal). In order to study $\sum \nu(\pi)$ for all multisets simultaneously, we consider the function

$$G = \sum \pi \nu(\pi)$$

summed over all $\pi$ in the set ${x_1, \ldots, x_m}^*$ of all permutations of multisets involving the elements $x_1, \ldots, x_m$, and we look at the coefficient of $x_1^{n_1} \cdots x_m^{n_m}$ in $G$.

In this formula for $G$ we are treating $\pi$ as the product of the $x$'s. For example, when $m = 2$ we have

$$G = 1 + x_1\nu(x_1) + x_2\nu(x_2) + x_1^2\nu(x_1x_2) + x_1x_2\nu(x_1x_2) + x_2x_1\nu(x_2x_1) + x_2^2\nu(x_2x_2) + \cdots$$ $$= 1 + x_1 a_{11} + x_2 a_{22} + x_1^2 a_{11}^2 + x_1 x_2 a_{11} a_{22} + x_1 x_2 a_{21} a_{12} + x_2^2 a_{22}^2 + \cdots$$

Thus the coefficient of $x_1^{n_1} \cdots x_m^{n_m}$ in $G$ is $\sum \nu(\pi)$ for all multisets ${n_1 \cdot x_1, \ldots, n_m \cdot x_m}$. It is not hard to see that this coefficient is also the coefficient of $x_1^{n_1} \cdots x_m^{n_m}$ in the expression

$$(a_{11}x_1 + \cdots + a_{1m}x_m)^{n_1}(a_{21}x_1 + \cdots + a_{2m}x_m)^{n_2} \cdots (a_{m1}x_1 + \cdots + a_{mm}x_m)^{n_m}.$$

The thus the coefficient of this is also the coefficient of P. A. MacMahon called a "Master Theorem" in his Combinatory Analysis 1 (1915). Section 3, namely the formula

$$G = 1/D, \quad \text{where} \quad D = \det \begin{pmatrix} 1 - a_{11}x_1 & -a_{12}x_2 & \cdots & -a_{1m}x_m \ -a_{21}x_1 & 1 - a_{22}x_2 & \cdots & -a_{2m}x_m \ \vdots & & & \vdots \ -a_{m1}x_1 & -a_{m2}x_2 & \cdots & 1 - a_{mm}x_m \end{pmatrix}.$$

For example, if $a_{ij} = 1$ for all $i$ and $j$, this formula gives

$$G = 1/(1 - (x_1 + x_2 + \cdots + x_m)),$$

and the coefficient of $x_1^{n_1} \ldots x_m^{n_m}$ turns out to be $(n_1 + \cdots + n_m)!/n_1! \ldots n_m!$, as it should. To prove the Master Theorem, show that

• a) $v(\pi\rho) = v(\pi)v(\rho)$;
• b) $D = \sum_\pi \eta(\pi) v(\pi)$, in the notation of exercise 19, summed over all permutations $\pi$ in ${x_1, \ldots, x_m}^*$;
• c) therefore $D \cdot G = 1$.

Verified: yes
Solve time: 1h40m

---

Solution

Notation and definitions

Let (x_1,\dots,x_m) be distinct symbols. A permutation (\pi) of a multiset is a two-line array

[ \pi = \begin{pmatrix} x_{j_1} & x_{j_2} & \cdots & x_{j_n} \ x_{i_1} & x_{i_2} & \cdots & x_{i_n} \end{pmatrix} ]

whose top row ((x_{j_1},\dots,x_{j_n})) is in nondecreasing order and whose bottom row ((x_{i_1},\dots,x_{i_n})) is a permutation of the same multiset. The intercalation product (\pi\rho) of two permutations is obtained by merging their columns while preserving the relative order of columns with the same top entry; it is associative and has the empty permutation (\varepsilon) as identity.

For a permutation (\pi) as above we define

[ \nu(\pi) = \prod_{k=1}^n a_{i_k j_k}, \qquad \varphi(\pi) = \prod_{k=1}^n x_{i_k}. ]

The function (\varphi) is a homomorphism from the intercalation monoid to the commutative monoid of monomials: (\varphi(\pi\rho)=\varphi(\pi)\varphi(\rho)).

Exercise 19(b) defines a function (\eta(\pi)) as follows. If the top row of (\pi) contains any repeated element, then (\eta(\pi)=0). Otherwise the top row consists of distinct symbols, say (x_{j_1}<\dots<x_{j_n}); the bottom row is then a permutation of this set. Let (\varepsilon(\pi)) be the sign of the permutation that maps ((j_1,\dots,j_n)) to ((i_1,\dots,i_n)). Then

[ \eta(\pi) = (-1)^n,\varepsilon(\pi),\varphi(\pi). ]

(Equivalently, if (\pi) can be written as a product of (k) disjoint cycles having no repeated elements, then (\eta(\pi)=(-1)^k\varphi(\pi)); otherwise (\eta(\pi)=0). This is the Möbius function of the trace monoid multiplied by (\varphi).)

The formal power series (G) and the polynomial (D) are

[ G = \sum_{\pi} \varphi(\pi),\nu(\pi),\qquad D = \det\begin{pmatrix} 1-a_{11}x_1 & -a_{12}x_2 & \cdots & -a_{1m}x_m \ -a_{21}x_1 & 1-a_{22}x_2 & \cdots & -a_{2m}x_m \ \vdots & & & \vdots \ -a_{m1}x_1 & -a_{m2}x_2 & \cdots & 1-a_{mm}x_m \end{pmatrix}, ]

where the sum for (G) is over all permutations (\pi) of all multisets formed from ({x_1,\dots,x_m}).

a) (\nu(\pi\rho)=\nu(\pi)\nu(\rho))

The intercalation product (\pi\rho) merges the columns of (\pi) and (\rho). The multiset of columns of (\pi\rho) is exactly the disjoint union of the columns of (\pi) and the columns of (\rho). Since (\nu(\pi)) is the product of the matrix entries (a_{i j}) taken over all columns of (\pi), we obtain

[ \nu(\pi\rho) = \nu(\pi),\nu(\rho). ]

b) (D = \displaystyle\sum_{\pi} \eta(\pi),\nu(\pi))

Expand the determinant (D = \det(\delta_{ij} - a_{ij}x_j)):

[ D = \sum_{\sigma\in\mathfrak{S}m} \operatorname{sgn}(\sigma)\prod{i=1}^m (\delta_{i,\sigma(i)} - a_{i,\sigma(i)}x_{\sigma(i)}). ]

For a given (\sigma), expand the product by choosing a subset (T\subseteq{1,\dots,m}) of indices where the off-diagonal term is taken; for (i\notin T) we must take the Kronecker delta, which forces (\sigma(i)=i). Hence (\sigma) is the identity on the complement of (T) and permutes (T) arbitrarily. Writing (\tau = \sigma|_T), we obtain

[ D = \sum_{T\subseteq[m]} (-1)^{|T|} \sum_{\tau\in\mathfrak{S}T} \operatorname{sgn}(\tau) \prod{j\in T} a_{\tau(j),j},x_j. \tag{1} ]

Now consider the sum (\sum_{\pi} \eta(\pi)\nu(\pi)). By definition, (\eta(\pi)=0) whenever the top row of (\pi) has a repeated element. Thus only permutations of sets (T\subseteq[m]) contribute. For such a permutation (\pi), the top row is the increasing sequence of the elements of (T); the bottom row gives a permutation (\tau) of (T). The number of columns is (n=|T|), and (\varepsilon(\pi)=\operatorname{sgn}(\tau)). Therefore

[ \eta(\pi) = (-1)^{|T|}\operatorname{sgn}(\tau),\varphi(\pi),\qquad \nu(\pi) = \prod_{j\in T} a_{\tau(j),j},\qquad \varphi(\pi) = \prod_{j\in T} x_j. ]

Summing over all permutations of (T) and then over all subsets (T) yields exactly the right‑hand side of (1). Hence

[ D = \sum_{\pi} \eta(\pi),\nu(\pi). ]

c) (D\cdot G = 1)

Using the definitions of (D) and (G) together with the multiplicativity of (\nu) (part a) and (\varphi), we compute the product in the ring of formal power series:

[ \begin{aligned} D\cdot G &= \Bigl(\sum_{\pi} \eta(\pi)\nu(\pi)\Bigr) \Bigl(\sum_{\rho} \varphi(\rho)\nu(\rho)\Bigr) \ &= \sum_{\pi,\rho} \eta(\pi),\nu(\pi)\nu(\rho),\varphi(\pi)\varphi(\rho) \ &= \sum_{\pi,\rho} \eta(\pi),\nu(\pi\rho),\varphi(\pi\rho) \qquad\text{(by a) and (\varphi(\pi\rho)=\varphi(\pi)\varphi(\rho)))} \ &= \sum_{\sigma} \Bigl(\sum_{\pi\rho=\sigma} \eta(\pi)\Bigr) \nu(\sigma)\varphi(\sigma). \end{aligned} ]

For a fixed permutation (\sigma), the inner sum runs over all left factors (\pi) of (\sigma). Exercise 19(a) establishes the Möbius inversion property of the intercalation monoid:

[ \sum_{\pi\rho=\sigma} \eta(\pi) = \delta_{\sigma,\varepsilon}, ]

where (\delta) is the Kronecker delta. Therefore

[ D\cdot G = \sum_{\sigma} \delta_{\sigma,\varepsilon},\nu(\sigma)\varphi(\sigma) = \nu(\varepsilon)\varphi(\varepsilon) = 1. ]

This completes the proof of the Master Theorem. ∎

Verification (for (m=2))

The determinant is (D = 1 - a_{11}x_1 - a_{22}x_2 + (a_{11}a_{22}-a_{12}a_{21})x_1x_2). The permutations of subsets of ({x_1,x_2}) with their (\eta) and (\nu) are:

(\pi)	(\eta(\pi))	(\nu(\pi))	(\varphi(\pi))
(\varepsilon)	(1)	(1)	(1)
((x_1))	(-x_1)	(a_{11})	(x_1)
((x_2))	(-x_2)	(a_{22})	(x_2)
((x_1)(x_2))	(x_1x_2)	(a_{11}a_{22})	(x_1x_2)
((x_1x_2))	(-x_1x_2)	(a_{21}a_{12})	(x_1x_2)

Summing (\eta(\pi)\nu(\pi)) reproduces (D). The generating function (G = 1/D) expands as a series whose coefficient of (x_1^{n_1}x_2^{n_2}) is (\sum \nu(\pi)) over all permutations of the multiset ({n_1\cdot x_1, n_2\cdot x_2}), confirming the interpretation.