Classical combinatorial numbers · Definition

Derangement

enumerative combinatoricsclassical combinatorial numbers

Before you start you need to know

The hat-check problem asks how many permutations avoid every fixed point. The answer follows directly from the inclusion-exclusion principle.

Definition

A derangement is a permutation of \(n\) elements with no fixed points; the number of derangements is \(D_n\).

\[D_n = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}\]

Let \(A_i\) be the set of permutations that fix element \(i\). Since \(|A_{i_1}\cap\cdots\cap A_{i_k}|=(n-k)!\), inclusion-exclusion gives the formula above. Moreover, \(D_n=(n-1)(D_{n-1}+D_{n-2})\) and \(D_n/n!\to e^{-1}\).

For \(n=4\) we add \(4!\), subtract \(\binom{4}{1}3!\), add \(\binom{4}{2}2!\), subtract \(\binom{4}{3}1!\), and add \(\binom{4}{4}0!\), which gives \(9\). For example, \(2143\) and \(4321\) are two of these derangements.

Typical error: keeping only the first term of the series and writing \(D_n\approx n!-1\), forgetting that higher-order terms correct the overlaps between fixed-point sets.

Think about it

Why does \(n!-\sum_i |A_i|\) give zero instead of \(D_n\)?

Because \(\sum_i |A_i|=n\,(n-1)!=n!\) overcounts permutations with several fixed points; the intersections must be added back.

Exercises 10

  1. Which of these permutations of \(\{1,2,3,4\}\), written as \(\sigma(1)\sigma(2)\sigma(3)\sigma(4)\), is a derangement?
  2. Of the 9 derangements of 4 elements, how many are a single 4-cycle?
  3. What is \(D_3\)?
  4. What is \(D_4\)?
  5. If \(D_n/n!\) approaches \(1/e\), what approximate proportion of permutations of \(n\) elements has at least one fixed point for large \(n\)?
  6. In the series \(D_n/n!=\sum_{k=0}^{n}\frac{(-1)^k}{k!}\), what is the coefficient of the term \(k=2\)?
  7. For large \(n\), what value does \(D_n/n!\) approach?
  8. How many permutations of 5 elements have exactly one fixed point?
  9. How many permutations of 4 elements fix at least one point?
  10. Which statement about \(D_n\) is false?

References

  • Richard P. Stanley, Enumerative Combinatorics, Volume 1, 2nd edition, Cambridge University Press, 2012.
  • Herbert S. Wilf, generatingfunctionology, 3rd edition, A K Peters, 2006.