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.

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?

at least one element can occur twice :-

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

all distinct elements :-

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

is i am right ?

Hints:

• A multiset can be of the form $\{x,x,y,y\}$ or $\{x,x,y,z\}$ or $\{y,x,y,z\}$
• Multiset is an unordered collection

Subscribe to GO Classes for GATE CSE 2022

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)

what if n is bounded??
can you explain b part clearly
In part (a), when we consider only one element appears twice case, why answer is not nC3 since we are selecting total 3 elements out of n..
@anchitjindal if u will take nC3 it will not include all the terms  for example (1,1,3,4)and (1,1,4,5) etc....
pranay Datta explanation is awesome

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.

Infinite, because size of multi-set is not given.

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.

@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

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

by

Hello srestha

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 nC1 cannot select

look S={1,2,3}

case 1) only one element will repeat

total possibilities {1,1,2,3},{2,2,1,3}{3,3,1,2}

case 2) two element will repeat (more than two can't repeat as we have only 4 place)

total possibilities {1,1,2,2}{1,1,3,3}{2,2,3,3}

{1,1,2,3}

now if I do selection according to u then it will be (nC1)(n-2C2)

though it will depend on given options and also there is no error in my approach too

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.

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)

yes edited

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$

yes, I mean it

thanks

@srestha maam,

what if part b has asked for size=4? how can we calculate no. of multisets then?

It depends on how u want to construct the multiset.
Ok ma'am, got it

For part(A):-

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

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