Combinatorics is the branch of mathematics which entails the study of combinations and permutations of sets of elements
Derangements Poojit Hegde June 2015 This report will discuss the theory of derangements, a topic in discrete mathematics. Some examples will also be discussed along with some extensions.
1
Background
Combinatorics is the branch of mathematics which entails the study of combinations and permutations of sets of elements and their relations. A permutation is simply the rearrangement of the elements of a set where the order has significance, whereas a combination is a selection of elements with disregard to order. For example, 1,2 and 2,1 are the same combination, yet they are different permutations. The study of derangements is an application of a permutation. They were first studied by Pierre Remond de Montmort, a famous French mathematician, who also studied probability and finite differences. He came up with the problem of derangements in 1708 and solved it in 1713. A different method of solution was later found Nicholas Bernoulli, using the principle of inclusion and exclusion. Many years later, Leonhard Euler, with no knowledge of Remond de Montmort’s work, revisited it in 1779. Euler presented methods of recursion to solve derangement problems. Euler familiarized the mathematical community with derangements, and he posed the following problem to illustrate the topic: Given any series of n letters a, b, c, d, e, etc., how many ways can they be rearranged such that no letter is in its original position?
2
What are Derangements?
Derangements are permutations of a set of elements in which no element remains in its original position. Any permutation of Sn = {1, 2, 3, · · · n} that has no fixed points is a derangement of Sn .
2.1
Scenario
There are three kids, each with a different Pokemon card. Each kid wants to give away their Pokemon card and get a different card in return. How many possible ways can this happen? 1
In essence, this problem asks to find the number of derangements for three elements. Let Kid 1 have Card A, Kid 2 have Card B, and Kid 3 have Card C. Let us denote this as {A, B, C}.
What are all the possible permutations? We can list them: {A, B, C} {A, C, B} {B, A, C} {B, C, A} {C, A, B} {C, B, A} There are a total of 6 permutations. How many of these are derangements? {B, C, A} {C, A, B} There are only 2 derangements. Thus, the two possibilities are: 1) Kid 1 gets Card B, Kid 2 gets Card C, and Kid 3 gets Card A 2) Kid 1 gets Card C, Kid 2 gets Card A, and Kid 3 gets Card B
3
Methodologies
In the previous example, there were only three objects for which the derangements were being counted. It clearly becomes much more involved to count them when n increases. Multiple techniques have been developed to count derangements.s The notation for the number of derangements of n elements is ! n. (The symbol lover Euler used the notation Π(n) to represent the number of derangements of n objects).
3.1
Using PIE
A common way to count derangements is using the principle of inclusion-exclusion (PIE). PIE is a systematic way to account for overcounting and undercounting in overlapping sets. Let us denote Fk as the number of permutations in which k elements are fixed, and let us denote. Recall that ! n is the number of derangements of n elements. (All derangement numbers (! n) are also known as subfactorial numbers. The function y =! x is called the subfactorial function.) To start with, we will consider all possible permutations. Then, we will subtract all the permutations in which exactly 1 element is fixed (same position). Then, we will add all the permutations in which exactly 2 elements are fixed. Then, we will subtract all the 2
n permutations in which exactly 3 elements are fixed, and so on. There are different cases 1 n where 1 element is fixed, 2 different cases where 2 elements are fixed, and so on. For Fk , we just have to permute n − k elements and keep k fixed. Thus, Fk = (n − k)!. n n n ! n = F0 − F1 + F2 − F3 · · · + (−1)n Fn 1 2 3 n n n = n! − (n − 1)! + (n − 2)! − (n − 3)! · · · + (−1)n 1! 1 2 3 n! n! n! − · · · + (−1)n = n! − + 1! 2! 3! 1 1 1 1 = n! (1 − + − · · · + (−1)n 1! 2! 3! n! n X 1 (−1)k = n! k! k=0 We have reached the following formula to count derangements: ! n = n!
n X
(−1)k
k=0
3.2
1 k!
Recursion
Interestingly enough, there are also recursive relationships in derangements. Assume that there are n people with n objects. Assume that the first person takes object i. Since person 1 can’t take object 1, there are n − 1 choices. Now, there are two different cases for what person i can do: pick object 1 or don’t pick object 1. Player i picks object 1: The problem is reduced to n − 2 objects and n − 2 players. Player i does not pick object 1: The problem is reduced to n − 1 objects and n − 1 players Thus, ! n = (n − 1)(! (n − 1)+! (n − 2)) , for all integers n ≥ 2. The same kind of recursive relationship can be applied to factorials. This can easily be verified using distribution and the definition of a factorial. n! = (n − 1)((n − 1)! +(n − 2)! ). Another recursive formula for the subfactorial function (derangements) is the following: ! n =! (n − 1) ∗ n + (−1)n , for integers n ≥ 1.
3.3
Probability of a Derangement
We know that derangements are a subset of all the permutations. This leads to the question, what is the probability of a permutation being a derangement? 3
The number of permutations of a set of n elements is n!. We are looking for the likelihood that a permutation of n elements (n!) is also a derangement of the set of n elements (! n). !n This is demonstrated by the ratio n! . Let’s make a table to look for a pattern. n
!n
n!
!n n!
0 1 2 3 4 5 6 7 8 9 10
1 0 1 2 9 44 265 1854 14833 133496 1334961
1 1 2 6 24 120 720 5040 40320 362880 3628800
1 0 0.5 0.33333 0.375 0.36667 0.36806 0.36786 0.36788 0.36788 0.36788
Very interestingly enough, the ratio seems to converge to about 0.36788. This is in fact approximately 1/e, where e is Euler’s number. To the accuracy of 10 digits, 1e = 0.3678794412, and !10 = 0.3678794643. As shown by the table, it converges very quickly. The following 10! result can be proved in multiple ways, including Poissonization and using Taylor Series: !n 1 = n→∞ n! e lim
We can use this limit to approximate ! n quite accurately. Since it converges quickly, rearranging the equation results in ! n ≈ n!e In fact, ! n is n!e rounded to the nearest integer. This can be represented using the floor function:
n! 1 !n = + e 2
3.4
Cave Example
There are 10 couples, each with a single child. The 10 children get lost in a dark cave. Each couple goes into the cave and pulls out one child. How many ways are there in which at least one child gets paired with their parents? What is the probability of that occurring? We can solve this problem in multiple ways. Notice that the number of ways of NO child getting paired correctly is simply ! 10. Thus, the number of ways for at least one child to get paired is total − unfavorable = 10! −! 10. How can we find ! 10? 4
One way is to use the summation formula derived using the principle of inclusion and exclusion.
! 10 = 10!
n X 1 1 1 1 1 1 1 1 1 1 1 1 ) = 1334961 (−1)k = (10! )( − + − + − + − + − + k! 0! 1! 2! 3! 4! 5! 6! 7! 8! 9! 10! k=0
We also could have solved this using a recursive formula. This would involve using previous derangements to find subsequent ones. However, since this problem is asking only for probability, the approximation for the probability of a permutation being a derangement can be used. In addition, we could have found this value using the floor function formula. This method usually takes less computational time. 1 + = b1334961.41612c = 1334961. ! 10 = 10! e 2 The problem asks for the complement of this. 10! −! 10 = 3628800 − 1334961 = 2293839. Now we can find the probability.
10!−!10 10!
=
2293839 3628800
= 0.63212053571.
as n approaches infinity. The probability can be found immediately using the limit of !n n! Notice that this fraction is the complement of the probability we desire. T 1−
! 10 1 e−1 ≈1− ≈ ≈ 0.63212055882 10! e e
. There is about a 63.2% chance of at least one child being matched up with their parents. is about 1e for almost all n, there is a 63.2% chance of at least one child being Since !n n! matched with their parents even if there are a billion children and a billion couples. Notice how computationally favorable the limit is, and it is very accurate for even small n. It is quite remarkable that the Euler’s number e appears in derangements, demonstrating the ubiquity and the beauty of the number e in mathematics.
4
Generalizations
Earlier, we encountered a formula for the derangement of n objects. ! n = n!e + 1 12 . This leads one to wonder, can this be used to extend the subfactorial function ! n to rational numbers? TO answer this question, first we need the gamma function. The gamma function is used to extrapolate the factorial function to all complex numbers, except negative integers. γ(n) = (n − 1)!. We can use this to extend the definition of the subfactorial function ! n. !n ≈
n! γ(n + 1) ≈ e e 5
We can find an exact value using the incomplete gamma function. Z ∞ γ(n + 1, −1) xn e−(x+1) dx !n = = e −1
Figure 1: Analytic continuation to the complex plane
References Dunham, William. Euler: The Master of Us All. Washington, D.C.: Mathematical Association of America, 1999. Print. Weisstein, Eric W. ”Subfactorial.” From MathWorld–A Wolfram Web Resource. ”Number of Derangements.” OeisWiki RSS. N.p., n.d. Web. 30 May 2015. Mehdi Hassani, Derangements and Applications, Journal of Integer Sequences, 6(1), Article 03.1.2, 2003. ”Derangements.” Derangements. Illinois State University Mathematics Department, n.d. Web. 30 May 2015. Baker, Greg. ”Inclusion-Exclusion.” Inclusion-Exclusion. N.p., n.d. Web. 30 May 2015.
6
