This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses 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

View Answer

Explanation: Using the inclusion-exclusion principle, the total number of ways of splitting the girls into 3 groups is 3

^{8}+ 3.(2

^{8}) + 3.(1

^{8}). 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) ^{18}C_{6}

b) ^{20}P_{6}

c) ^{25}C_{4} * 6!

d) ^{19}P_{5}

View Answer

Explanation: 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) ^{64}C_{21} * 15

b) ^{64}C_{20}

c) ^{44}C_{20} * 2!

d) ^{65}C_{22}

View Answer

Explanation: 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) =

^{64}C

_{20}.

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

View Answer

Explanation: 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) ^{22}P_{7}

b) ^{34}C_{6}

c) ^{35}C_{7}

d) ^{28}C_{8}

View Answer

Explanation: By the definition of star and bar problem, there are

^{n+r-1}C

_{r-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

^{35}C

_{7}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

View Answer

Explanation: 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) ^{15}C_{10}

b) ^{10}C_{5} * 11

c) ^{15}C_{8} * 4!

d) ^{13}C_{9}

View Answer

Explanation: 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-1}C

_{r-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

^{13}C

_{9}.

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) ^{M}C_{N-k}

b) ^{N}C_{M}

c) N * B_{k}

d) B_{k}

View Answer

Explanation: 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 B

_{k}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

View Answer

Explanation: The problem can be described as distinct objects into any number of identical bins and this number can be found with B

_{7}= ∑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, B

_{7}= 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

View Answer

Explanation: This problem can be viewed as identical objects distributed into distinct non-empty bins. Using the formula for these kind of distributions

^{n-1}C

_{r-1}=

^{15}C

_{7}= 6435. Thus, there are distributions of the pizza slices.

**Sanfoundry Global Education & Learning Series – Discrete Mathematics.**

To practice all areas of Discrete Mathematics, __here is complete set of 1000+ Multiple Choice Questions and Answers__.