An Insight Into Generating Functions – Mattia Giuri's bizarre blog

The technique of using a generating function is widely used in combinatorics: you have a polynomial where the coefficient of the term of degree n represents how many times n appears in your counting problem.

Let’s see a simple example to make it clearer.

Let’s say we have 2 standard dice, we roll both and we want to compute all the possible sums that can occur. The generating function of the dice is no other than:

$x + x^2 + x^3 + x^4 + x^5 + x^6$

Each term represents one face of the die. Rolling two dice means squaring such function. The result is:

$x^2 + 2x^3 + 3x^4 + 4x^5 + 5x^6 + 6x^7 + 5x^8 + 4x^9 + 3x^{10} + 2x^{11} + x^{12}$

This means that there are (for example) 6 different ways to have 7 as sum of the values from 2 dice.

Now let’s see something more complicated.

A Very Nice Problem

Let n be a positive integer. Find the number of polynomials $f(x)$ with coefficients in {0, 1, 2, 3} such that $f(2) = n$

Notice that

$f(x) = a_0 + a_1x + ... + a_kx^k$

And

$f(2) = a_0 + 2a_1 + ... + 2^ka_k$

Since $a_k \in$ {0, 1, 2, 3} we have that the number of polynomials that satisfy the condition is the coefficient of $x^n$ of this generating function: