Page 450 - Discrete Mathematics and Its Applications

6.5 Generalized Permutations and Combinations 429

We will see that there are closed formulae for counting the ways to distribute objects,
distinguishable or indistinguishable, into distinguishable boxes. We are not so lucky when we
count the ways to distribute objects, distinguishable or indistinguishable, into indistinguishable
boxes; there are no closed formulae to use in these cases.

DISTINGUISHABLE OBJECTS AND DISTINGUISHABLE BOXES We first consider the
case when distinguishable objects are placed into distinguishable boxes. Consider Example 8
in which the objects are cards and the boxes are hands of players.

EXAMPLE 8 How many ways are there to distribute hands of 5 cards to each of four players from the standard
deck of 52 cards?

Solution: We will use the product rule to solve this problem. To begin, note that the first player
can be dealt 5 cards in C(52, 5) ways. The second player can be dealt 5 cards in C(47, 5) ways,
because only 47 cards are left. The third player can be dealt 5 cards in C(42, 5) ways. Finally,
the fourth player can be dealt 5 cards in C(37, 5) ways. Hence, the total number of ways to deal
four players 5 cards each is

52! 47! 42! 37!
C(52, 5)C(47, 5)C(42, 5)C(37, 5) = · · ·
47! 5! 42! 5! 37! 5! 32! 5!
52!
= .
5! 5! 5! 5! 32! ▲

Remark: The solution to Example 8 equals the number of permutations of 52 objects, with 5 in-
distinguishable objects of each of four different types, and 32 objects of a fifth type. This equality
can be seen by defining a one-to-one correspondence between permutations of this type and dis-
tributions of cards to the players. To define this correspondence, first order the cards from 1 to 52.
Then cards dealt to the first player correspond to the cards in the positions assigned to objects of
the first type in the permutation. Similarly, cards dealt to the second, third, and fourth players, re-
spectively, correspond to cards in the positions assigned to objects of the second, third, and fourth
type, respectively. The cards not dealt to any player correspond to cards in the positions assigned
to objects of the fifth type. The reader should verify that this is a one-to-one correspondence.

Example 8 is a typical problem that involves distributing distinguishable objects into dis-
tinguishable boxes. The distinguishable objects are the 52 cards, and the five distinguishable
boxes are the hands of the four players and the rest of the deck. Counting problems that involve
distributing distinguishable objects into boxes can be solved using Theorem 4.

THEOREM 4 The number of ways to distribute n distinguishable objects into k distinguishable boxes so
that n i objects are placed into box i, i = 1, 2,...,k, equals

n!
.
n 1 ! n 2 !··· n k !

Theorem 4 can be proved using the product rule. We leave the details as Exercise 47. It can also
be proved (see Exercise 48) by setting up a one-to-one correspondence between the permutations
counted by Theorem 3 and the ways to distribute objects counted by Theorem 4.

INDISTINGUISHABLE OBJECTS AND DISTINGUISHABLE BOXES Counting the
number of ways of placing n indistinguishable objects into k distinguishable boxes turns out to
be the same as counting the number of n-combinations for a set with k elements when repeti-
tions are allowed. The reason behind this is that there is a one-to-one correspondence between