Page 449 - Discrete Mathematics and Its Applications

428 6 / Counting

positions free. Then the two Cs can be placed in C(4, 2) ways, leaving two free positions. The U
can be placed in C(2, 1) ways, leaving just one position free. Hence E can be placed in C(1, 1)
way. Consequently, from the product rule, the number of different strings that can be made is

7! 4! 2! 1!
C(7, 3)C(4, 2)C(2, 1)C(1, 1) = · · ·
3! 4! 2! 2! 1! 1! 1! 0!
7!
=
3! 2! 1! 1!
= 420 . ▲

We can prove Theorem 3 using the same sort of reasoning as in Example 7.

THEOREM 3 The number of different permutations of n objects, where there are n 1 indistinguishable
objects of type 1, n 2 indistinguishable objects of type 2,..., and n k indistinguishable objects
of type k,is

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

Proof: To determine the number of permutations, first note that the n 1 objects of type one can be
placed among the n positions in C(n, n 1 ) ways, leaving n − n 1 positions free. Then the objects
of type two can be placed in C(n − n 1 ,n 2 ) ways, leaving n − n 1 − n 2 positions free. Continue
placing the objects of type three,..., type k − 1, until at the last stage, n k objects of type k
can be placed in C(n − n 1 − n 2 − ··· − n k−1 ,n k ) ways. Hence, by the product rule, the total
number of different permutations is

C(n, n 1 )C(n − n 1 ,n 2 ) ··· C(n − n 1 − ··· − n k−1 ,n k )

n! (n − n 1 )! (n − n 1 − ··· − n k−1 )!
= ···
n 1 ! (n − n 1 )! n 2 ! (n − n 1 − n 2 )! n k ! 0!
n!
= .
n 1 ! n 2 !··· n k !

Distributing Objects into Boxes

Many counting problems can be solved by enumerating the ways objects can be placed into boxes
(where the order these objects are placed into the boxes does not matter). The objects can be
either distinguishable, that is, different from each other, or indistinguishable, that is, considered
identical. Distinguishable objects are sometimes said to be labeled, whereas indistinguishable
objects are said to be unlabeled. Similarly, boxes can be distinguishable, that is, different,
or indinguishable, that is, identical. Distinguishable boxes are often said to be labeled, while
indistinguishable boxes are said to be unlabeled. When you solve a counting problem using
the model of distributing objects into boxes, you need to determine whether the objects are
distinguishable and whether the boxes are distinguishable. Although the context of the counting
problem makes these two decisions clear, counting problems are sometimes ambiguous and it
may be unclear which model applies. In such a case it is best to state whatever assumptions you
are making and explain why the particular model you choose conforms to your assumptions.