2.2: Forbidden Position Permutations

Suppose we shuffle a deck of cards; what is the probability that no card is in its original location? More generally, how many permutations of \([n]=\<1,2,3,\ldots,n\>\) have none of the integers in their "correct'' locations? That is, 1 is not first, 2 is not second, and so on. Such a permutation is called a derangement of \([n]\). Let \(S\) be the set of all permutations of \([n]\) and \(A_i\) be the permutations of \([n]\) in which \(i\) is in the correct place. Then we want to know \(|\bigcap_^n A_i^c|\). For any \(i\), \(|A_i|=(n-1)!\): once \(i\) is fixed in position \(i\), the remaining \(n-1\) integers can be placed in any locations. What about \(|A_i\cap A_j|\)? If both \(i\) and \(j\) are in the correct position, the remaining \(n-2\) integers can be placed anywhere, so \(|A_i\cap A_j|=(n-2)!\). In the same way, we see that \(|A_\cap A_\cap\cdots\cap A_|=(n-k)!\). Thus, by the inclusion-exclusion formula, in the form of Equation 2.1.1, \[\eqalign< |\bigcap_^n A_i^c|&=|S|+\sum_^n (-1)^k(n-k)!\cr &=n!+\sum_^n (-1)^k(n-k)!\cr &=n!+\sum_^n (-1)^k\cr &=n!+n!\sum_^n (-1)^k<1\over k!>\cr &=n!\,\Bigl(1+\sum_^n (-1)^k<1\over k!>\Bigr)\cr &=n!\,\sum_^n (-1)^k<1\over k!>.\cr >\nonumber\] The last sum should look familiar: \[e^x=\sum_^\infty <1\over k!>x^k.\nonumber\] Substituting \(x=-1\) gives \[e^ = \sum_^\infty <1\over k!>(-1)^k.\nonumber\] The probability of getting a derangement by chance is then \[<1\over n!>n!\,\sum_^n (-1)^k <1\over k!>=\sum_^n (-1)^k<1\over k!>,\nonumber\] and when \(n\) is bigger than 6, this is quite close to \[e^ \approx 0.3678.\nonumber\] So in the case of a deck of cards, the probability of a derangement is about 37%. Let \(D_n=n!\,\sum_^n (-1)^k<1\over k!>\). These derangement numbers have some interesting properties. The derangements of \([n]\) may be produced as follows: For each \(i\in\<2,3,\ldots,n\>\), put \(i\) in position 1 and 1 in position \(i\). Then permute the numbers \(\<2,3,\ldots,i-1,i+1,\ldots n\>\) in all possible ways so that none of these \(n-2\) numbers is in the correct place. There are \(D_\) ways to do this. Then, keeping 1 in position \(i\), derange the numbers \(\\), with the "correct'' position of \(i\) now considered to be position 1. There are \(D_\) ways to do this. Thus, \(D_n=(n-1)(D_+D_)\). We explore this recurrence relation a bit: \[\eqalignno< D_n&=nD_-D_+(n-1)D_&(*)\cr &=nD_-(n-2)(D_+D_)+(n-1)D_\cr &=nD_-(n-2)D_-(n-2)D_+(n-1)D_\cr &=nD_+D_-(n-2)D_&(*)\cr &=nD_+(n-3)(D_+D_)-(n-2)D_\cr &=nD_+(n-3)D_+(n-3)D_-(n-2)D_\cr &=nD_-D_+(n-3)D_&(*)\cr &=nD_-(n-4)(D_+D_)+(n-3)D_\cr &=nD_-(n-4)D_-(n-4)D_+(n-3)D_\cr &=nD_+D_-(n-4)D_.&(*)\cr >\nonumber\] It appears from the starred lines that the pattern here is that \[D_n=nD_+(-1)^kD_+(-1)^(n-k)D_.\nonumber\] If this continues, we should get to \[D_n=nD_+(-1)^D_+(-1)^(2)D_.\nonumber\] Since \(D_2=1\) and \(D_1=0\), this would give \[D_n=nD_+(-1)^n,\nonumber\] since \( (-1)^n=(-1)^\). Indeed this is true, and can be proved by induction. This gives a somewhat simpler recurrence relation, making it quite easy to compute \(D_n\). \[\bullet\quad\bullet\quad\bullet\nonumber\] There are many similar problems.

Example \(\PageIndex\)

How many permutations of \([n]\) contain no instance of \(i\) followed by \(i+1\)? Solution By a similar use of the inclusion-exclusion formula, it turns out that this is \[Q_n=n!\,\sum_^ (-1)^k<1\over k!>+ (n-1)!\,\sum_^ (-1)^ <1\over (k-1)!>. \nonumber\] Note that the limits on the two sums are not identical.

This page titled 2.2: Forbidden Position Permutations is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by David Guichard via source content that was edited to the style and standards of the LibreTexts platform.

  1. Back to top