Results 1 to 5 of 5

Math Help - Multisubsets Bijection

  1. #1
    Junior Member
    Joined
    Jan 2011
    Posts
    45

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1581
    Awards
    1

    Re: Multisubsets Bijection

    Quote Originally Posted by AkilMAI View Post
    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: \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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jan 2011
    Posts
    45

    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1581
    Awards
    1

    Re: Multisubsets Bijection

    Quote Originally Posted by AkilMAI View Post
    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 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 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 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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jan 2011
    Posts
    45

    Re: Multisubsets Bijection

    oh yes that is true......thank you
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Bijection
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 6th 2010, 12:58 AM
  2. Bijection
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 23rd 2010, 10:14 AM
  3. bijection of e^x * ln x
    Posted in the Calculus Forum
    Replies: 8
    Last Post: January 20th 2010, 12:46 PM
  4. bijection help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 12th 2009, 07:59 PM
  5. Bijection
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: February 22nd 2006, 02:42 PM

Search Tags


/mathhelpforum @mathhelpforum