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://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}
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
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
@srestha
edit your answer..it is not correct.
you don't have to permute elements in a set.
and in your 2nd case once u chose 3 elements out of n then again you have to choose one out of 3 for repetition. ==> $3*(^nC_3)$
So final answer $= (^nC_2)+3* (^nC_3)$
@Verma Ashish yes this answer is wrong. Your approach is right.
at least can be broken down into exactly.
exactly 1 repeat OR exactly 2 repeats = nC3 (select any 3) * 3C1(select 1 among three to repeat) + nC2 (both repeats)
For 1st one where both elements repeats , multiset could be
$^n C_2$
For 2nd one where only one element repeates, multiset could be
$^nC_3*^3C_1$
a. no of the multiset of length 4 such that at least one element is repeated. n^4 - n(n-1)(n-2)(n-3) b. length 0 :nC0 length 1 : nC1 lenth 2 : nC1+nC2 . . . lenth n :nC1+nC2+........ nCn
total = 1+(n)nC1+(n-1)nC2+..........+nCn