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:
- Exactly one element occurs exactly twice: Select this element in ${nchoose{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.
- 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 ${nchoose 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
