# Multisubsets Bijection

• Aug 21st 2011, 09:10 AM
AkilMAI
Multisubsets Bijection
I'm doing some warm-up for the starting of the next year.I came across this problem but unfortunately I don't know how to do it but I"m curious how.Any help will be appreciated.Thank you.
Let Z* denote the nonnegative integers,and S be the set:
{(y1,y2,y3,y4,y5) |yi belongs to Z*,y1+y2+y3+y4=11}.
I must.
a)Define a bijection from S to the set of all 11-element multisubset of the set {1,2,3,4,5}.,showing that the defined function is a bijection.
b)Find the size of S
c)How many elements (y1,y2,y3,y4,y5) of S have yi>=1?
d)How many elements (y1,y2,y3,y4,y5) of S have yi>=2?
• Aug 21st 2011, 10:07 AM
Plato
Re: Multisubsets Bijection
Quote:

Originally Posted by AkilMAI
Let Z* denote the nonnegative integers,and S be the set: {(y1,y2,y3,y4,y5) |yi belongs to Z*,y1+y2+y3+y4=11}.
a)Define a bijection from S to the set of all 11-element multisubset of the set {1,2,3,4,5}.,showing that the defined function is a bijection.
b)Find the size of S
c)How many elements (y1,y2,y3,y4,y5) of S have yi>=1?
d)How many elements (y1,y2,y3,y4,y5) of S have yi>=2?

I cannot help with part a) because I don't understand the part in blue.
Can you define "the set of all 11-element multisubset of the set {1,2,3,4,5}"?

b) This is just counting the number of 5-tuples whose sum of entries is 11: \$\displaystyle \binom{11+5-1}{11}\$.

c) use the formula in b) with this mind trick, think of starting with a one in each variable. So instead of 11 we use 6.
• Aug 21st 2011, 10:54 AM
AkilMAI
Re: Multisubsets Bijection
I got it for the first part.Let's call the multisubset T.Take an element
of T (a k-element multisubset of {1, 2, 3, . . . , n}), and arrange its elements in ascending
order, such as 1, 1, 2, 4, 4, 5, 7, 7, 7, 9, 9 (k = 11). We map this to an element of S, by adding 0
to the 1st element, 1 to the 2nd element, 2 to the 3rd element, and so on, until finally adding
k − 1 to the kth element. (so we get 1, 2, 4, 7, 8, 10, 13, 14, 15, 18, 19).Inversing the map should mean just to inverse the order.

S is not a multisubset but we are the using formula for a multisubset to define its size.Why?
Also why 6 elements instead of 11 because there are 5 variables?
• Aug 21st 2011, 11:37 AM
Plato
Re: Multisubsets Bijection
Quote:

Originally Posted by AkilMAI
S is not a multisubset but we are the using formula for a multisubset to define its size.Why? Also why 6 elements instead of 11 because there are 5 variables?

Well \$\displaystyle S=\{(y_1,y_2,y_3,y_4,y_5):~y_1+y_2+y_3+y_4+y_5=11 \}\$ As before that is a set of 5-tuples whose coordinates add up to eleven. The number of non-negative solutions to \$\displaystyle y_1+y_2+y_3+y_4+y_5=11\$ is found by the multi-set counting formula. That is, count the number of ways to put 11 identical 1's into five different cells.

If we want \$\displaystyle y_i\ge 1\$ go ahead put a 1 in each of the five cells and then count the number of ways to handle the other six.
• Aug 21st 2011, 11:40 AM
AkilMAI
Re: Multisubsets Bijection
oh yes that is true......thank you