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:

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

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 with coefficients in {0, 1, 2, 3} such that

Notice that

And

Since {0, 1, 2, 3} we have that the number of polynomials that satisfy the condition is the coefficient of of this generating function:

By the geometric series formula , we get that it’s equivalent to:

This is telescoping which means that nearly all of its terms simplify and we are left with:

Which is equivalent (in its expanded form) to:

Or

So the number of polynomials of degree n that satisfy the initial condition is