2.2: Forbidden Position Permutations
( \newcommand{\kernel}{\mathrm{null}\,}\)
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,…,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 Ai be the permutations of [n] in which i is in the correct place. Then we want to know |⋂ni=1Aci|.
For any i, |Ai|=(n−1)!: once i is fixed in position i, the remaining n−1 integers can be placed in any locations.
What about |Ai∩Aj|? If both i and j are in the correct position, the remaining n−2 integers can be placed anywhere, so |Ai∩Aj|=(n−2)!.
In the same way, we see that |Ai1∩Ai2∩⋯∩Aik|=(n−k)!. Thus, by the inclusion-exclusion formula, in the form of Equation 2.1.1,
|n⋂i=1Aci|=|S|+n∑k=1(−1)k(nk)(n−k)!=n!+n∑k=1(−1)kn!k!(n−k)!(n−k)!=n!+n∑k=1(−1)kn!k!=n!+n!n∑k=1(−1)k1k!=n!(1+n∑k=1(−1)k1k!)=n!n∑k=0(−1)k1k!.
The last sum should look familiar: ex=∞∑k=01k!xk. Substituting x=−1 gives e−1=∞∑k=01k!(−1)k. The probability of getting a derangement by chance is then 1n!n!n∑k=0(−1)k1k!=n∑k=0(−1)k1k!, and when n is bigger than 6, this is quite close to e−1≈0.3678. So in the case of a deck of cards, the probability of a derangement is about 37%.
Let Dn=n!∑nk=0(−1)k1k!. These derangement numbers have some interesting properties. The derangements of [n] may be produced as follows: For each i∈{2,3,…,n}, put i in position 1 and 1 in position i. Then permute the numbers {2,3,…,i−1,i+1,…n} in all possible ways so that none of these n−2 numbers is in the correct place. There are Dn−2 ways to do this. Then, keeping 1 in position i, derange the numbers {i,2,3,…,i−1,i+1,…n}, with the "correct'' position of i now considered to be position 1. There are Dn−1 ways to do this. Thus, Dn=(n−1)(Dn−1+Dn−2).
We explore this recurrence relation a bit:
Dn=nDn−1−Dn−1+(n−1)Dn−2=nDn−1−(n−2)(Dn−2+Dn−3)+(n−1)Dn−2=nDn−1−(n−2)Dn−2−(n−2)Dn−3+(n−1)Dn−2=nDn−1+Dn−2−(n−2)Dn−3=nDn−1+(n−3)(Dn−3+Dn−4)−(n−2)Dn−3=nDn−1+(n−3)Dn−3+(n−3)Dn−4−(n−2)Dn−3=nDn−1−Dn−3+(n−3)Dn−4=nDn−1−(n−4)(Dn−4+Dn−5)+(n−3)Dn−4=nDn−1−(n−4)Dn−4−(n−4)Dn−5+(n−3)Dn−4=nDn−1+Dn−4−(n−4)Dn−5.
It appears from the starred lines that the pattern here is that Dn=nDn−1+(−1)kDn−k+(−1)k+1(n−k)Dn−k−1. If this continues, we should get to Dn=nDn−1+(−1)n−2D2+(−1)n−1(2)D1. Since D2=1 and D1=0, this would give Dn=nDn−1+(−1)n, since (−1)n=(−1)n−2. Indeed this is true, and can be proved by induction. This gives a somewhat simpler recurrence relation, making it quite easy to compute Dn.
∙∙∙
There are many similar problems.
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 Qn=n!n−1∑k=0(−1)k1k!+(n−1)!n−1∑k=1(−1)k−11(k−1)!. Note that the limits on the two sums are not identical.