TAOCP 5.1.2 Exercise 17

The generating function for the number of inversions in a random permutation of the multiset \(\{n_1\cdot x_1, n_2\cdot x_2, \ldots, n_m\cdot x_m\}\) (with \(x_1 < x_2 < \cdots < x_m\)) is the \(z\)-m...

taocpmathematicsalgorithmsvolume-3math-medium

Section 5.1.2: Permutations of a Multiset

Exercise 17. [M24] Find the average and standard deviation of the number of inversions in a random permutation of a given multiset, using the generating function found in exercise 16.

Verified: yes
Solve time: 38m35s

Solution

The generating function for the number of inversions in a random permutation of the multiset
({n_1\cdot x_1, n_2\cdot x_2, \ldots, n_m\cdot x_m}) (with (x_1 < x_2 < \cdots < x_m)) is the (z)-multinomial coefficient

[ G(z) = \binom{n}{n_1,n_2,\ldots,n_m}_z = \frac{[n]_z!}{[n_1]_z!,[n_2]_z!,\cdots,[n_m]_z!}, \qquad\text{where}\quad [k]z! = \prod{i=1}^k (1+z+\cdots+z^{i-1}). ]

The total number of permutations is (G(1) = \binom{n}{n_1,\ldots,n_m}).
Let (X) be the number of inversions. Its mean (\mu = \mathbb{E}[X]) and variance (\sigma^2 = \operatorname{Var}(X)) are obtained from the logarithmic derivatives of (G(z)) at (z=1).

Mean

Write (A_i(z) = 1+z+\cdots+z^{i-1}). Then ([k]z! = \prod{i=1}^k A_i(z)) and

[ \ln G(z) = \sum_{i=1}^n \ln A_i(z) - \sum_{j=1}^m \sum_{i=1}^{n_j} \ln A_i(z). ]

Differentiating,

[ \frac{G'(z)}{G(z)} = \sum_{i=1}^n \frac{A_i'(z)}{A_i(z)} - \sum_{j=1}^m \sum_{i=1}^{n_j} \frac{A_i'(z)}{A_i(z)}. ]

At (z=1) we have (A_i(1)=i), (A_i'(1)=1+2+\cdots+(i-1)=i(i-1)/2), hence

[ \frac{A_i'(1)}{A_i(1)} = \frac{i-1}{2}. ]

Therefore

[ \mu = \frac{G'(1)}{G(1)} = \sum_{i=1}^n \frac{i-1}{2} - \sum_{j=1}^m \sum_{i=1}^{n_j} \frac{i-1}{2} = \frac{1}{2}\left(\frac{n(n-1)}{2} - \sum_{j=1}^m \frac{n_j(n_j-1)}{2}\right) = \frac{1}{4}\left(n(n-1) - \sum_{j=1}^m n_j(n_j-1)\right). ]

Since (\sum n_j = n), this simplifies to

[ \boxed{\mu = \frac{1}{4}\left(n^2 - \sum_{j=1}^m n_j^2\right)}. ]

Variance

The variance is (\sigma^2 = \frac{G''(1)}{G(1)} + \frac{G'(1)}{G(1)} - \left(\frac{G'(1)}{G(1)}\right)^2 = H''(1) + H'(1)) with (H = \ln G).
We already have (H'(1) = \mu). To find (H''(1)) we differentiate (f_i(z) = A_i'(z)/A_i(z)):

[ f_i'(z) = \frac{A_i''(z)A_i(z) - (A_i'(z))^2}{A_i(z)^2}. ]

At (z=1): (A_i(1)=i), (A_i'(1)=i(i-1)/2), and (A_i''(1) = \sum_{k=2}^{i-1} k(k-1) = \frac{i(i-1)(i-2)}{3}).

Thus

[ f_i'(1) = \frac{\frac{i(i-1)(i-2)}{3}\cdot i - \left(\frac{i(i-1)}{2}\right)^2}{i^2} = \frac{(i-1)(i-2)}{3} - \frac{(i-1)^2}{4} = \frac{(i-1)(i-5)}{12}. ]

Summing from (i=1) to (n) (the term for (i=1) is zero):

[ \sum_{i=1}^n f_i'(1) = \frac{1}{12}\sum_{i=1}^n (i^2-6i+5) = \frac{1}{12}\left(\frac{n(n+1)(2n+1)}{6} - 3n(n+1) + 5n\right) = \frac{n(2n^2-15n+13)}{72}. ]

Hence

[ H''(1) = \frac{1}{72}\left[ n(2n^2-15n+13) - \sum_{j=1}^m n_j(2n_j^2-15n_j+13) \right]. ]

Now (\sigma^2 = H''(1) + \mu). Adding (\mu = \frac{18}{72}\left(n^2 - \sum n_j^2\right)) gives

[ \sigma^2 = \frac{1}{72}\left[ n(2n^2-15n+13) + 18n^2

  • \sum_{j=1}^m \bigl( n_j(2n_j^2-15n_j+13) + 18n_j^2 \bigr) \right]. ]

The bracket simplifies because the linear terms (13n) and (13\sum n_j) cancel (since (\sum n_j = n)):

[ n(2n^2-15n+13) + 18n^2 = 2n^3 + 3n^2 + 13n, ] [ n_j(2n_j^2-15n_j+13) + 18n_j^2 = 2n_j^3 + 3n_j^2 + 13n_j. ]

Therefore

[ \sigma^2 = \frac{1}{72}\left[ 2\Bigl(n^3 - \sum_{j=1}^m n_j^3\Bigr)

  • 3\Bigl(n^2 - \sum_{j=1}^m n_j^2\Bigr) \right]. ]

The standard deviation is the square root of the variance.

[ \boxed{\sigma^2 = \frac{1}{72}\left[ 2\left(n^3 - \sum_{j=1}^m n_j^3\right) + 3\left(n^2 - \sum_{j=1}^m n_j^2\right) \right]}, \qquad \boxed{\sigma = \sqrt{\sigma^2}}. ]

Verification

  • For a set ((n_j=1) for all (j), (m=n)):
    (\mu = \frac{n^2-n}{4} = \binom{n}{2}/2),
    (\sigma^2 = \frac{n(n-1)(2n+5)}{72}), matching the classical result.

  • For a multiset with all elements equal ((m=1), (n_1=n)):
    (\mu = 0), (\sigma^2 = 0), as there is only one permutation.

  • For ({2\cdot a, 1\cdot b}) ((n=3), (n_1=2,n_2=1)):
    (\mu = 1), (\sigma^2 = 2/3), agreeing with the distribution (0,1,2) each with probability (1/3).