Skip to main content
\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
Mathematics LibreTexts

2.2: Forbidden Position Permutations

  • Page ID
    7146
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    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_{i=1}^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_{i_1}\cap A_{i_2}\cap\cdots\cap A_{i_k}|=(n-k)!\). Thus, by the inclusion-exclusion formula, in the form of Equation 2.1.1,

    \[\eqalign{ |\bigcap_{i=1}^n A_i^c|&=|S|+\sum_{k=1}^n (-1)^k{n\choose k}(n-k)!\cr &=n!+\sum_{k=1}^n (-1)^k{n!\over k!(n-k)!}(n-k)!\cr &=n!+\sum_{k=1}^n (-1)^k{n!\over k!}\cr &=n!+n!\sum_{k=1}^n (-1)^k{1\over k!}\cr &=n!\,\Bigl(1+\sum_{k=1}^n (-1)^k{1\over k!}\Bigr)\cr &=n!\,\sum_{k=0}^n (-1)^k{1\over k!}.\cr }\nonumber\]

    The last sum should look familiar: \[e^x=\sum_{k=0}^\infty {1\over k!}x^k.\nonumber\] Substituting \(x=-1\) gives \[e^{-1} = \sum_{k=0}^\infty {1\over k!}(-1)^k.\nonumber\] The probability of getting a derangement by chance is then \[{1\over n!}n!\,\sum_{k=0}^n (-1)^k{1\over k!} =\sum_{k=0}^n (-1)^k{1\over k!},\nonumber\] and when \(n\) is bigger than 6, this is quite close to \[e^{-1} \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_{k=0}^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_{n-2}\) ways to do this. Then, keeping 1 in position \(i\), derange the numbers \(\{i,2,3,\ldots,i-1,i+1,\ldots n\}\), with the "correct'' position of \(i\) now considered to be position 1. There are \(D_{n-1}\) ways to do this. Thus, \(D_n=(n-1)(D_{n-1}+D_{n-2})\).

    We explore this recurrence relation a bit:

    \[\eqalignno{ D_n&=nD_{n-1}-D_{n-1}+(n-1)D_{n-2}&(*)\cr &=nD_{n-1}-(n-2)(D_{n-2}+D_{n-3})+(n-1)D_{n-2}\cr &=nD_{n-1}-(n-2)D_{n-2}-(n-2)D_{n-3}+(n-1)D_{n-2}\cr &=nD_{n-1}+D_{n-2}-(n-2)D_{n-3}&(*)\cr &=nD_{n-1}+(n-3)(D_{n-3}+D_{n-4})-(n-2)D_{n-3}\cr &=nD_{n-1}+(n-3)D_{n-3}+(n-3)D_{n-4}-(n-2)D_{n-3}\cr &=nD_{n-1}-D_{n-3}+(n-3)D_{n-4}&(*)\cr &=nD_{n-1}-(n-4)(D_{n-4}+D_{n-5})+(n-3)D_{n-4}\cr &=nD_{n-1}-(n-4)D_{n-4}-(n-4)D_{n-5}+(n-3)D_{n-4}\cr &=nD_{n-1}+D_{n-4}-(n-4)D_{n-5}.&(*)\cr }\nonumber\] 

    It appears from the starred lines that the pattern here is that \[D_n=nD_{n-1}+(-1)^kD_{n-k}+(-1)^{k+1}(n-k)D_{n-k-1}.\nonumber\] If this continues, we should get to \[D_n=nD_{n-1}+(-1)^{n-2}D_{2}+(-1)^{n-1}(2)D_{1}.\nonumber\] Since \(D_2=1\) and \(D_1=0\), this would give \[D_n=nD_{n-1}+(-1)^n,\nonumber\] 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 \(D_n\).

    \[\bullet\quad\bullet\quad\bullet\nonumber\]

    There are many similar problems.

    Example \(\PageIndex{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 \[Q_n=n!\,\sum_{k=0}^{n-1} (-1)^k{1\over k!}+ (n-1)!\,\sum_{k=1}^{n-1} (-1)^{k-1} {1\over (k-1)!}. \nonumber\] Note that the limits on the two sums are not identical.

    Contributors and Attributions

     


    2.2: Forbidden Position Permutations is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by David Guichard.

    • Was this article helpful?