400
Relations, Functions, and Matrices
elements in A i for each i. Therefore the first summation in equation (3) adds together terms that are all of the same size. The number of such terms equals the
number of ways to pick one set A i out of the n such sets, or C(n, 1).
In the second summation, the terms count the number of permutations on n
elements that leave two of those elements fixed. There are
(1)(1)(n − 2) c (1) = (n − 2)!
such functions in a given A i d A j, and C(n, 2) ways to choose the two sets out of
n. In general, if there are k sets in the intersection, then k elements must be held
fixed, so there are (n − k)! functions in the intersection set, and there are C(n, k)
ways to choose the k sets to form the intersection. Therefore equation (3) becomes
0 A 1 c c c A n 0 = C(n, 1)(n − 1)! − C(n, 2)(n − 2)! + C(n, 3)(n − 3)!
− c + (−1)
n+1
C(n, n)(n − n)!
This expression represents the number of all possible nonderangement permutations. We subtract this value from the total number of permutation functions,
which is n!:
n! − C(n, 1)(n − 1)! + C(n, 2)(n − 2)! − C(n, 3)(n − 3)!
+ c + (−1)
n
C(n, n)(n − n)!
Rewriting this expression,
n! −
n!
1!(n − 1)!
(n − 1)! +
n!
2!(n − 2)!
(n − 2)! −
n!
3!(n − 3)!
(n − 3)!
+ c + (−1)
n n!
n!0!
0!
= n! −
n!
1!
+
n!
2!
−
n!
3!
+ c + (−1)
n n!
n!
= n! c1 −
1
1!
+
1
2!
−
1
3!
+ c + (−1)
n 1
n!
d
(4)
example 42
For n = 3, Equation (4) says that the number of derangements is
3!a1 −
1
1!
+
1
2!
−
1
3!
b =
3!
2!
−
3!
3!
= 3 − 1 = 2
Written in array form, the two derangements are
a
1 2 3
2 3 1
b
and
a
1 2 3
3 1 2
b