Generating Function Example from class

Question

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?

Answer 1

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)$.

Answer 2

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.