Page 445 - Discrete Mathematics and Its Applications

424 6 / Counting

Combinations with Repetition

Consider these examples of combinations with repetition of elements allowed.

EXAMPLE 2 How many ways are there to select four pieces of fruit from a bowl containing apples, oranges,
and pears if the order in which the pieces are selected does not matter, only the type of fruit and
not the individual piece matters, and there are at least four pieces of each type of fruit in the
bowl?

Solution: To solve this problem we list all the ways possible to select the fruit. There are 15
ways:
4 apples 4 oranges 4 pears
3 apples, 1 orange 3 apples, 1 pear 3 oranges, 1 apple
3 oranges, 1 pear 3 pears, 1 apple 3 pears, 1 orange
2 apples, 2 oranges 2 apples, 2 pears 2 oranges, 2 pears
2 apples, 1 orange, 1 pear 2 oranges, 1 apple, 1 pear 2 pears, 1 apple, 1 orange
The solution is the number of 4-combinations with repetition allowed from a three-element set,
{apple, orange, pear}. ▲

To solve more complex counting problems of this type, we need a general method for
counting the r-combinations of an n-element set. In Example 3 we will illustrate such a method.

EXAMPLE 3 How many ways are there to select five bills from a cash box containing $1 bills, $2 bills, $5
bills, $10 bills, $20 bills, $50 bills, and $100 bills? Assume that the order in which the bills are
chosen does not matter, that the bills of each denomination are indistinguishable, and that there
are at least five bills of each type.

Solution: Because the order in which the bills are selected does not matter and seven dif-
ferent types of bills can be selected as many as five times, this problem involves counting
5-combinations with repetition allowed from a set with seven elements. Listing all possibilities
would be tedious, because there are a large number of solutions. Instead, we will illustrate the
use of a technique for counting combinations with repetition allowed.
Suppose that a cash box has seven compartments, one to hold each type of bill, as illustrated
in Figure 1. These compartments are separated by six dividers, as shown in the picture. The
choice of five bills corresponds to placing five markers in the compartments holding different
types of bills. Figure 2 illustrates this correspondence for three different ways to select five bills,
where the six dividers are represented by bars and the five bills by stars.
The number of ways to select five bills corresponds to the number of ways to arrange six
bars and five stars in a row with a total of 11 positions. Consequently, the number of ways to
select the five bills is the number of ways to select the positions of the five stars from the 11
positions. This corresponds to the number of unordered selections of 5 objects from a set of 11

$100 $50 $20 $10 $5 $2 $1

FIGURE 1 Cash Box with Seven Types of Bills.