# Generating Function Example from class

Example: Consider the sequence $(h_n)$ where $h_n$ is the number of nonnegative integer solutions to $$a_1+a_2+a_3+a_4+a_5=n.,$$ where $a_1$ is even, $a_2$ is odd, $a_3$ is a multiple of $5$, $a_4$ is 1,3, or 7, and $a_5$ is 0 or 1.

Without clear explaination, my professor writes $$(1+x^2++x^4\dots)(x+x^3+x^5+\dots)(1+x^5+x^{10}+\dots)(x+x^3+x^7)(1+x)=\sum_{a_1+a_2+a_3+a_4+a_5=0}^{\infty} x^{a_1+a_2+a_3+a_4+a_5},$$ where the $a_i$s respect the conditions stated above. We can simplify to $\frac{x(1+x)(x+x^3+x^7)}{(1-x^2)^2(1-x^5)}.$

My question: where did the first five generating functions come from? I see the relation between the exponents and the $a_i$s but how does one formally obtain these new generating functions and why are all of their coefficients 0 or 1?

-
Why doesn't $n$ show up anywhere else in the problem? – The Substitute Mar 11 '13 at 16:42
Typoes in the sum, the condition should be $a_1 + \ldots + a_5 = n$ (and the other restrictions, really). – vonbrand Mar 11 '13 at 17:53
I don't know how to put that under the sum, but I mentioned it afterward. I want the sum to start from 0, not n. – The Substitute Mar 11 '13 at 18:30
A convention is to write $\displaystyle \sum_{\text{conditions}}$ to express that we are summing over all variables that comply with the <condition>. It'll just be a mess in this case, too complex. – vonbrand Mar 11 '13 at 18:35

In this generating function, the things representing the solutions are the exponents. The condition that $a_1$ is even means that it can be $0, 2, 4, 6, \ldots$. Your professor therefore associates it to the even powers $(1 + x^2 + x^4 + \ldots)$. It's similar for the other cases.

Now, if you understand how multiplication works (distribution) and think about it, you can recognize that the coefficient of $x^n$ in the product is exactly the number of ways of adding $a_1 + \ldots + a_5$ to get $n$. Why? Let's look at a few of the small cases.

In how many ways can we get $a_1 + \ldots + a_5 = 2$? Looking at them, we know there is exactly one (when $a_2 = a_4 = 1$). Similarly, in $$(1+x^2+x^4\dots)(x+x^3+x^5+\dots)(1+x^5+x^{10}+\dots)(x+x^3+x^7)(1+x)$$ we see that the only way to get the exponent $2$ is to choose $1$ from the first, $x$ from the second, $1$ from the third, $x$ from the fourth, and $1$ from the last. Thus the coefficient of $x^2$ in the answer will be $1$. If we were to do this for another, say $n=4$ (or in our problem, the coefficient of $x^4$), you can directly show that for every solution in the $a_i$ there is a corresponding choice of terms whose exponents yield that solution in the product.

Thus the number of solutions for $\sum a_i = n$ will be the coefficient of $x^n$ in the expansion of $(1+x^2+x^4\dots)(x+x^3+x^5+\dots)(1+x^5+x^{10}+\dots)(x+x^3+x^7)(1+x)$.

-
can't much improve on that. (+1) – robjohn Mar 11 '13 at 17:11

The coefficient of $x^n$ in the product of two power series $$\sum_{k=0}^\infty c_kx^k=\sum_{k=0}^\infty a_kx^k\ \sum_{k=0}^\infty b_kx^k$$ is given by $$c_n=\sum_{k=0}^na_k\,b_{n-k}$$ That is, the term in the product that have $n$ as the exponent of $x$ comes from the products of the terms whose exponents sum to $n$.

If we take $a_n$ to be the indicator function of a given set of non-negative integers, $A$, and $b_n$ to be the indicator function of another set of non-negative integers, $B$, then $c_n$ is the number of ways to get $n$ as the sum of a number from $A$ and a number from $B$.

This can be extended to several sets of non-negative integers. In the case at hand, the coefficients of $$f_1(x)=1+x^2+x^4+\dots$$ are the indicator function of the even integers. The coefficients of $$f_2(x)=x+x^3+x^5+\dots$$ are the indicator function of the odd integers. The coefficients of $$f_3(x)=1+x^5+x^{10}+\dots$$ are the indicator function of the multiples of $5$. The coefficients of $$f_4(x)=x+x^3+x^7$$ are the indicator function of $\{1,3,7\}$. Finally, the coefficients of $$f_5(x)=1+x$$ are the indicator function of $\{0,1\}$.

Thus, the coefficient of $x^n$ of $f_1f_2f_3f_4f_5(x)$ is the number of ways to get $n$ as the sum of a number from each of the sets mentioned.

-