How/why does this generating function approach work?

99 Views Asked by At

Suppose I wanted to find the number of solutions of $$e_1 + e_2 + e_3 = 17$$ where $e_1, e_2,$ and $e_3$ are nonnegative integers with $2 \leq e_1 \leq 5, 3 \leq e_2 \leq 6, 4 \leq e_3 \leq 7$.

The solution [apparently] lies in the fact that the number of solutions with the indicated constraints is the coefficient of $x^{17}$ in the expansion of $$\bigg(\sum_{k=2}^5 x^k \bigg)\bigg(\sum_{k=3}^6 x^k \bigg) \bigg(\sum_{k=4}^7 x^k\bigg) $$Why is this the case? Why, on a fundamental level, do elementary generating function-based counting methods (such as this one) work?

1

There are 1 best solutions below

0
On

As described in the comments a $x^{17}$ monom iff you multiply $x^l$,$x^m$,$x^n$ from the first, second, third sum (i.e. $2\leq l\leq 5, 3\leq m\leq 6, 4\leq n \leq 7$) with $l+n+m=17$. So the coefficient of $x^{17}$ in the product is exactly given by the number of possibilities for $l+m+n=17$.