Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

2 Answers

up vote 4 down vote accepted

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

share|improve this answer
1  
can't much improve on that. (+1) –  robjohn Mar 11 '13 at 17:11
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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