Derangements and the Inclusion-Exclusion Principle

 

             This section gives proofs of some unproved observations; it is a bit more technical than the rest of the article.  A derangement is another name for a permutation with no fixed points.  We can count the number of derangements using the Principle of Inclusion-Exclusion (see Tucker 2002, pages 321-322).  If we have subsets  chosen from a set with  elements, then the number of the elements that do not appear in any of the subsets is , which is a generalization of Venn Diagram counting arguments.  We first subtract the number of elements in the sum of all the subsets, and if there are any intersections, we have subtracted too much, so we add back the number of elements that are common to pairs of sets, but this is adding back too much, so we subtract, etc.  In counting derangements, our “elements” are the  possible name games.  We let  represent the set of permutations in which  is a fixed point.  The intersection of  of the  ’s consists of permutations that have a particular  elements fixed.  There are  different such intersections, and within each, there are  elements in the set, each corresponding to a different permutation of the elements that are not (necessarily) fixed.  Thus, the number of derangements is .  The Taylor Series  converges to , where  is the constant 2.71828…, and this convergence is very rapid; the first six terms are correct to within three decimal places.  Thus, the number of derangements is approximately  and the probability that a random permutation is a derangement is approximately . 

To find the rest of the distribution, we let  be the probability that in a game with  players,  pick their own names.  Then, we can choose the fixed points in  ways and the non-matches in  ways.  Thus, , and since , we have .  The table below shows the approximate values of elements in this distribution.

Asymptotic Probability Distribution of Number of Fixed Points

Number of Fixed Points	Probability
0	1/e  36.7879%
1	1/e  36.7879%
2	1/2e  18.3940%
3	1/6e  6.1313%
4	1/24e  1.5328%
5	1/120e  0.3066%
6	1/720e  0.0511%
7	1/5040e  0.0073%
8	1/40320e  0.0009%

 

 

 

We can use a similar inclusion-exclusion argument to find the number of permutations with no 2-cycles, no 3-cycles, etc., and from there derive results for the distributions of each of these.  For counting the number without 2-cycles, we let  be the set of permutations that contain  as a 2-cycle.  The intersection of  of the  ’s consists of permutations that have a particular  2-cycles.  There are  ways to choose the elements in the 2-cycles, and  ways to arrange them into 2-cycles (there are  ways to arrange the elements in a line; we then place parenthesis on the first two, the next two, etc.  We have over counted by a factor of  ways to arrange the  2-cycles and by  because there are 2 ways to arrange the elements within each cycle).  There are  ways to arrange the elements that are not (necessarily) in 2-cycles.  Thus, the number of permutations without 2-cycles is  , which converges to , so that the probability that a permutation has no two cycles is .  Similar arguments show that the probability that a permutation has no  -cycles is .  

 

Tucker, Alan.  Applied Combinatorics, 4^th edition.  New York: Wiley, 2002.

 

Note: This is a supplement to, Borkovitz, Debra, “The Name Game: Exploring Random Permutations.”  Mathematics Teacher 98 (October 2005).

 

PDF Version                            Back to Articles                        Home