446 CHAPTER 7 Counting and Combinatorics
IAI n A 3 1, IA 2 N 43 1, and JAI nA 2 n A 3 J. A 1 = {1 23,1 32). A 2 = {1 23,32 1}. A 3 -
{123, 2134. JA 1 A 21 = A 1 nA 31 = IA 2 n A 31 = 1{123}I- =1. A 1 nA 2 n A 31 = 1.
We first count the number of permutations that fix at least one element:IAI U A 2 UA 31 = JAl + jA 2 j + lA 31 - JA 1 nAA 2 - JA 1 NA 3 - IA 2 NA 3 I+JA 1 nA 2 NA 3 I
=2+2+2-1-1-1+1=4
The number of derangements is just the difference between the number of permutationsand the number of permutations that fix at least one element: 6 - 4 = 2. U
The reader should compare this solution to the Hat Check Problem in Section 1.5.3.Constructing the kth Permutation
Computer simulations often use randomly generated permutations of sets of n elements as
test data. If all the permutations on n elements are listed in some order, then by generating
a random number k such that 1 < k < n, it is possible to choose the kth permutation of n
elements at random.
An alternative to storing all the n! permutations of an n-element set is to find a method
for constructing the kth of n! permutations on n elements one element at a time without
constructing any of the other n! - 1 permutations.
The kth of n! permutations of n elements must be found relative to some ordering of
the permutations. For the method shown here, assume that the permutations are in lexi-
cographical or dictionary order (see Example 9 in Section 3.8.2). This ordering for the
permutations on three and four elements is shown in Figure 7.8. Observe that the permuta-
tions are numbered beginning with 0, not with 1.3 Elements 4 Elements
# Permutation # Permutation # Permutation- 1 2 3 0. 1 2 3 4 12. 3 1 2 4
- 1 3 2 1. 1 2 4 3 13. 3 1 4 2
- 2 1 3 2. 1 3 2 4 14. 3 2 1 4
- 2 3 1 3. 1 3 4 2 15. 3 2 4 1
- 3 1 2 4. 1 4 2 3 16. 3 4 1 2
- 3 2 1 5. 1 4 3 2 17. 3 4 2 1
- 2 1 3 4 18. 4 1 2 3
- 2 1 4 3 19. 4 1 3 2
- 2 3 1 4 20. 4 2 1 3
- 2 3 4 1 21. 4 2 3 1
- 2 4 1 3 22. 4 3 1 2
- 2 4 3 1 23. 4 3 2 1
Figure 7.8 Lexicographical Ordering of Permutations.