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

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

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

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