n.n. (n-1)(n-2) multisets

all distinct elements :-

n.(n-1).(n-2).(n-3) multisets

is i am right ?

3,928 views

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.

- 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?
- How many multisets can be constructed from n distinct elements?

Best answer

**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:

- Exactly one element occurs exactly twice:
- 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

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 have a different approach.But It is not giving right answer.Please point out my mistake.

Here am using combinations with repetition approach.

{_ _ _ _}

first two am dedicating for exactly two ad per given question. so first two can be filled using C(n,1).

and last two can be filled with n-1 elements in either both repeat or both are distinct.

Its like mapping this problem into integral solution...x2+x3+.....xn= 2.

so V(n-1,2)= C(n-1-1+2,2)

so am getting second half can be filled with C(n,2) ways.

so total n*nC2.

please help where am I doing redundant counting?

Here am using combinations with repetition approach.

{_ _ _ _}

first two am dedicating for exactly two ad per given question. so first two can be filled using C(n,1).

and last two can be filled with n-1 elements in either both repeat or both are distinct.

Its like mapping this problem into integral solution...x2+x3+.....xn= 2.

so V(n-1,2)= C(n-1-1+2,2)

so am getting second half can be filled with C(n,2) ways.

so total n*nC2.

please help where am I doing redundant counting?

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.**

@Abhi Girin

In your approach, you are overcounting the cases when there are 2 elements repeated exactly 2 times.

To overcome this with the same approach you have taken, first count the (2, 1, 1) cases as follows:

(nC1) * (nC2 - (n - 1))

Here we are subtracting n - 1 because we only want one element to appear exactly twice.

Then to the above, add nC2 for (2, 2) cases.

Final answer will be (nC1) * (nC2 - (n - 1)) + (nC2) = n*((n-1)^2)/2

In your approach, you are overcounting the cases when there are 2 elements repeated exactly 2 times.

To overcome this with the same approach you have taken, first count the (2, 1, 1) cases as follows:

(nC1) * (nC2 - (n - 1))

Here we are subtracting n - 1 because we only want one element to appear exactly twice.

Then to the above, add nC2 for (2, 2) cases.

Final answer will be (nC1) * (nC2 - (n - 1)) + (nC2) = n*((n-1)^2)/2

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.

Srestha , here i didn't get what do you want to say.

{1,1,2,3}? if you're talking about elements 1,1,2,3 , then there is condition that all n elements are distinct and pardon me but i think your answer is wrong.

you can see when i take n=3 , total possibilities are 6 , while your answer is producing something different. if you can justify your answer in detail , i can find who is doing mistake.

{1,1,2,3}? if you're talking about elements 1,1,2,3 , then there is condition that all n elements are distinct and pardon me but i think your answer is wrong.

you can see when i take n=3 , total possibilities are 6 , while your answer is producing something different. if you can justify your answer in detail , i can find who is doing mistake.

@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)

Search GATE Overflow