Discrete Mathematics Multiple Choice Questions on “Counting – Division of Objects”.
1. For a gaming competition, 8 girls are planning on splitting up into 3 (non-empty) groups. How many ways can they split up into these groups?
a) 465
b) 1056
c) 966
d) 3215
Answer: c
Clarification: Using the inclusion-exclusion principle, the total number of ways of splitting the girls into 3 groups is 38 + 3.(28) + 3.(18). However, since the three groups are identical we need to divide by 3!. Hence, the answer is 966.
2. In a picnic with 20 persons where 6 chocolates will be given to the top 8 children(the chocolates are distinct: first, second). How many ways can this be done?
a) 18C6
b) 20P6
c) 25C4 * 6!
d) 19P5
Answer: b
Clarification: This is a permutation problem since the chocolates are distinct. The answer is P(20, 6) -> the number of ways to arrange 20 things taken 6 at a time -> which is (frac{20!}{(20-6)!}) = 20*19*18*17*16*15.
3. How many ways can one choose 20 cookies from 45 different types (assuming there are at least 20 of each type)?
a) 64C21 * 15
b) 64C20
c) 44C20 * 2!
d) 65C22
Answer: b
Clarification: Imagine the 20 cookies one is choosing are indistinguishable dots. The 45 different types of cookies are like 45 distinguishable boxes and so the answer is C(45 + 20-1, 20) = 64C20.
4. Assume that it is an afternoon. What is the time on the 24 hour clock after 146 hours?
a) 12:10 pm
b) 8:30 am
c) 3 am
d) 2 pm
Answer: d
Clarification: Divide 146 with 24. The remainder is the time on the 24 hour clock. So, 146 = 6*24 + 2 and the result is 2pm.
5. There are 28 identical oranges that are to be distributed among 8 distinct girls. How many ways are there to distribute the oranges?
a) 22P7
b) 34C6
c) 35C7
d) 28C8
Answer: c
Clarification: By the definition of star and bar problem, there are n+r-1Cr-1 possible distributions of n identical objects among r distinct bins. Now, there are n = 28 identical objects and r = 8 distinct bins. Using the formula above, there are 35C7 ways to distribute the oranges.
6. There are 5 distinct fruits. How many ways can they be planted into identical fruit plants?
a) 87
b) 52
c) 76
d) 128
Answer: b
Clarification: These fruits can be placed into 1, 2, 3, 4 or 5 fruit plants. The number of distributions of fruits into fruit plants will thus be the sum of Stirling numbers of the second kind: S(5,1) + S(5,2) + S(5,3) + S(5,4) + S(5,5) = 1 + 15 + 25 + 10 + 1 = 52.
7. A woman has 14 identical pens to distribute among a group of 10 distinct students. How many ways are there to distribute the 14 pens such that each student gets at least one pencil?
a) 15C10
b) 10C5 * 11
c) 15C8 * 4!
d) 13C9
Answer: d
Clarification: For this type of problem, n>=r must be true and so according to stars and bars model, the number of possible arrangements of stars and bars is n-1Cr-1 or equivalently, there are n-1Cr-1 distributions of n identical objects into r distinct non-empty bins. In this example, there are n = 14 identical objects to be distributed among r=10 distinct bins. Using the above formula, the number of possible distributions is 13C9.
8. Suppose that M is the product of k distinct primes. Find the number of ways to write N as the product of positive integers(>1), where the order of terms does not matter.
a) MCN-k
b) NCM
c) N * Bk
d) Bk
Answer: d
Clarification: To solve the problem first find the prime factorization of each term of the product, and place the factors of each term into a box. Then, since N is the product of distinct prime factors, each prime factor appears in a unique box. Since the product of all of these terms is N, each prime factor must be in a box. Conversely, for any arrangement of these n distinct primes into r identical boxes, multiply the primes in a box to create a term and the product of these terms results in N. This establishes the bijection and the number of ways is Bk which is Bell number.
9. How many ways are there to place 7 differently colored toys into 5 identical urns if the urns can be empty? Note that all balls have to be used.
a) 320
b) 438
c) 1287
d) 855
Answer: d
Clarification: The problem can be described as distinct objects into any number of identical bins and this number can be found with B7 = ∑S(7,k), where S(7,k) is the number of distributions of 5 distinct objects into k identical non-empty bins, so that S(7,1) = 1, S(7,2) = 63, S(7,3) = 301, S(7,4) = 350 and S(7,5) = 140. These values can be found using the recurrence relation identity for Stirling numbers of the second kind. Thus, B7 = 1 + 63 + 301 + 350 + 140 = 855.
10. Suppose, there are 7 of your friends who want to eat pizza (8 distinct people in total). You order a 16-cut pizza (16 identical slices). How many distributions of pizza slices are there if each person gets at least one slice of pizza?
a) 346
b) 6435
c) 3214
d) 765
Answer: b
Clarification: This problem can be viewed as identical objects distributed into distinct non-empty bins. Using the formula for these kind of distributions n-1Cr-1 = 15C7 = 6435. Thus, there are distributions of the pizza slices.