280
Sets, Combinatorics, and Probability
In general, if we use the same scheme to represent a combination of r objects out
of n distinct objects with repetition allowed, there must be n − 1 markers to indicate the number of copies of each of the n objects. This gives r + (n − 1) slots to
fill, and we want to know the number of ways to select r of these. Therefore we
want
C(r + n − 1, r) =
(r + n − 1)!
r!(r + n − 1 − r)!
=
(r + n − 1)!
r!(n − 1)!
This agrees with the result in Example 58, where r = 5, n = 3.
We have discussed a number of counting techniques in this chapter. Table 4.2
summarizes the techniques you can apply in various circumstances, although there
may be several legitimate ways to solve any one counting problem.
Practice 35 Six children get one lollipop each from among a selection of red, yellow, and green lollipops. How many sets of lollipops are possible? (We do not care which child gets which.) ■
Table 4.2
You Want to Count the Number of …
Technique to Try
Subsets of an n-element set
Use formula 2
n .
Outcomes of successive events
Multiply the number of outcomes for
each event.
Outcomes of disjoint events
Add the number of outcomes for each
event.
Outcomes given specific choices at
each step
Draw a decision tree and count the
number of paths.
Elements in overlapping sections of
related sets
Use principle of inclusion and exclusion
formula.
Ordered arrangements of r out of n
distinct objects
Use P( n, r ) formula.
Ways to select r out of n distinct
objects
Use C( n, r ) formula.
Ways to select r out of n distinct
objects with repetition allowed
Use C( r + n − 1, r ) formula.
Generating Permutations and Combinations
In a certain county, lottery ticket numbers consist of a sequence (a permutation)
of the 9 digits 1, 2, …, 9. The ticket printing company may or may not know that
9! = 362,880 distinct ticket numbers are possible, but it certainly needs a way to
Sets, Combinatorics, and Probability
In general, if we use the same scheme to represent a combination of r objects out
of n distinct objects with repetition allowed, there must be n − 1 markers to indicate the number of copies of each of the n objects. This gives r + (n − 1) slots to
fill, and we want to know the number of ways to select r of these. Therefore we
want
C(r + n − 1, r) =
(r + n − 1)!
r!(r + n − 1 − r)!
=
(r + n − 1)!
r!(n − 1)!
This agrees with the result in Example 58, where r = 5, n = 3.
We have discussed a number of counting techniques in this chapter. Table 4.2
summarizes the techniques you can apply in various circumstances, although there
may be several legitimate ways to solve any one counting problem.
Practice 35 Six children get one lollipop each from among a selection of red, yellow, and green lollipops. How many sets of lollipops are possible? (We do not care which child gets which.) ■
Table 4.2
You Want to Count the Number of …
Technique to Try
Subsets of an n-element set
Use formula 2
n .
Outcomes of successive events
Multiply the number of outcomes for
each event.
Outcomes of disjoint events
Add the number of outcomes for each
event.
Outcomes given specific choices at
each step
Draw a decision tree and count the
number of paths.
Elements in overlapping sections of
related sets
Use principle of inclusion and exclusion
formula.
Ordered arrangements of r out of n
distinct objects
Use P( n, r ) formula.
Ways to select r out of n distinct
objects
Use C( n, r ) formula.
Ways to select r out of n distinct
objects with repetition allowed
Use C( r + n − 1, r ) formula.
Generating Permutations and Combinations
In a certain county, lottery ticket numbers consist of a sequence (a permutation)
of the 9 digits 1, 2, …, 9. The ticket printing company may or may not know that
9! = 362,880 distinct ticket numbers are possible, but it certainly needs a way to