Uniformly at Random

Posts Tagged ‘permutations

The number of ways of shuffling a cabinet

leave a comment »

No doubt the first question on the mind of anyone reading the previous post concerning John A. Macdonald’s double shuffle is, “In how many ways could Macdonald have appointed his former cabinet members to new ministries so that no minister was appointed to the same position that he had held in the previous Macdonald government?”

Letting n denote the number of ministers in Macdonald’s cabinet, the answer to this question is d(n), the number of derangements of an n-element set. A derangement is a permutation such that no element is mapped to itself. The number of derangements of an n-element set is well-known to be d(n) = n! \sum_{i=0}^n (-1)^i/i!, which turns out to be simply the nearest integer to n!/e.

I am too lazy to bother writing a proof of this formula here, so instead I refer the reader to, for example, the book Concrete Mathematics by Graham, Knuth and Patashnik.

Advertisements

Written by uncudh

February 27, 2009 at 4:44 pm

Posted in math

Tagged with ,

Enumerating permutations by number of inversions

with 2 comments

We have previously given a proof of the identity

\prod_{i \geq 1}(1-q^i) = \sum_{n=-\infty}^\infty (-1)^n q^{(3n^2+n)/2},

which is Euler’s Pentagonal Number Theorem. We now describe how to apply this formula to derive a formula for the number of permutations of n elements with k inversions. Let p = p_1p_2 \cdots p_n be a permutation of 1,2,\ldots,n, written in the so-called “one line” notation. An inversion of p is a pair (p_i,p_j) such that i<j and p_i>p_j. Let i(p) denote the number of inversions of p. Then we claim that the generating function I_n of i(p) is

I_n(q) = \sum_{p \in S_n} q^{i(p)} = (1+q)(1+q+q^2)\cdots(1+q+\cdots+q^{n-1}) = \prod_{i=1}^n\frac{1-q^i}{1-q}.

We prove this by induction on n. For n=2, we have one permutation with no inversions and one with one inversion, whence we obtain the generating function I_2(q) = 1+q, as claimed.

Suppose the claim holds for n-1 and let p be a permutation of 1,2,\ldots,n-1. We create a new permutation q by inserting n into p. If we insert n after all elements of p we have created no new inversions; if we insert n after all but one element of p we have created one new inversion; and in general, if we insert n after all but i elements of p we create i new inversions. Thus the number of permutations so created is enumerated by the generating function

I_{n-1}(q)\cdot(1+q+\cdots+q^{n-1}) = (1+q)(1+q+q^2)\cdots(1+q+\cdots+q^{n-1}),

as claimed. This completes the proof.

Let b(n,k) denote the coefficient of q^k in I_n(q); i.e., b(n,k) is the number of permutations of n elements with k inversions. We wish to deduce a formula for b(n,k). Since b(n,k) is the coefficient of q^k in \prod_{i=1}^n\frac{1-q^i}{1-q} = (1-q)^{-n}\prod_{i=1}^n (1-q^i), it must also equal the coefficient of q^k in the infinite product (1-q)^{-n}\prod_{i \geq 1}(1-q^i). By Euler’s Pentagonal Number Theorem, we have

(1-q)^{-n}\prod_{i \geq 1}(1-q^i) = (1-q)^{-n}\sum_{j=-\infty}^\infty (-1)^j q^{(3j^2+j)/2}.

Thus, b(n,k) is the coefficient of q^k in (1-q)^{-n}\sum_{j=-\infty}^\infty (-1)^j q^{(3j^2+j)/2}. By the binomial theorem, we have

(1-q)^{-n} = \sum_{h \geq 0} {n+h-1 \choose h}q^h

(recall that {-n \choose h} = (-1)^h {n+h-1 \choose h}). Thus, letting d_j = (3j^2+j)/2 denote the pentagonal numbers, we obtain a term q^k in (1-q)^{-n}\sum_{j=-\infty}^\infty (-1)^j q^{d_j} by multiplying a term q^{k-d_j} from (1-q)^{-n} by a term q^{d_j} from \sum_{j=-\infty}^\infty (-1)^j q^{d_j}. The coefficient of q^{k-d_j} in (1-q)^{-n} is {n+k-d_j-1 \choose k-d_j}, and the coefficient of q^{d_j} in \sum_{j=-\infty}^\infty (-1)^j q^{d_j} is (-1)^j. Thus, the coefficient b(n,k) of q^k is given by

b(n,k) = \sum_j (-1)^j {n+k-d_j-1 \choose k-d_j},

where the sum is over all j for which d_j \leq k. This is the desired formula for the number of permutations of n elements with k inversions.

Written by uncudh

February 17, 2009 at 2:48 am

Posted in math

Tagged with , ,