# Math Help - simple question on bijection

1. ## simple question on bijection

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

2. Originally Posted by aman_cc

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.

3. Originally Posted by HallsofIvy
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.

4. Originally Posted by aman_cc

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.

5. Thanks Drexel28. Logging in after a long gap.
I will have to read your response more carefully, I still pretty confused here.