A multi-set is an unordered collection of elements where elements may repeat any number of times. The size of a multi-set is the number of elements in it, counting repetitions.
THEOREM: The number of k-element multi-sets whose elements all belong to [n] is C(n+k-1,k)
*where [n] is the number of elements in the set and k is the size of multi-set to be formed.
• • • • •
Given [n]=3 and k=5
we get, C(3+5-1,5) = 21.
Thus, the number of multi-sets possible = 21
Alternatively, you can assume the number of times an element added from Y to the multi-set be represented as a,b,c.
then number of ways to form multi-set is number of solutions to the equation a+b+c = 5 (where 0<=a<=5,0<=b<=5,0<=c<=5).
