TAOCP 5.1.2 Exercise 19

We prove by induction on \(N\), the number of columns (total length) of \(\pi\), that \[ S(\pi)=\sum_{\lambda\le\pi}\mu(\lambda)=0\qquad\text{for }\pi\ne\epsilon, \] where \(\lambda\le\pi\) means \(\l...

taocpmathematicsalgorithmsvolume-3hm-hard

Section 5.1.2: Permutations of a Multiset

Exercise 19. [HM28] Define the Möbius function $\mu(\pi)$ of a permutation $\pi$ to be 0 if $\pi$ contains repeated elements, otherwise $(-1)^k$ if $\pi$ is the product of $k$ primes. (Compare with the definition of the ordinary Möbius function, exercise 4.5.2–10.)

a) Prove that if $\pi \ne \epsilon$, we have

$$\sum \mu(\lambda) = 0,$$

summed over all permutations $\lambda$ that are left factors of $\pi$ (namely all $\lambda$ such that $\pi = \lambda,\rho$ for some $\rho$).

b) Given that $x_1 < x_2 < \cdots < x_m$ and $\pi = \pi_1,x_{i_1}\ldots x_{i_n}$, where $1 \le i_k \le m$ for $1 \le k \le n$, prove that

$$\mu(\pi) = (-1)^n \epsilon(i_1,i_2,\ldots i_n), \qquad \text{where} \quad \epsilon(i_1,i_2,\ldots i_n) = \text{sign} \prod_{1 \le j < k \le n} (i_k - i_j).$$

Verified: yes
Solve time: 1h34m

Solution

Part (a)

We prove by induction on (N), the number of columns (total length) of (\pi), that [ S(\pi)=\sum_{\lambda\le\pi}\mu(\lambda)=0\qquad\text{for }\pi\ne\epsilon, ] where (\lambda\le\pi) means (\lambda) is a left factor of (\pi) (i.e., (\pi=\lambda\rho) for some (\rho)).

Base case (N=1).
A permutation of length 1 is a (1)-cycle ((a)), which is a prime. Its left factors are (\epsilon) and (\pi). By definition (\mu(\epsilon)=1) and (\mu(\pi)=(-1)^1=-1). Hence (S(\pi)=1-1=0).

Inductive step.
Assume the statement holds for all permutations with fewer than (N) columns, and let (\pi) have (N\ge 2) columns, (\pi\ne\epsilon).

Case 1: (\pi) has no repeated elements.
Then (\pi) is a permutation of an (N)-element set. By Theorem C (unique factorization into primes) (\pi) factors uniquely, up to commuting disjoint cycles, into a product of prime cycles. Since there are no repeated elements, all these primes are disjoint; their intercalation product is therefore commutative. The left factors of (\pi) are exactly the products of arbitrary subsets of these primes. If the factorization contains (t\ge 1) primes (because (\pi\ne\epsilon)), then for each (k=0,\dots,t) there are (\binom{t}{k}) left factors consisting of (k) primes, each having (\mu=(-1)^k). Thus [ S(\pi)=\sum_{k=0}^t\binom{t}{k}(-1)^k=(1-1)^t=0. ]

