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.

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?

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.

Re: Multisubsets Bijection

oh yes that is true......thank you