292
Sets, Combinatorics, and Probability
86. At a birthday party, a mother prepares a plate of cookies for 8 children. There are plenty of chocolate chip,
peanut butter, and oatmeal cookies, but each child gets only 1 cookie.
a. How many different plates can be prepared?
b. How many different plates can be prepared if at least 1 of each kind of cookie is given out?
c. How many different plates can be prepared if no one likes oatmeal cookies?
d. How many different plates can be prepared if 2 children insist on getting peanut butter?
e. How many different plates can be prepared if the dog got into the kitchen and ate all the chocolate chip
cookies except 2?
87. On Halloween, 10 identical apples are distributed to 7 children.
a. How many distributions are possible? (Hint: One possible distribution is that child 1 gets 3 apples,
child 2 gets 0 apples, child 3 gets 2 apples, child 4 gets 0 apples, child 5 and child 6 get 1 apple
each, and child 7 gets 3 apples. Although the problem says apples are distributed to children, think of
assigning a child’s name to each apple; a child’s name can go to more than 1 apple.)
b. How many distributions are possible if each child is to receive at least 1 apple?
88. Eight identical antique pie safes are sold at a furniture auction to 3 bidders.
a. In how many ways can the pie safes be distributed among the bidders? (See the hint for Exercise 87.)
b. In how many ways can the pie safes be distributed if bidder A gets only 1 pie safe?
89. How many distinct nonnegative integer solutions are there to the equation
x 1 + x 2 + x 3 + x 4 = 10
where the solution
x 1 = 3, x 2 = 1, x 3 = 4, x 4 = 2
and the solution
x 1 = 4, x 2 = 2, x 3 = 3, x 4 = 1
are distinct? (Hint: Think of this problem as distributing 10 pennies to 4 children; then see the hint in
Exercise 87.)
90. How many distinct nonnegative integer solutions are there to the equation
x 1 + x 2 + x 3 = 7
in which x 1 ≥ 3? (See the hint for Exercise 89.)
91. Prove that for n ≥ 1, P(n, n) = P(n, n − 1). (The proof does not require induction, even though it sounds
like a very likely candidate for induction.)
92. Prove that for n ≥ 2, P(n, 1) + P(n, 2) = n
2
.
93. Prove that for any n and r with 0 ≤ r ≤ n, C(n, r) = C(n, n − r). Explain why this is intuitively true.
94. Prove that for any n and r with 0 ≤ r ≤ n, C(n, 2) = C(r, 2) + C(n − r, 2) + r(n − r).
95. Prove the identity
C(n, r)C(r, k) = C(r, k)C(n − k, r − k) for r ≤ n and k ≤ r
Give a combinatorial argument.
Sets, Combinatorics, and Probability
86. At a birthday party, a mother prepares a plate of cookies for 8 children. There are plenty of chocolate chip,
peanut butter, and oatmeal cookies, but each child gets only 1 cookie.
a. How many different plates can be prepared?
b. How many different plates can be prepared if at least 1 of each kind of cookie is given out?
c. How many different plates can be prepared if no one likes oatmeal cookies?
d. How many different plates can be prepared if 2 children insist on getting peanut butter?
e. How many different plates can be prepared if the dog got into the kitchen and ate all the chocolate chip
cookies except 2?
87. On Halloween, 10 identical apples are distributed to 7 children.
a. How many distributions are possible? (Hint: One possible distribution is that child 1 gets 3 apples,
child 2 gets 0 apples, child 3 gets 2 apples, child 4 gets 0 apples, child 5 and child 6 get 1 apple
each, and child 7 gets 3 apples. Although the problem says apples are distributed to children, think of
assigning a child’s name to each apple; a child’s name can go to more than 1 apple.)
b. How many distributions are possible if each child is to receive at least 1 apple?
88. Eight identical antique pie safes are sold at a furniture auction to 3 bidders.
a. In how many ways can the pie safes be distributed among the bidders? (See the hint for Exercise 87.)
b. In how many ways can the pie safes be distributed if bidder A gets only 1 pie safe?
89. How many distinct nonnegative integer solutions are there to the equation
x 1 + x 2 + x 3 + x 4 = 10
where the solution
x 1 = 3, x 2 = 1, x 3 = 4, x 4 = 2
and the solution
x 1 = 4, x 2 = 2, x 3 = 3, x 4 = 1
are distinct? (Hint: Think of this problem as distributing 10 pennies to 4 children; then see the hint in
Exercise 87.)
90. How many distinct nonnegative integer solutions are there to the equation
x 1 + x 2 + x 3 = 7
in which x 1 ≥ 3? (See the hint for Exercise 89.)
91. Prove that for n ≥ 1, P(n, n) = P(n, n − 1). (The proof does not require induction, even though it sounds
like a very likely candidate for induction.)
92. Prove that for n ≥ 2, P(n, 1) + P(n, 2) = n
2
.
93. Prove that for any n and r with 0 ≤ r ≤ n, C(n, r) = C(n, n − r). Explain why this is intuitively true.
94. Prove that for any n and r with 0 ≤ r ≤ n, C(n, 2) = C(r, 2) + C(n − r, 2) + r(n − r).
95. Prove the identity
C(n, r)C(r, k) = C(r, k)C(n − k, r − k) for r ≤ n and k ≤ r
Give a combinatorial argument.