# simple question on bijection

• Dec 30th 2009, 08:20 AM
aman_cc
simple question on bijection

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

Let the coefficient of $\displaystyle x^N$ be $\displaystyle C$

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

I want to show that
$\displaystyle 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
• Dec 30th 2009, 08:50 AM
HallsofIvy
Quote:

Originally Posted by aman_cc

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

Let the coefficient of $\displaystyle x^N$ be $\displaystyle C$

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

I want to show that
$\displaystyle 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 $\displaystyle (1+x+...+x^{a_1})(1+x+...+x^{a_2})....(1+x+...+x^{ a_n})$ without "combining like terms". Then $\displaystyle Cx^n$ is precisely a sum of C terms of the form $\displaystyle x^{y_1}x^{y_2}\cdot\cdot\cdot x^{y_k}$ with $\displaystyle 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.
• Dec 30th 2009, 09:11 AM
aman_cc
Quote:

Originally Posted by HallsofIvy
Imagine multiplying $\displaystyle (1+x+...+x^{a_1})(1+x+...+x^{a_2})....(1+x+...+x^{ a_n})$ without "combining like terms". Then $\displaystyle Cx^n$ is precisely a sum of C terms of the form $\displaystyle x^{y_1}x^{y_2}\cdot\cdot\cdot x^{y_k}$ with $\displaystyle 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. :(
• Jan 1st 2010, 11:22 AM
Drexel28
Quote:

Originally Posted by aman_cc

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

Let the coefficient of $\displaystyle x^N$ be $\displaystyle C$

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

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

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

I mean though, this is just a formal way of putting what HallsOfIvy said.
• Jan 13th 2010, 09:33 AM
aman_cc
Thanks Drexel28. Logging in after a long gap.
I will have to read your response more carefully, I still pretty confused here.