The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+12 votes
602 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 Set Theory & Algebra by Veteran (68.8k points)
recategorized by | 602 views
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. Atleast one element has to occur exactly twice. That would leave 2 more places in the multiset. This means, atmost two elements can occur exactly twice. We can thus divide this into 2 mutually exclusive cases as follows:

Exactly one element occurs exactly twice:

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

Exactly two elements that occur twice each: These two will fill up the multiset,

so you only have to select two elements out of n in nC
Since these are mutually exclusive, the total number of ways to form the multiset is: nC+ n. (n-1)C 

B) there are infinite number of sets as n is unbounded. 

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

answered by Veteran (10.1k points)
selected by
what if n is bounded??
can you explain b part clearly
+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 (76.6k points)

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.

@Rupendra

how 1 element can repeat?

So nC1 cannot select

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}

@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

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 (49.1k points)
edited by
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

32,442 questions
39,188 answers
108,792 comments
36,561 users