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

Answer 2

For question a)

 

Case 1: Exactly ONE element occurs exactly twice

This creates a multiset that looks like $\{a, a, b, c\}$.

• Choose 1 element out of $n$ to be the one that repeats twice: $\binom{n}{1}$

• Choose 2 elements out of the remaining $n-1$ to appear once each: $\binom{n-1}{2}$

• Ways for Case 1: $\binom{n}{1} \times \binom{n-1}{2}$

 

 

Case 2: Exactly TWO elements occur exactly twice (The Correction)

This creates a multiset that looks like $\{a, a, b, b\}$.

• Choose 2 elements out of $n$ to repeat twice: $\binom{n}{2}$

• Ways for Case 2: $\binom{n}{2}$
   

Note : We cannot we use the approach of picking one element and then another $\binom{n}{1} \times \binom{n-1}{1}$ , because it overcounts 
example: Suppose we pick first element as 1 and second element as 2 which gives {1,1,2,2,} but since order dosent matter in a multiset if we pick first element as 2 and second element as 1 then it overcounts the same set {1,1,2,2} 

---

For question b)

Answer is infinite.

Take a single element {A} then possible multisets are 

• {A}

• {A, A}

• {A, A, A}

• {A, A, A, A}

• ...and so on, forever.