## Description

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.