[Solved]: Multisets of a given set

Problem Detail: 

A multiset is an unordered collection of elements where elements may repeat any number of times. The size of a multiset is the number of elements in it counting repetitions.

(a) What is the number of multisets of size $4$ that can be constructed from $n$ distinct elements so that at least one element occurs exactly twice?

(b) How many multisets can be constructed from $n$ distinct elements?

For part b, infinite is correct.

For part a, taking $n=3$ and elements $\{1,2,3\}$ we have multisets as: $\{1,1,2,2\}, \{1,1,3,3\}, \{1,1,2,3\}, \{2,2,3,3\}, \{2,2,1,3\}, \{3,3,1,2\}$, for a total of $6$.

Similarly for $n=4$ and using elements $\{1,2,3,4\}$, we have $18$ multisets. There must be some formula, or we have to develop one!

I am in particular looking for a formula when there is a restriction on the number occurrences in the multiset.

Asked By : user1771809

Answered By : Paresh

Here is one way to go about your part (a):

There are four places to be filled in the multiset using the $n$ distinct elements. Atleast one element has to occur exactly twice. That would leave 2 more places in the multiset. This means, atmost two elements can occur exactly twice. We can thus divide this into 2 mutually exclusive cases as follows:

1. Exactly one element occurs exactly twice: Select this element in ${n\choose{1}} = n$ ways. Fill up the remaining two spots using 2 distinct elements from the remaining $n-1$ elements in ${{n-1}\choose{2}}$ ways. Overall: $n \cdot {{n-1}\choose{2}} = \frac{n(n-1)(n-2)}{2}$ ways.
2. Exactly two elements that occur twice each: These two will fill up the multiset, so you only have to select two elements out of $n$ in ${n\choose 2} = \frac{n(n-1)}{2}$ ways.

Since these are mutually exclusive, the total number of ways to form the multiset is: $$\frac{n(n-1)(n-2)}{2} + \frac{n(n-1)}{2}$$$$ = \frac{n(n-1)^2}{2}$$

Note, that $n \ge 2$ otherwise no element can be present twice. This is also obvious from the formula (when $n = 0, 1$).

You can check that the formula tallies with your counts.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7578