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.


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.

  • $\begingroup$ one more thing suppose we are given {a,b,c,d} and {1*a,2*b,3*c,5*d} than way to distribute 10 vertices among a,b,c,d ? $\endgroup$ – user1771809 Dec 25 '12 at 13:46
  • $\begingroup$ @user1771809 What do you mean by {1*a,2*b,3*c,5*d}? What do you mean by distribute 10 vertices among a,b,c,d? Please be clearer. And if this is a reasonably different question, you might want to post a separate question too. $\endgroup$ – Paresh Dec 25 '12 at 17:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.