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 

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

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}$