objects, how many leave no object in its original place?
The answer to the question will provide a general formula for ! n and so for p n = ! n/n !, the probability that a permutation of n objects is a derangement.
Before we begin, we have said that the notation ! n is standard, but it will be convenient for us to use the alternative D n = ! n . The use of ! n does have something of a visual disadvantage when expressions contain both factorials and subfactorials, as some will in what follows; also, not that it matters to us, the expression ! n ! is ambiguous. For example, !3! might mean (!3)! = 2! = 2 or !(3! ) = !6 = 265; compare this with the respective equivalents of D 3 ! = 2 and D 3 ! = 265.
A First Solution
First, we will find a recurrence relation for D n .
If {a 1 , a 2 , a 3 , …,a n } is a derangement of { 1, 2, 3, …,n} , it must be that a 1 ≠ 1, which leaves n - 1 possibilities for it; for the sake of illustration we will assume that a 1 = 2. Now let d n be the number of such derangements, which means that D n = (n - 1 )d n . Now there are two possibilities:
(1) a 2 = 1, which means that the derangement has the form { 2,1, a 3 , a 4 , a 5 , …,a n } , where {a 3 , a 4 , a 5 , …,a n } is a derangement of { 3,4,5, …,n} , and there are exactly D n-2 of these;
(2) a 2 ≠ 1, with {a 2 , a 3 , a 4 , …,a n } a derangement of { 1, 3, 4, …,n} ; there are D n-1 of these.
These combine to mean that d n = D n-1 + D n-2 and therefore
(Incidentally, this means that D n must be divisible by n - 1.)
Table 5.1. Numbers of derangements for small sets.
Knowing that D 1 = 0 and D 2 = 1, this relation will allow us to generate D n for any n and table 5.1 shows the first few of them.
(Using this result and induction, it is also easy to establish that D n = nD n-1 + (-1) n .)
We are interested in p n = D n /n !, the probability of a permutation of n objects being a derangement, and the recurrence relation that we have just derived allows us to begin to find a general expression for this:
And so,
And we now have a recurrence relation for p n , which we can most easily deal with by writing q n = p n - p n-1 and chasingdown the expressions to get
where
This means that we may write
tidying up the −1 term.
Now, if we write the expressions for q n explicitly, we get
and if we add the equations vertically we have, after almost complete cancellation on the right-hand side,
which can conveniently be written as
and we have the expression we seek.
Bernoulli’s Solution
The more powerful the mathematical tools used to prove a result, the shorter that proof might be expected to be and we should not ignore the significantly shorter attack which is based on the inclusion–exclusion principle. The general principle is discussed in appendix A and the eminent Nicholas Bernoulli used it to establish the formula for D n in the following way.
Using the inclusion–exclusion principle we have that
with the series finishing with the number 1, which is the total number of permutations fixing all n numbers. So,
with the first part of each term the number of ways of choosing the numbers to be fixed and the second the number of permutations of what remains. Simplifying gives
And so
and, once again,
The Final Proof
Following Heba Hathout’s article ‘The old hats problem’ 1 , we can count the n ! ways of arranging the n objects by partitioning the ways into n + 1 disjoint subsets S 0 , S 1 , S 2 , …,S n , where S r is the set of permutations in which there are exactly n - r fixed points, and we will write N(S r ) for the number of elements in S r . For example, if there are two fixed points, we have the subset of permutations S n-2 with the two fixed points chosen inpossible ways: this means that
Continuing the argument results in the total number of permutations of the n objects decomposed in terms of the N(S r ) as
We then have that
and this is a special form of an expression amenable to
The answer to the question will provide a general formula for ! n and so for p n = ! n/n !, the probability that a permutation of n objects is a derangement.
Before we begin, we have said that the notation ! n is standard, but it will be convenient for us to use the alternative D n = ! n . The use of ! n does have something of a visual disadvantage when expressions contain both factorials and subfactorials, as some will in what follows; also, not that it matters to us, the expression ! n ! is ambiguous. For example, !3! might mean (!3)! = 2! = 2 or !(3! ) = !6 = 265; compare this with the respective equivalents of D 3 ! = 2 and D 3 ! = 265.
A First Solution
First, we will find a recurrence relation for D n .
If {a 1 , a 2 , a 3 , …,a n } is a derangement of { 1, 2, 3, …,n} , it must be that a 1 ≠ 1, which leaves n - 1 possibilities for it; for the sake of illustration we will assume that a 1 = 2. Now let d n be the number of such derangements, which means that D n = (n - 1 )d n . Now there are two possibilities:
(1) a 2 = 1, which means that the derangement has the form { 2,1, a 3 , a 4 , a 5 , …,a n } , where {a 3 , a 4 , a 5 , …,a n } is a derangement of { 3,4,5, …,n} , and there are exactly D n-2 of these;
(2) a 2 ≠ 1, with {a 2 , a 3 , a 4 , …,a n } a derangement of { 1, 3, 4, …,n} ; there are D n-1 of these.
These combine to mean that d n = D n-1 + D n-2 and therefore
(Incidentally, this means that D n must be divisible by n - 1.)
Table 5.1. Numbers of derangements for small sets.
Knowing that D 1 = 0 and D 2 = 1, this relation will allow us to generate D n for any n and table 5.1 shows the first few of them.
(Using this result and induction, it is also easy to establish that D n = nD n-1 + (-1) n .)
We are interested in p n = D n /n !, the probability of a permutation of n objects being a derangement, and the recurrence relation that we have just derived allows us to begin to find a general expression for this:
And so,
And we now have a recurrence relation for p n , which we can most easily deal with by writing q n = p n - p n-1 and chasingdown the expressions to get
where
This means that we may write
tidying up the −1 term.
Now, if we write the expressions for q n explicitly, we get
and if we add the equations vertically we have, after almost complete cancellation on the right-hand side,
which can conveniently be written as
and we have the expression we seek.
Bernoulli’s Solution
The more powerful the mathematical tools used to prove a result, the shorter that proof might be expected to be and we should not ignore the significantly shorter attack which is based on the inclusion–exclusion principle. The general principle is discussed in appendix A and the eminent Nicholas Bernoulli used it to establish the formula for D n in the following way.
Using the inclusion–exclusion principle we have that
with the series finishing with the number 1, which is the total number of permutations fixing all n numbers. So,
with the first part of each term the number of ways of choosing the numbers to be fixed and the second the number of permutations of what remains. Simplifying gives
And so
and, once again,
The Final Proof
Following Heba Hathout’s article ‘The old hats problem’ 1 , we can count the n ! ways of arranging the n objects by partitioning the ways into n + 1 disjoint subsets S 0 , S 1 , S 2 , …,S n , where S r is the set of permutations in which there are exactly n - r fixed points, and we will write N(S r ) for the number of elements in S r . For example, if there are two fixed points, we have the subset of permutations S n-2 with the two fixed points chosen inpossible ways: this means that
Continuing the argument results in the total number of permutations of the n objects decomposed in terms of the N(S r ) as
We then have that
and this is a special form of an expression amenable to
Similar Books
Mourning Glory
Warren Adler
Breaking Point
C. J. Box
Under His Command
Annabel Wolfe
The Mating Intent-mobi
Bonnie Vanak
Shoeshine Girl
Clyde Robert Bulla
Free Lunch
David Cay Johnston
Wolf's Desire
Ambrielle Kirk
The Empire (The Lover's Opalus)
Grayson Reyes-Cole
Not Dead in the Heart of Dixie
R Kralik
Abigail's Story
Ann Burton