Discrete Mathematics for Computer Science

Permutations and Combinations 445

Solution. First determine all the different cases that are possible, and then count the num-
ber of hands for each separate case. Finally, add up the counts for each case to get the total
count required. The different cases are listed in Table 7.3.

Table 7.3 Distribution of Aces and Kings

# of Aces Possible # of Kings

0 No hand possible

1 0

2 0or I

3 0orl or2

4 0 or 1, since the hand has only five cards

There are eight subcases for which the number of hands must be counted. The count
for each of these cases is given in Table 7.4.

Table 7.4 Number of Hands with Given Aces and Kings

# of Aces # of Kings Aces Kings Other Cards # of Hands

1 0 C(4, 1)- C(44,4) = 543,004

2 0 C(4, 2) - C(44, 3) = 79,464

2 1 C(4,2). C(4, 1). C(44,2) =22,704

3 0 C(4, 3) • C(44,2) = 3784

3 1 C(4,3)- C(4, 1). C(44, 1) =704

3 2 C(4,3). C(4,2) =24

4 0 C(4, 4) • C(44, 1) =^44

4 1 C(4,4)- C(4, 1) =4

The answer is the sum of the number of hands in each of the eight subcases, which is
649,732. N

In Example 11, we saw how the Multiplication Principle was first used in each case
and then how the Addition Principle was used to find the total number for all cases. This
analysis proceeded fairly directly, because we first split all the cases into disjoint subsets
so that each of the possible hands being counted arose in one and only one of the subcases.

Using the Principle of Inclusion-Exclusion

In many problems, it is not particularly easy to verify that a set of subsets are pairwise
disjoint. If you want to count the number of elements in the union of such subsets, the
Principle of Inclusion-Exclusion is often useful as a proof technique.
Let X = {x1, X2 ... , xn} be a set. A permutation y y2 .. y., y, of the elements of X
has a fixed point, or fixes, xi if yi = xi for some i where 1 < i < n. A derangement of X
is a permutation of X with no fixed point.

Example 12. Find the number of derangements of a set with three elements.

Solution. Let X = {1, 2, 3}. Let Ai = {permutations of X that fix i} where 1 <

i < 3. To compute I AI U A 2 U A 3 1, we need to compute IA 1, 1A 2 1, JA 3 1, A 1 n A 2 1,