Page 446 - Discrete Mathematics and Its Applications

6.5 Generalized Permutations and Combinations 425

$
$
1
10
$ $ ** ***
$ $
$

$
$ $ $
100 50 20 $ 5 ** ** *
$ $ $
$

$
$ $ $
100 10 $ 2 1 * ** * *
$ $ $
$

FIGURE 2 Examples of Ways to Select Five Bills.

objects, which can be done in C(11, 5) ways. Consequently, there are

11!
C(11, 5) = = 462
5! 6!

ways to choose five bills from the cash box with seven types of bills. ▲

Theorem 2 generalizes this discussion.

THEOREM 2 There are C(n + r − 1,r) = C(n + r − 1,n − 1)r-combinations from a set with n elements
when repetition of elements is allowed.

Proof: Each r-combination of a set with n elements when repetition is allowed can be rep-
resented by a list of n − 1 bars and r stars. The n − 1 bars are used to mark off n different
cells, with the ith cell containing a star for each time the ith element of the set occurs in the
combination. For instance, a 6-combination of a set with four elements is represented with three
bars and six stars. Here

∗∗|∗| |∗ ∗ ∗
represents the combination containing exactly two of the first element, one of the second element,
none of the third element, and three of the fourth element of the set.
As we have seen, each different list containing n − 1 bars and r stars corresponds to an
r-combination of the set with n elements, when repetition is allowed. The number of such lists
is C(n − 1 + r, r), because each list corresponds to a choice of the r positions to place the r
stars from the n − 1 + r positions that contain r stars and n − 1 bars. The number of such lists
is also equal to C(n − 1 + r, n − 1), because each list corresponds to a choice of the n − 1
positions to place the n − 1 bars.

Examples 4–6 show how Theorem 2 is applied.