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. 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:
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.
ref: http://http://cs.stackexchange.com/questions/7578/multisets-of-a-given-set
@anchitjindal07
nx (n-1)C2 = n(n-1)(n-2)/2 . Let this be "k".
nC3 = n(n-1)(n-2)/3! = {n(n-1)(n-2)/2}/3 = k/3 which clearly shows that we are missing out something i.e. we are not counting some things.
I am taking an example. Let n=4 and the distinct elements are {1,2,3,4}. We try to make a multiset of size=4.
With nC3 we get 4 combinations like <1,2,3>,<1,2,4>,<1,3,4>,<2,3,4>.
Now for each of these combinations we can have 3 different multisets and this is what nC3 is not including.
For <1,2,3>, multisets can be <1,1,2,3>,<1,2,2,3>,<1,2,3,3>. But instead of 3 only one is counted. Hence we need to multiply 3 with the total no. of combinations obtained.
So 3 x nC3 = n(n-1)(n-2)/2 =k
I didn't get your B point.
There are infinite number of sets as n is unbounded.
First, $n$ is of course not unbounded otherwise the solution of $1st$ doesn't make sense. Actually , number of multisets are unbounded because with $1$ you can create infinite number of sets.
okay n is bounded say n=1 and the set has only one element a.
Multisets are {},{a},{a,a},{a,a,a},{a,a,a,a},{a,a,a,a,a,a}.................... infinite since size of multiset is not fixed.
The question says-
A multiset is an unordered collection of elements where elements may repeat any number of times.
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}
For 1st one where both elements repeats , multiset could be $\left ( \binom{n}{2}.\frac{4!}{2!.2!} \right )$
For 2nd one where only one element repeates, multiset could be $\left ( \binom{n}{3}.\frac{4!}{2!.} \right )$
So, total number of multiset where " at least one element occurs exactly twice "=$\left ( \binom{n}{2}.\frac{4!}{2!.2!} \right )+\left ( \binom{n}{3}.\frac{4!}{2!.} \right )$
b)It will be infinite
Hello srestha
I think your answer is wrong.
case 1) when only one element repeated. choose one out of n ( $\binom{n}{1}$ways ). NOw to fill remaining two places , we have $n-1$ elements so choose any two out of those ($\binom{n-1}{2}$ways ). hope you know , it's basic property of set(even multiset) that order of element doesn't matter. mean S={1,1,2} is same as S={1,2,1}
case 2) if we notice , he said element must appear "exactly" two times , now in that case as we are taking two element with appears with repetition.It can't happen that some element will appear 3 times , either it won't appear or if appear then it will be exactly twice. So choose two out of n means $\binom{n}{2}$ ways.
So i'm agree with pranay datta's answer.
@Rupendra
how 1 element can repeat?
So ^{n}C_{1} cannot select
@Rupendra I am pretty sure about this ans
{1,1,2,3}
now if I do selection according to u then it will be (^{n}C_{1})(^{n-2}C_{2})
though it will depend on given options and also there is no error in my approach too