The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+12 votes
744 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? 
asked in Combinatory by Veteran (59.5k points)
edited by | 744 views
0
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 ?

3 Answers

+12 votes
Best answer

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. 

ref: http://http://cs.stackexchange.com/questions/7578/multisets-of-a-given-set

answered by Boss (10.2k points)
selected by
0
what if n is bounded??
0
can you explain b part clearly
0
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..
0
@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....
0
pranay Datta explanation is awesome
+1 vote

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}

For 1st one where both elements repeats , multiset  could be $\left ( \binom{n}{2}.\frac{4!}{2!.2!} \right )$

For 2nd one where only one element repeates, multiset could be $\left ( \binom{n}{3}.\frac{4!}{2!.} \right )$

So, total number of multiset where " at least one element occurs exactly twice "=$\left ( \binom{n}{2}.\frac{4!}{2!.2!} \right )+\left ( \binom{n}{3}.\frac{4!}{2!.} \right )$

b)It will be infinite

answered by Veteran (88.9k points)
0

Hello srestha

I think your answer is wrong.

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.

0

@Rupendra

how 1 element can repeat?

So nC1 cannot select

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

@Rupendra I am pretty sure about this ans

{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

0
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.
0 votes
a.
no of multiset of length 4 such that atleast one element is repeated..
n^4 - n(n-1)(n-2)(n-3)
 
b.
length 0 :1
length 1 : n
lenth 2 : nC2
.
.
.
lenth n : nCn
total = 1+nC1+nC2+..........+nCn
         = 2^n
answered by Veteran (54.9k points)
edited by
0
how can be length 2 is nC2

it will be nC2+n

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

37,118 questions
44,701 answers
127,278 comments
43,765 users