simple question on bijection

**aman_cc** · December 30th 2009, 08:20 AM

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

**HallsofIvy** · December 30th 2009, 08:50 AM

Originally Posted by aman_cc

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.

**aman_cc** · December 30th 2009, 09:11 AM

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.

**Drexel28** · January 1st 2010, 11:22 AM

Originally Posted by aman_cc

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.

**aman_cc** · January 13th 2010, 09:33 AM

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

Thread: simple question on bijection

LinkBack

Thread Tools

Display

simple question on bijection

Similar Math Help Forum Discussions

[SOLVED] Really simple question too hard for a simple mind

Easy Question - Simple Interest, Simple Discount

Maths dispute - a very simple simple exponents question

Simple Integral Question (I think it's simple)

bijection

Search Tags