Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

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|=(n1)!: once i is fixed in position i, the remaining n1 integers can be placed in any locations.

What about |AiAj|? If both i and j are in the correct position, the remaining n2 integers can be placed anywhere, so |AiAj|=(n2)!.

In the same way, we see that |Ai1Ai2Aik|=(nk)!. Thus, by the inclusion-exclusion formula, in the form of Equation 2.1.1,

|ni=1Aci|=|S|+nk=1(1)k(nk)(nk)!=n!+nk=1(1)kn!k!(nk)!(nk)!=n!+nk=1(1)kn!k!=n!+n!nk=1(1)k1k!=n!(1+nk=1(1)k1k!)=n!nk=0(1)k1k!.

The last sum should look familiar: ex=k=01k!xk. Substituting x=1 gives e1=k=01k!(1)k. The probability of getting a derangement by chance is then 1n!n!nk=0(1)k1k!=nk=0(1)k1k!, and when n is bigger than 6, this is quite close to e10.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,,i1,i+1,n} in all possible ways so that none of these n2 numbers is in the correct place. There are Dn2 ways to do this. Then, keeping 1 in position i, derange the numbers {i,2,3,,i1,i+1,n}, with the "correct'' position of i now considered to be position 1. There are Dn1 ways to do this. Thus, Dn=(n1)(Dn1+Dn2).

We explore this recurrence relation a bit:

Dn=nDn1Dn1+(n1)Dn2=nDn1(n2)(Dn2+Dn3)+(n1)Dn2=nDn1(n2)Dn2(n2)Dn3+(n1)Dn2=nDn1+Dn2(n2)Dn3=nDn1+(n3)(Dn3+Dn4)(n2)Dn3=nDn1+(n3)Dn3+(n3)Dn4(n2)Dn3=nDn1Dn3+(n3)Dn4=nDn1(n4)(Dn4+Dn5)+(n3)Dn4=nDn1(n4)Dn4(n4)Dn5+(n3)Dn4=nDn1+Dn4(n4)Dn5.

It appears from the starred lines that the pattern here is that Dn=nDn1+(1)kDnk+(1)k+1(nk)Dnk1. If this continues, we should get to Dn=nDn1+(1)n2D2+(1)n1(2)D1. Since D2=1 and D1=0, this would give Dn=nDn1+(1)n, since (1)n=(1)n2. 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.

Example 2.2.1

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!n1k=0(1)k1k!+(n1)!n1k=1(1)k11(k1)!. 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.

Support Center

How can we help?