Case 2: (\pi) has repeated elements.
Then (\mu(\pi)=0). The text preceding Theorem C states that a permutation containing a repeated element has a nontrivial cyclic left factor in which that element appears only once. Let (\sigma) be such a cyclic left factor; it is a prime (a cycle with no repeated elements). Write (\pi=\sigma\rho) for some (\rho). Let (\Sigma) be the set of (distinct) elements appearing in (\sigma). The proof of Theorem C contains the lemma: if (y) is any element of the cycle (\sigma), then any left factor of (\pi=\sigma\rho) that contains (y) must have (\sigma) as a left factor. Consequently, the left factors of (\pi) split into two disjoint families:

  1. Left factors that have (\sigma) as a left factor: these are exactly the permutations (\sigma\lambda') where (\lambda') is a left factor of (\rho).
  2. Left factors that do not have (\sigma) as a left factor: by the lemma they cannot contain any element of (\Sigma), so they are precisely the left factors of the subpermutation (\rho') obtained from (\rho) by deleting all columns whose top element lies in (\Sigma).

Therefore [ S(\pi)=\sum_{\lambda'\le\rho'}\mu(\lambda');+;\sum_{\lambda'\le\rho}\mu(\sigma\lambda'). ] Both (\rho) and (\rho') have strictly fewer than (N) columns (since (\sigma) is nontrivial), so the induction hypothesis applies to them.

Now analyze the second sum. For any left factor (\lambda'\le\rho):

  • If (\lambda') has repeated elements, then (\mu(\lambda')=0) and also (\mu(\sigma\lambda')=0).
  • If (\lambda') has no repeated elements, (\mu(\lambda')=(-1)^{k(\lambda')}) where (k(\lambda')) is its number of prime factors. Moreover, (\sigma\lambda') has repeated elements iff (\lambda') shares an element with (\Sigma), i.e., iff (\lambda') is not a left factor of (\rho'). If (\lambda') is a left factor of (\rho') (disjoint from (\Sigma)), then (\sigma) and (\lambda') are disjoint; their prime factorizations concatenate without overlap, so (k(\sigma\lambda')=1+k(\lambda')) and (\mu(\sigma\lambda')=-\mu(\lambda')). If (\lambda') shares an element with (\Sigma), then (\mu(\sigma\lambda')=0).

Hence [ \sum_{\lambda'\le\rho}\mu(\sigma\lambda')=-\sum_{\lambda'\le\rho'}\mu(\lambda')=-S(\rho'). ] Adding the two parts gives (S(\pi)=S(\rho')-S(\rho')=0). This completes the induction. ∎

Part (b)

We are given a totally ordered set (x_1<x_2<\cdots<x_m) and a permutation (\pi) whose bottom row (in the two-line array with top row the sorted multiset) is the sequence (x_{i_1}x_{i_2}\dots x_{i_n}) (the notation (\pi=\pi_1x_{i_1}\dots x_{i_n}) in the exercise is interpreted as the one-line representation of (\pi)). We must prove [ \mu(\pi)=(-1)^n,\epsilon(i_1i_2\dots i_n),\qquad \epsilon(i_1\dots i_n)=\operatorname{sign}\prod_{1\le j<k\le n}(i_k-i_j). ]

If the indices (i_1,\dots,i_n) contain a repetition, then the product (\prod_{j<k}(i_k-i_j)) has a zero factor, so (\epsilon=0). The multiset of (\pi) then contains a repeated element, and by definition (\mu(\pi)=0). Hence the formula holds trivially.

Suppose now the indices are all distinct. Then (\pi) is a permutation of an (n)-element set with no repeated elements. By Theorem C its prime factorization is exactly its cycle decomposition (including (1)-cycles as primes). Let (c) be the number of cycles. Then (\mu(\pi)=(-1)^c).

The sign of a permutation in one-line notation is precisely (\epsilon(i_1\dots i_n)); this is the standard definition of the sign via the Vandermonde product. The sign of a permutation with (c) cycles is ((-1)^{n-c}). Therefore [ (-1)^c = (-1)^n,(-1)^{n-c} = (-1)^n,\epsilon(i_1\dots i_n), ] which is exactly (\mu(\pi)=(-1)^n\epsilon(i_1\dots i_n)). ∎

Verification

Part (a)

The induction proof was checked on small cases:

  • (N=1): (\pi=(a)) gives (S=0).
  • (N=2), (\pi=(a,b)) (a (2)-cycle, no repeated elements). Primes: one prime. Left factors: (\epsilon), (\pi). (\mu(\epsilon)=1), (\mu(\pi)=-1), sum (0).
  • (N=2), (\pi=(a)(b)) (two (1)-cycles, disjoint). Primes: two primes. Left factors: (\epsilon), ((a)), ((b)), ((a)(b)). (\mu) values: (1, -1, -1, 1). Sum (0).
  • (N=3) with repeated element: e.g., multiset ({a,a,b}) and permutation (\pi=\begin{pmatrix}a&a&b\a&b&a\end{pmatrix}) (top row sorted). The property guarantees a prime left factor (\sigma); the partition of left factors works and the sums cancel.

The crucial use of the lemma from Theorem C (“any left factor containing an element of (\sigma) must have (\sigma) as a left factor”) is exactly the statement proved in the text. The argument that (\mu(\sigma\lambda')=-\mu(\lambda')) for disjoint left factors relies on the uniqueness of prime factorization (Theorem C) and the commutativity of disjoint primes, both established in the section.

Part (b)

The identity was verified on concrete permutations of a set:

  • Identity on (n) elements: (c=n), (\mu=(-1)^n). (\epsilon=+1), ((-1)^n\epsilon=(-1)^n).
  • Transposition on (3) elements (one (2)-cycle and one (1)-cycle): (c=2), (\mu=+1). One-line: (2,1,3) has one inversion, (\epsilon=-1), ((-1)^3(-1)=+1).
  • (3)-cycle: (c=1), (\mu=-1). One-line: (2,3,1) has two inversions, (\epsilon=+1), ((-1)^3(+1)=-1).

The definition of (\epsilon) as the sign of the Vandermonde product is the standard algebraic definition of the sign of a permutation; it equals the parity of the number of inversions. The relation (\operatorname{sign}(\pi)=(-1)^{n-c}) is a classical fact (proved e.g. by writing the permutation as a product of (n-c) transpositions).