edited by
7,744 views
33 votes
33 votes

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.

  1. 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?
  2. How many multisets can be constructed from n distinct elements? 
edited by

6 Answers

Best answer
33 votes
33 votes

A. There are four places to be filled in the multiset using the $n$ distinct elements. At least one element has to occur exactly twice. That would leave $2$ more places in the multiset. This means, at most 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:
  2. Select this element in $n$ ways.

Fill up the remaining two spots using $2$ distinct elements from the remaining $n−1$ elements in ${}^{(n-1)}C_2$ ways.

Exactly two elements that occur twice each: These two will fill up the multiset.

So, we only have to select two elements out of $n$ in ${}^nC_2$ ways. 
Since, these are mutually exclusive, the total number of ways to form the multiset is: ${}^nC_2 + n. {}^{(n-1)}C_2.$  

B. There are infinite number of sets as $n$ is unbounded. ($\because$ size of multiset is not given)

ref: http://cs.stackexchange.com/questions/7578/multisets-of-a-given-set

edited by
15 votes
15 votes

a)There are n distinct elements

Now, we have to find at least one element occurs exactly twice

For example, multiset could be {1,1,2,2} or {1,1,2,3}

As it is construction of a set arrangement not required.

For 1st one where both elements repeats , multiset could be $ \binom{n}{2}$

For 2nd one where only one element repeates, multiset could be $ \binom{n}{3}.\binom{3}{1}$

So, we will just permute when total number of multiset where " at least one element occurs exactly twice "$=^{n}\textrm{C}_{2}+3.^{n}\textrm{C}_{3}$

b)It will be infinite

edited by
2 votes
2 votes
4 places to be filled..

1 element exactly twice is must..

so choose 1 element from n => nC1=n ways

rest remaining 2 places , n-1 elements

so (n-1)^2 permutations, but a,b and b,a are same..

so n * 1/2 * (n-1)^2

= n(n-1)(n-1)/2

Related questions

39 votes
39 votes
6 answers
1
Kathleen asked Sep 14, 2014
9,898 views
The minimum number of cards to be dealt from an arbitrarily shuffled deck of $52$ cards to guarantee that three cards are from same suit is$3$$8$$9$$12$