Page 584 - Discrete Mathematics and Its Applications

8.6 Applications of Inclusion–Exclusion 563

where N is the number of permutations of n elements. This equation states that the number of
permutations that fix no elements equals the total number of permutations, less the number that
fix at least one element, plus the number that fix at least two elements, less the number that fix
at least three elements, and so on. All the quantities that occur on the right-hand side of this
equation will now be found.

First, note that N = n!, because N is simply the total number of permutations of n elements.
Also, N(P i ) = (n − 1)!. This follows from the product rule, because N(P i ) is the number of
permutations that fix element i, so the ith position of the permutation is determined, but each
of the remaining positions can be filled arbitrarily. Similarly,

N(P i P j ) = (n − 2)!,

because this is the number of permutations that fix elements i and j, but where the
other n − 2 elements can be arranged arbitrarily. In general, note that

) = (n − m)!,
P ...P i m
N(P i 1 i 2
because this is the number of permutations that fix elements i 1 ,i 2 ,...,i m , but where the
other n − m elements can be arranged arbitrarily. Because there are C(n, m) ways to choose m
elements from n, it follows that

N(P i ) = C(n, 1)(n − 1)!,
1≤i≤n

N(P i P j ) = C(n, 2)(n − 2)!,
1≤i<j≤n

and in general,

) = C(n, m)(n − m)!.
N(P i 1 i 2
P ...P i m
1≤i 1 <i 2 <···<i m ≤n
Consequently, inserting these quantities into our formula for D n gives

n
D n = n!− C(n, 1)(n − 1)!+ C(n, 2)(n − 2)! − ··· + (−1) C(n, n)(n − n)!
n! n! n n!
= n!− (n − 1)!+ (n − 2)! − ··· + (−1) 0!.
1!(n − 1)! 2!(n − 2)! n! 0!

Simplifying this expression gives

1 1 1

D n = n! 1 − + − ··· + (−1) n .
1! 2! n!

HISTORICAL NOTE In rencontres (matches), an old French card game, the 52 cards in a deck are laid out
in a row. The cards of a second deck are laid out with one card of the second deck on top of each card of
the first deck. The score is determined by counting the number of matching cards in the two decks. In 1708
Pierre Raymond de Montmort (1678–1719) posed le problème de rencontres: What is the probability that no
matches take place in the game of rencontres? The solution to Montmort’s problem is the probability that a
randomly selected permutation of 52 objects is a derangement, namely, D 52 /52!, which, as we will see, is
approximately 1/e.