0
$\begingroup$

I am currentely discussing generating functions in my discrete mathematic class. However the professor showed us how to solve counting problems of the form $x^1 + x^2 + x^3 = n$ with $x_i$ and $n$ positives integers and some restrictions. I understand the procedure, but I cannont find why we redefine the problem this way. If someone could maybe give me a link (because I've been looking forever) or a proof of why it works (other than the intuitive "the exponents adds up so it works") I would be eternally grateful :D.

Heres what I (think) I understand:

A generating function would be a way to "encode" information about any real number sequence, finite or inifinite $a_n = a_1, a_2, ... a_k, ... $ into a power serie

$$\sum_{k\geq 0}{}{a_kx^k}$$ where $x$ is an "inderterminate" variable, which in some way we dont really care about It's value (maybe?) and see it more as a position indicator.

Therefore, we kind of take for granted that for some appropriate x, the function is analytical and we can manipulate it.

Alright so from there I get it, it's kind of a way to represent a sequence and by finding it's generating function we can find the $k^{th}$ term desired.

But here's the example we did with no explanation of why it worked.

"Find the number of solution of $$e_1 + e_2 + e_3 = 17$$ such that $$2\leq e_1\leq5$$ $$3\leq e_2\leq 6$$ $$4\leq e_3\leq7$$ and $n$, $e_1$, $e_2$, $e_3$ $\in \mathbb{Z}_\geq0$

And the way they do it is just saying "well all u have to do is find the coefficient of $x^{17}$ in $(x^2+x^3+x^4+x^5)(x^3+x^4+x^5+x^6)(x^4+x^5+x^6+x^7)$

But from what I've been told so far it's kind of multiplying the 3 generating functions of the sequences $(0,0,1,1,1,1,0...)(0,0,0,1,1,1,1,0,...)(0,0,0,0,1,1,1,1,0,0...)$

Is there something I am missing, or maybe are there no real "logic" behind it and we just define it this way cause it works..??

Anyways, thank you everyone. I tried to make my question as clear as possible but still I'm sorry of the question is unclear but ultimately I'm trying to understand why do we define it this way other than "because it works".

Thank you!!!!

$\endgroup$
1
$\begingroup$

I'll try to explain the example you gave, the problem of finding the number of integer solutions to $e_1+e_2+e_3=17$ given $2\leq e_1\leq 5$, $3\leq e_2\leq 6$, and $4\leq e_3\leq 7$.

Suppose we thought about the problem backwards, i.e., what if someone asked you what is the coefficient of $x^{17}$ in the polynomial $$(x^2+x^3+x^4+x^5)(x^3+x^4+x^5+x^6)(x^4+x^5+x^6+x^7).$$

We can note that the product polynomial is formed by taking the sum over every possible product of three terms where the each term is chosen from each of the three factor polynomials (this polynomial product rule can be proved by induction). We then would group the terms of the same exponent in the result to find the coefficient of $x^{17}$. We get one more term of $x^{17}$ for every combination of three terms that give a product of $x^{17}$, which happens precisely when we chose some $e_1\in\{2,3,4,5\}$, $e_2\in\{3,4,5,6\}$, and $e_3\in\{4,5,6,7\}$ so that $x^{e_1}x^{e_2}x^{e_3} = x^{e_1+e_2+e_3} = x^{17}$, so the coefficient on $x^{17}$ is exactly the number of ways to choose terms in the polynomials $x^{e_1}$, $x^{e_2}$, and $x^{e_3}$ from $(x^2+x^3+x^4+x^5)$, $(x^3+x^4+x^5+x^6)$, and $(x^4+x^5+x^6+x^7)$, respectively. So, this is exactly the same as counting the number of ways that $e_1+e_2+e_3=17$.

Now, the reason why we prefer to do it in terms of these polynomials/series instead of just the raw combinatorial problem is because putting it in terms of polynomials/series gives us a much richer set of tools we can manipulate and analyze the representation in. As long as the polynomials are equal, we will always have the information encoded in the coefficients once we write our expression in polynomial form.

I hope that clears things up!

$\endgroup$
  • $\begingroup$ Ohh I see! so it's just a "convenient way" of defining the problem to in a way we can encore more informations then? $\endgroup$ – Ian Leclaire Apr 7 '18 at 20:54
  • $\begingroup$ We're not encoding more information, it's just easier to manipulate because we can do things like take derivatives, convolutions, limits, so on and so forth. $\endgroup$ – Yu Zhao Apr 7 '18 at 22:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.