TAOCP 5.2.1 Exercise 37

**Proof of the identity.

taocpmathematicsalgorithmsvolume-3math-medium

Section 5.2.1: Sorting by Insertion

Exercise 37. [M25] Let $g_n(z)$ be the probability generating function for inversions in a random permutation of $n$ objects, Eq. 5.1.1–(11). Let $g_{Mn}(z)$ be the corresponding generating function for the quantity $B$ in Program M. Show that

$$\sum_{n \ge 0} g_{Mn}(z) \frac{M^N u^N}{N!} = \left(\sum_{n \ge 0} g_n(z) \frac{u^n}{n!}\right)^M,$$

and use this formula to derive the variance of $B$.

Verified: no
Solve time: 11m18s

Solution

Proof of the identity.

Let (g_n(z)) be the probability generating function for the number of inversions in a uniformly random permutation of (n) objects. From Eq. 5.1.1-(11),

[ g_n(z) = \frac{1}{n!}\prod_{k=1}^n\frac{1-z^k}{1-z}. ]

In Program M (a multiway merge sort) the (N) records are distributed into (M) lists, each sorted independently by straight insertion. The quantity (B) is the total number of moves, which equals the total number of inversions inside the lists. If the input permutation is random, the assignment of elements to lists is uniform and independent; hence the list sizes follow a multinomial distribution with parameters (N) and (p = 1/M). Given the sizes (n_1,\dots,n_M) (with (\sum n_i = N)), the lists are independent random permutations. Therefore the probability generating function of (B) is

[ g_{MN}(z) = \sum_{\substack{n_1+\cdots+n_M=N\ n_i\ge 0}} \frac{N!}{n_1!\cdots n_M!},\frac{1}{M^N}\prod_{i=1}^M g_{n_i}(z). ]

Multiply by (M^N u^N/N!) and sum over (N\ge 0):

[ \sum_{N\ge 0} g_{MN}(z)\frac{M^N u^N}{N!} = \sum_{N\ge 0}\sum_{n_1+\cdots+n_M=N} \prod_{i=1}^M \frac{g_{n_i}(z) u^{n_i}}{n_i!} = \left(\sum_{n\ge 0} g_n(z)\frac{u^n}{n!}\right)^M. ]

This establishes the required identity.

Derivation of the variance.

Set (A(u) = \sum_{n\ge 0} g_n(z)\frac{u^n}{n!}). The identity becomes

[ \sum_{N\ge 0} g_{MN}(z)\frac{M^N u^N}{N!} = A(u)^M. \tag{1} ]

We know (g_n(1)=1), so (A(u)\big|_{z=1} = e^u). The first two factorial moments of inversions in a single permutation are

[ \mu_n = \frac{n(n-1)}{4}, \qquad \nu_n = E[X_n(X_n-1)] = \frac{n(n-1)(n-2)(9n+13)}{144}, ]

hence

[ A'(u)\big|{z=1} = \sum{n\ge 0} \mu_n\frac{u^n}{n!}, \qquad A''(u)\big|{z=1} = \sum{n\ge 0} \nu_n\frac{u^n}{n!}. ]

Differentiate (1) with respect to (z) and set (z=1):

[ \sum_{N\ge 0} E[B_N]\frac{M^N u^N}{N!} = M e^{(M-1)u}\sum_{n\ge 0} \mu_n\frac{u^n}{n!}. ]

Extracting the coefficient of (u^N/N!) gives

[ E[B_N] M^N = M\sum_{k=0}^N \binom{N}{k}(M-1)^k \mu_{N-k}. ]

Substituting (\mu_{N-k} = (N-k)(N-k-1)/4) and simplifying yields

[ E[B_N] = \frac{N(N-1)}{4M}. \tag{2} ]

Differentiate (1) twice and evaluate at (z=1):

[ \sum_{N\ge 0} E[B_N(B_N-1)]\frac{M^N u^N}{N!} = M(M-1) e^{(M-2)u}\bigl(A'(u)\bigr)^2\big|_{z=1}

  • M e^{(M-1)u} A''(u)\big|_{z=1}. ]

The coefficient of (u^N/N!) on the right‑hand side is

[ M(M-1)\sum_{k=0}^N \binom{N}{k}(M-2)^k \sum_{i=0}^{N-k} \binom{N-k}{i}\mu_i\mu_{N-k-i}

  • M\sum_{k=0}^N \binom{N}{k}(M-1)^k \nu_{N-k}. ]

Evaluating the sums (or, more simply, using the combinatorial interpretation that (B) is the sum of the inversions in (M) independent lists whose sizes are multinomial) gives

[ E[B_N(B_N-1)] = \frac{N^{(4)}}{16 M^2} + \frac{5}{18}\frac{N^{(3)}}{M^2}, \tag{3} ]

where (N^{(4)} = N(N-1)(N-2)(N-3)) and (N^{(3)} = N(N-1)(N-2)).

The variance is

[ \operatorname{Var}(B_N) = E[B_N(B_N-1)] + E[B_N] - \bigl(E[B_N]\bigr)^2. ]

Substitute (2) and (3):

\begin{align*} \operatorname{Var}(B_N) &= \frac{N^{(4)}}{16 M^2} + \frac{5}{18}\frac{N^{(3)}}{M^2}

  • \frac{N(N-1)}{4M} - \frac{N^2(N-1)^2}{16 M^2} \[4pt] &= \frac{1}{16 M^2}\bigl(N^{(4)} - N^2(N-1)^2\bigr)
  • \frac{5}{18 M^2}N^{(3)}
  • \frac{N(N-1)}{4M} \[4pt] &= \frac{-4N^3 + 10N^2 - 6N}{16 M^2}
  • \frac{5(N^3 - 3N^2 + 2N)}{18 M^2}
  • \frac{N^2 - N}{4M} \[4pt] &= \frac{4N^3 - 30N^2 + 26N}{144 M^2}
  • \frac{36M N^2 - 36M N}{144 M^2} \[4pt] &= \frac{4N^3 + (36M-30)N^2 + (26-36M)N}{144 M^2} \[4pt] &= \frac{N(N-1)(2N + 18M - 13)}{72 M^2}. \end{align*}

Thus the variance of (B) is

[ \boxed{\operatorname{Var}(B) = \frac{N(N-1)(2N + 18M - 13)}{72 M^2}}. ]

Verification. For (M=1) this reduces to the well‑known variance of inversions in a random permutation, (\frac{N(N-1)(2N+5)}{72}). For (N=2) it gives (\frac{2\cdot1(4+18M-13)}{72 M^2} = \frac{2M-1}{4M^2}), which matches the direct calculation.

This completes the proof. ∎