Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 6 down vote accepted

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.

share|improve this answer
    
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 ? –  user1771809 Dec 25 '12 at 13:46
    
@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. –  Paresh Dec 25 '12 at 17:53
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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