What are generating functions?

I have never really understood what generating functions are. I am trying to learn how they work in some counting problems;

Take, for example, this problem. If I were to find the number of non-negative integral solutions to the following equation $3a+4b+2c+d=20$, the standard trick (as seen in some places on the internet) is to take the product of the series $$\displaystyle (1+x^3+x^6+\dots)(1+x^4+x^8+\dots )(1+x^2+x^4+\dots)(1+x+x^2+\dots)$$ and find the coefficient of $x^{20}$.

I am not able to understand why that is the case. Perhaps, it can be explained in this manner. If $a$ is 0, [let $A(x)=1+x^3+x^6+\dots$] then $A(x)=x^0=1$, if $a=1$, $A(x)=1+x^3$ as each $a$ contributes $3a$ to the sum.But I am still not sure what is being done.

I will be grateful if someone could tell me if I am on the right track .What exactly do we mean by the construction of a generating function of a sequence" in a rigorous manner and how are they useful in counting?I am not looking for techniques in manipulating generating functions but I wish to understand in a rigorous manner how they work.

Solution 1:

To quote the introductory words of Wilf in Chapter 1 of his excellent book "generatingfunctionology",

A generating function is a clothesline on which we hang up a sequence of numbers for display.

Specifically, to answer your question on what it means to talk of the "generating function of a sequence": Given a sequence $a_0, a_1, a_2, \dots$, the generating function of that sequence is the object $A(x) = a_0 + a_1x + a_2x^2 + \dots$. This is a way of encoding all the elements of the sequence into a single object.

For instance, consider the very simple sequence defined by $a_n = 1$ for all $n$. Its generating function is the object $A(x) = 1 + x + x^2 + \dots$, which can also (if you wish) be written more concisely as $\dfrac{1}{1-x}$. Or, consider the sequence defined by $a_n = 2^n$. The generating function of this sequence is the object $A(x) = 1 + 2x + 2^2x^2 + 2^3x^3 + \dots$, which can also be written as $\dfrac{1}{1-2x}$. Note that this gives a way to encode all the (infinitely many) elements of the sequence $1, 2, 2^2, 2^3, \dots$ into a single object $A(x)$. (Of course there are other ways too: you could say that the function $n \mapsto 2^n$ is a single object.)

Anyway, now that you hopefully understand roughly what generating functions are, we can turn to their use in counting problems. In general, when we want to find an element of some sequence, one way is to find the generating function of the whole sequence first, and then find the particular element we care about. This may seem like more work, but in practice can often be simpler.

So, let $a_n$ be the number of solutions to $3a + 4b + 2c + d = n$; we want to find the generating function $A(x) = a_0 + a_1x + a_2x^2 + \dots$ and then read off $a_{20}$ which is the coefficient of $x^{20}$ in it. All this should answer what generating functions are here, why take coefficient of $x^{20}$ etc.

The actual part related to the counting problem is relatively simple (though nontrivial) once you understand all this: if you consider $(1 + x^3 + x^6 + \dots)$, the coefficient of $x^k$ in this is $1$ if $k$ can be written as $3a$ for some $a$, and $0$ otherwise. Similarly the other factors. For any solution $(a, b, c, d)$ satisfying $3a + 4b + 2c + d = n$, when you multiply the four factors $(1+x^3+x^6+\dots)(1+x^4+x^8+\dots)(1+x^2+x^4+\dots)(1+x+x^2+\dots)$ together, you'll get a bunch of terms, where each term in the product is got by taking one particular term from each of the factors, and multipying those four terms together. One of the particular products is that of taking $x^{3a}$ from the first factor, $x^{4b}$ from the second, etc., to give $x^{3a}x^{4b}x^{2c}x^{d} = x^{3a + 4b + 2c + d} = x^n$. Each solution $(a, b, c, d)$ contribues one such term $x^n$, and these solutions are the only way to get $x^n$ in the product. So the coefficient of $x^n$ is the number of times it occurs in the product, which is the number of solutions.

Solution 2:

One way to get a term of $x^{20}$ in the product you have listed is the term $x^6 x^8 x^2 x^4$. This term corresponds to the solution $a = 2$, $b = 2$, $c = 1$, $d = 4$.

You can repeat this idea for any solution of $3a + 4b + 2c + d = 20$. That is, every solution arises from some product of terms in your polynomials and vice versa. Thus, the number of solutions is equal to the number of ways you can get a term of $x^{20}$ in your product (i.e. the coefficient of $x^{20}$).