Question

The size of a multiset is 6 which is equal to the number of elements in it with counting repetitions (a multiset is an unordered collection of elements where the elements may repeat any number of times). Determine the number of multisets can be grouped from n distinct elements so that at least one element occurs exactly twice?

(a) 326

(b) 28

(c) 45

(d) 62

This question was posed to me during an interview for a job.

Question is from Counting topic in section Counting of Discrete Mathematics

Answer 1

Correct option is (c) 45

To elaborate: There are six places to be filled in the multiset using the n distinct elements. At least one element has to occur exactly twice and that would leave 4 more places in the multiset means that at most four elements can occur exactly once. Thus there are two mutually exclusive cases as follows: 1) Exactly one element occurs exactly twice and select this element in n ways. Fill up the remaining four spots using 5 distinct elements from the remaining n−1 elements in ^n-1C4 ways. 2) Exactly four elements that occur at least once each. Hence, the total number of ways to form the multiset is

^nC2 + n * ^n-1C4 = ^6C2 + 6 * ^6-1C4 = 45.