## Posts Tagged ‘**permutations**’

## The number of ways of shuffling a cabinet

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 denote the number of ministers in Macdonald’s cabinet, the answer to this question is , the number of derangements of an -element set. A *derangement* is a permutation such that no element is mapped to itself. The number of derangements of an -element set is well-known to be , which turns out to be simply the nearest integer to .

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.

## Enumerating permutations by number of inversions

We have previously given a proof of the identity

,

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 elements with inversions. Let be a permutation of , written in the so-called “one line” notation. An inversion of is a pair such that and . Let denote the number of inversions of . Then we claim that the generating function of is

.

We prove this by induction on . For , we have one permutation with no inversions and one with one inversion, whence we obtain the generating function , as claimed.

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

,

as claimed. This completes the proof.

Let denote the coefficient of in ; i.e., is the number of permutations of elements with inversions. We wish to deduce a formula for . Since is the coefficient of in , it must also equal the coefficient of in the infinite product . By Euler’s Pentagonal Number Theorem, we have

.

Thus, is the coefficient of in . By the binomial theorem, we have

(recall that ). Thus, letting denote the pentagonal numbers, we obtain a term in by multiplying a term from by a term from . The coefficient of in is , and the coefficient of in is . Thus, the coefficient of is given by

,

where the sum is over all for which . This is the desired formula for the number of permutations of elements with inversions.