Discrete Computational Structures Assignment #10

CS 230 : Discrete Computational Structures

Assignment #10

Suggested Reading: Rosen Sections 6.4 - 6.5.
These are the problems that you need to turn in. Always explain your answers and show your
reasoning. Spend time giving a complete solution. You will be graded based on how
well you explain your answers. Just correct answers will not be enough!
1. [5 Pts] Prove, using a combinatorial argument, that C(m + n, 2) = C(m, 2) + C(n, 2) + mn,
where m, n ≥ 2. To make your combinatorial argument, describe a problem that both the
lhs and rhs expressions count.
(a) I have two raffles: Raffle A with m participants and raffle B with n participants
(b) How many ways are there to pick 2 tickets from raffle A and B pooled? Choose 2 from
m+n
(c) 3 possibilities: pick 2 only from Raffle A or Raffle B, or pick one from each bag
(d) Choose 2 from m + Choose 2 from n + Choose 1 from m and 1 from n
(e) C(m + n, 2) = C(m, 2) + C(n, 2) + mn QED
2. [8 Pts] Prove, (a) using a combinatorial argument, and (b) using an algebraic proof, that
P(n, 3)C(n − 3, k − 3) = C(n, k)P(k, 3).
(a) i. Imagine the LHS, from n writers, is picking three writers for 1st-3rd place then
selecting k − 3 honorable mentions in no particular order from the remaining n − 3
writers.
ii. LHS gurantees 3 winners and k − 3 honorable mentions. This results in k potential
victors.
iii. Imagine RHS is picking k potential winners from n writers and then selecting 1st-3rd
place from that list of k writers, and the k − 3 not chosen are honorable mentions.
iv. This is removing 3 winners from a pool of 3 potential victors. It results in k − 3
honorable mentions and 3 winners.
v. LHS and RHS are the same QED
(b) i. n!
(n−3)! ∗
(n−3)!
(k−3)!(n−3−(k−3))! =
n!
(k)!(n−k)! ∗
k!
(k−3)!
ii. n!
1
∗
1
(k−3)!(n−k)! =
n!
(n−k)! ∗
1
(k−3)!
iii. n!
(n−k)!(k−3)! =
n!
(n−k)!(k−3)! QED
3. [6 Pts] A cookie shop sells 5 different kinds of cookies. How many different ways are there to
choose 16 cookies if (a) you pick at least two of each? (b) you pick at least 4 oatmeal cookies
and at most 4 chocolate chip cookies?
(a) i. 10 cookies already chosen. Choose 6 cookies to place in 5 bins
ii. (6+5−1)!
6!4!
iii. 10!
6!4!
(b) i. Count combos where 4 oatmeal already picked
ii. Subtract where 4 oatmeal already picked AND 5 or more chocolate chips picked
iii. (12+5−1)!
12!4! −
(7+5−1)!
7!4!
iv. 16!
12!4! −
11!
7!4!
4. [9 Pts] How many solutions are there to the equation x1 + x2 + x3 + x4 = 24, where xi
is
a non-negative integer, for all i, if (a) there are no restrictions? (b) x1 > 1, x2 > 2, x3 > 3,
x4 > 4? (c) x1 > 4 and x3 < 5?
(a) i. 24 objects in 4 bins.
ii. (24+4−1)!
24!3!
iii. 27!
24!3!
(b) i. 14 items already placed. choose 10 to place into 4 bins
ii. (10+4−1)!
10!3!
iii. 13!
10!3!
(c) i. 5 objects already placed. Compute that total
ii. Subtract the combinations where x1 > 4 (5 objects placed) AND x3 ≥ 5 (5 objects
placed)
iii. (19+4−1)!
19!3! −
(14+4−1)!
14!3!
iv. 22!
19!3! −
17!
14!3!
5. [10 Pts] How many ways are there to split 30 people into three committees of 5 people each
and five committees of 3 people each if (a) all eight committees have different tasks? (b)
all eight committees have the same task? (c) the three 5-member committees and two of
the 3-member committees are all given the same task while the remaining three 3-member
committees are not given any task yet?
(a) i. 30 choose 5 * 25 choose 5 * 20 choose 5 * 15 choose 3 * 12 choose 3 * 9 choose 3 *
6 choose 3 * 3 choose 3
ii. 30!
5!25! ∗
25!
5!20! ∗
20!
5!15! ∗
15!
3!12! ∗
12!
3!! ∗
9!
3!6! ∗
6!
3!3! ∗
3!
3!0!
iii. 30!
5!5!5!3!3!3!3!3!
(b) i. Each pair of committees of size 5 is interchangeable and each pair of committees of
size 3 is interchangeable. Division Rule on part a answer:
ii. 30!
(5!5!5!∗3!)(3!3!3!3!3!∗5!)
(c) i. Use division rule on committees that are indistinguishable (same/no task)
ii. 30!
(5!5!5!∗3!)(3!3!∗2!)(3!3!3!∗3!)
6. [6 Pts] How many ways are there to pack 6 different books into 6 identical boxes with no
restrictions placed on how many can go in a box (some boxes can be empty)? What if the
books are identical?
(a) i. 6 distinguishable objects in 6 identical bins: 11 Cases enumerated by brute force: 6
— 5,1 — 4,2 — 4,1,1 — 3,3 — 3,2,1 — 3,1,1,1
ii. 6: 6 choose 6 = 1
iii. 5,1: 6 choose 5 ways = 6
iv. 4,2: 6 choose 4 = 6!
4!2! = 15
v. 4,1,1: 6 choose 4 = 6!
4!2! = 15
vi. 3,3: 6 choose 3, division rule to remove duplciates = 6!
3!3!/2 = 10
vii. 3,2,1: 6 choose 3 = 6!
3!3! = 20
viii. 3,1,1,1: 6 choose 3 = 6!
3!3! = 20
ix. 2,2,2: 6 choose 2, division rule to remove duplicates = 6!
2!4!/3 = 5
x. 2,2,1,1: 6 choose 2 = 6!
2!4! = 15
xi. 2,1,1,1,1: 6 choose 2 = 6!
2!4! = 15
xii. 1,1,1,1,1,1: 6 choose 1, division rule to remove duplicates = 6!
1!5!/6 = 1
xiii. 1 + 6 + 15 + 15 + 10 + 20 + 20 + 5 + 15 + 15 + 1 = 123 ways
b) 6 identical objects in 6 identical bins: Just the # of cases! 11 ways
7. [6 Pts] How many ways can we place 12 books on a bookcase with 5 shelves if the books
are (a) indistinguishable copies (b) all distinct? Note that the position of the books on the
shelves matter.
a) 12 identical objects in 5 distinguishable bins: (12+5−1)!
12!4! =
16!
12!4!
b) 12! ways to order the 12 books. There are 13 spots to place 4 divideres 13 ∗ 4 (5 bins).
Every permutation of books has 13 ∗ 4 ways to place the dividers. 12! ∗ 52
For more practice, work on the problems from Rosen Sections 6.4 - 6.5.