Results 1 to 5 of 5

Math Help - simple question on bijection

  1. #1
    Super Member
    Joined
    Apr 2009
    Posts
    677

    simple question on bijection

    This seems trivial, but I'm getting stuck/confused how to prove it formally. Please help.

    Consider expansions of
    (1+x+...+x^{a_1})(1+x+...+x^{a_2})....(1+x+...+x^{  a_n})

    Let the coefficient of x^N be C

    Let me define a set, S as S=\{(y_1,y_2,...y_n)|x^{y_1+y_2..+y_n}=x^N\}
    Here y_i \in {0,...,a_i}

    I want to show that
    S\cong\{1,2,..,C\}

    I know what's going on behind the scenes, but just not able to express it coherently/rigorusly. I mean I'm not getting a smart bi-jection between the two sets
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,306
    Thanks
    1279
    Quote Originally Posted by aman_cc View Post
    This seems trivial, but I'm getting stuck/confused how to prove it formally. Please help.

    Consider expansions of
    (1+x+...+x^{a_1})(1+x+...+x^{a_2})....(1+x+...+x^{  a_n})

    Let the coefficient of x^N be C

    Let me define a set, S as S=\{(y_1,y_2,...y_n)|x^{y_1+y_2..+y_n}=x^N\}
    Here y_i \in {0,...,a_i}

    I want to show that
    S\cong\{1,2,..,C\}

    I know what's going on behind the scenes, but just not able to express it coherently/rigorusly. I mean I'm not getting a smart bi-jection between the two sets
    Imagine multiplying (1+x+...+x^{a_1})(1+x+...+x^{a_2})....(1+x+...+x^{  a_n}) without "combining like terms". Then Cx^n is precisely a sum of C terms of the form x^{y_1}x^{y_2}\cdot\cdot\cdot x^{y_k} with y_1+ y_2+ \cdot\cdot\cdot+ y_n= k. Write those terms in any order you please and map the first to 1, the second to 2, etc. up to mapping the last one to C.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by HallsofIvy View Post
    Imagine multiplying (1+x+...+x^{a_1})(1+x+...+x^{a_2})....(1+x+...+x^{  a_n}) without "combining like terms". Then Cx^n is precisely a sum of C terms of the form x^{y_1}x^{y_2}\cdot\cdot\cdot x^{y_k} with y_1+ y_2+ \cdot\cdot\cdot+ y_n= k. Write those terms in any order you please and map the first to 1, the second to 2, etc. up to mapping the last one to C.

    Thanks for your answer. But I'm not too convinced about. Not to say that you are not correct, but more so because I think I not framing the question properly/or am getting thoroughly confused .

    I am inclined to ask you what is the guarantee that you will be able to do what you say -
    " Write those terms in any order you please and map the first to 1, the second to 2, etc. up to mapping the last one to C"

    I was thinking on these lines. Isn't this situation exactly similar to the following:
    You have a urn with red and white balls. You pick balls one by one, if it is red you increase a counter(initially set as zero) by 1. Once you exhaust all the balls - the counter will tell you how many red balls were there. So, I need to do three things here:
    a> Establish more formally that the "situations are exactly similar" i.e. the coefficient = counter
    b> Counter indeed is number of balls (i.e. establish a bijection)

    Sorry if I'm messing stuff up - but as you would have guessed I'm struggling to say this in the language of mathematics. I'm unable to establish/prove both the above.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by aman_cc View Post
    This seems trivial, but I'm getting stuck/confused how to prove it formally. Please help.

    Consider expansions of
    (1+x+...+x^{a_1})(1+x+...+x^{a_2})....(1+x+...+x^{  a_n})

    Let the coefficient of x^N be C

    Let me define a set, S as S=\{(y_1,y_2,...y_n)|x^{y_1+y_2..+y_n}=x^N\}
    Here y_i \in {0,...,a_i}

    I want to show that
    S\cong\{1,2,..,C\}

    I know what's going on behind the scenes, but just not able to express it coherently/rigorusly. I mean I'm not getting a smart bi-jection between the two sets
    Maybe I am not understanding exactly what you're asking but why doesn't this work?

    Solution: It is clear that \left(1+x+\cdots+x^{a_1}\right)\cdots\left(1+x+\cd  ots+x^{a_n}\right) may be expressed in an expanded but completely unsimplified manner. It is clear that this unsimplified expansion may be interpreted as an ordered m-tuple, which we will denote \Sigma, with each coordinate as an unsimplified term. Also, with the same evidence it is clear that we may define a projection \pi:\Sigma\mapsto\left\{1,\cdots,m\right\} in the normal way. Furthermore, for a fixed N define F_N as the set of all coordinates of \Sigma such that the exponent of the coordinate is N when simplified. Lastly, if S and C are defined as in the problem let f:\left\{1,\cdots,C\right\}\mapsto S be defined recurrisvely by f(1) is the unique y\in F_N such that \pi(y) is the minimum of \pi\left(F_N\right) and f(n) is the unique element of F_N-\left\{f(1),f(2),\cdots,f\left(n-1\right)\right\} such that \pi\left(F_N-\left\{f(1),f(2),\cdots,f\left(n-1\right)\right\}\right) is a minimum. It is clear that f is an injection. Also, it is clear that if f were not a surjection then there would be at least C+1 coordinates of \Sigma such that their simplified exponent would be N where it follows that the coefficient of x^N in the simplified expression of \left(1+x+\cdots+x^{a_1}\right)\cdots\left(1+x\cdo  ts+x^{a_n}\right) must be at least C+1 which is a contradiction.


    EDIT: I didn't actually map to S with f, but it's easily fixable.

    I mean though, this is just a formal way of putting what HallsOfIvy said.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Thanks Drexel28. Logging in after a long gap.
    I will have to read your response more carefully, I still pretty confused here.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Really simple question too hard for a simple mind
    Posted in the Statistics Forum
    Replies: 2
    Last Post: October 5th 2010, 08:03 AM
  2. Easy Question - Simple Interest, Simple Discount
    Posted in the Business Math Forum
    Replies: 0
    Last Post: September 21st 2010, 08:22 PM
  3. Replies: 4
    Last Post: May 4th 2010, 09:08 AM
  4. Simple Integral Question (I think it's simple)
    Posted in the Calculus Forum
    Replies: 7
    Last Post: February 13th 2010, 02:37 PM
  5. bijection
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 6th 2008, 04:31 PM

Search Tags


/mathhelpforum @mathhelpforum