GATE CSE 2000 | Question: 5

Question

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? 

Comments

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

---

Shouldn’t the answer to the part (b) be  (e^n) -1     

reason-

multiset of size 1=    n

multiset of size 2=  n^2/ 2!

multiset of size 3=   n^3/3!

multiset of size 4=  n^4/ 4!

……….

multiset of size n=  n^n/ n! ……

thus it equals exponential   (e^n) -1 

---

Detailed Video Explanation with Complete Analysis: https://youtu.be/flD8YuOU2VI?t=1959&feature=shared

Answer 1

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

Comments

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

---

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

---

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

---

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 nC2 ways. 

Isn’t this 2*nC2 because they can also shuffle.  like –  AABB   or  BBAA

---

@ASNR1010 order of elements doesnot matter once they are inserted in a multiset.

---

@Pranay Datta 1 @Arjun 

why n is multiplied with (n-1)C2. 

(Is this any formula)

---

For part a, taking n=3 and elements {1,2,3} we have multisets as:

{1,1,2,2},{1,1,3,3},{1,1,2,3},{2,2,3,3},{2,2,1,3},{3,3,1,2}, for a total of 6.

Similarly for n=4and using elements {1,2,3,4}, we have 18 multisets.

---

bcoz we chose one element out of n (which will occur exactly twice)
so remaining elements are (n-1) and we have to fill 2 places .
(2 places are reamaining b'coz the first element which we chose will be repeated twice taking up 2 size out of 4 leaving choice only for 2 places)

---

shouldn't the case of only 1 element occuring twice be multiplied by 3 as

Case 1

{ 1, 1, 2, 3 }

Case 2

{ 1, 2, 2, 3 }

Case 3

{ 1, 2, 3, 3 }

 

wouldn't these make the sets different since it mentions unordered sets but not distinct element sets

 

---

thank you nice explaination @Pranay Datta 1

---

@Amoljadhav 13 dec combinatoriccs day :) for u for me today :P

---

ha ha yes :)) @꧁༒☬ĿọŗԀ 🆂🅷🅸🆅🅰☬༒꧂

Answer 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

Comments

It depends on how u want to construct the multiset.

---

Ok ma'am, got it

---

@srestha

For 1st one where both elements repeats , multiset could be (nC2)

Isn’t this 2*nC2 because they can also shuffle.  like –  AABB   or  BBAA ??

Answer 3

For part(A):- 

 

Comments

nice answer

Answer 4

The question says: “ ...at least one element occurs exactly twice.”

Case 1: one element repeat twice and the other two elements are distinct, as in {1,1,2,3}

Here we choose one element from n elements for repetition

and rest two distinct elements from the remaining (n-1) elements

Hence the number of ways: $\binom{n}{1}.\binom{n-1}{2}$

Case 2: two elements repeat twice, as in {1,1,2,2}

Here we choose two distinct elements from n elements for repetition

Hence the number of ways : $\binom{n}{2}$

By the fundamental principle of counting, the required answer is $\binom{n}{1}.\binom{n-1}{2} +\binom{n}{2}$

 

Answer 5

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

Answer 6

Yes for B the answer will be infinite but if there is a restriction that: the size of multiset can't exceed 'n' then we can generalize it in terms of n.

Here first I have selected i elements to be present in the multiset, then if i<k then these must be some element repeated here so this is equivalent to making partitions or distributing K identical balls into 'i' distinct boxes so that every box has atleast one ball. Hence k-1Ci-1, then the limits are simple i goes from 1 to k and k goes from 1 to n. 
Assumptions:- The size of multiset can't exceed n.