Formally:

The generating function of an infinite sequence $(a_0, a_1, \ldots)$ is represented by the power series:

$$ \sum_{n=0}^\infty a_nx^n $$

Informally:

Consider a sequence of numbers $(a_0, a_1, \ldots)$. We want to encode this sequence within a function, expressed as:

$$ a_0x^0 + a_1x^1 + a_2x^2 + \ldots + a_nx^n = \displaystyle\sum_{n=0}^\infty a_nx^n $$

Example of Sequence $(1, 1, 1, 1, \ldots )$:

$$ 1x^0 + 1x^1 + 1x^2 + \ldots + 1x^n = \displaystyle\sum_{n=0}^\infty x^n = \frac{1}{1 - x} $$

You may ask why the equation $\displaystyle\sum_{n=0}^\infty x^n = \frac{1}{1 - x}$ holds. This is explained by the convergence of geometric series.

The series:

$$ \sum_{n=0}^\infty x^n $$

is a geometric series with the common ratio \(x\). The sum \(S\) of an infinite geometric series is given by the formula:

$$ S = \frac{a}{1 - r} $$

where \(a\) is the first term of the series and \(r\) is the common ratio. For this specific series:

  • \(a = 1\) (the first term)
  • \(r = x\) (the common ratio)

Hence:

$$ \displaystyle\sum_{n=0}^\infty x^n = \frac{1}{1 - x} $$

Multiplication of GF’s and their combinatorial meaning

Let $A(x) = \sum_{n=0}^\infty a_nx^n$
Let $B(x) = \sum_{n=0}^\infty b_nx^n$

Then:

$$ A(x)B(x) = \sum_{n=0}^\infty (\sum_{i = 0}^n a_ib_{n-i})x^n $$

Notice that $A(x)B(x)$ is the generating function of the sequence with $n$-th element $\sum_{i = 0}^n a_ib_{n-i}$. From combinatorial perspective it’s the number of ways you can combine 2 types of objects in a size of n.

Let’s have an example for better understaning.

Problem: Find number of strings consisting of letters a,b,c of length n not containing aa as substring

The hard part is to construct the generatin function, after getting the closed form of it, there are multiple ways to decode it.

So let’s let’s denote A as generating function for strings not containing aa and analyize what are the cases we have.

  • empty
  • a
  • b + [strings not containing aa] (notice the recursion)
  • c + [strings not containing aa]
  • ab + [strings not containtng aa]
  • ac + [strings not containing aa]

let’s convert those into generating functions.

  • empty = 1
  • a = x
  • b + [strings not containing aa] = xA (one element x and rest is recursively generated by A)
  • c + [strings not containing aa] = xA (one element x and rest is recursively generated by A)
  • ab + [strings not containtng aa] = x^2A (two elements hence x^2 and rest again is recursively generated by A)
  • ac + [strings not containing aa] = x^2A similarly to the previous.

So $A = 1 + x + xA + xA + x^2A + x^2A = 1 + x + 2xA + 2x^2A = \frac{1 + x}{1 - 2x - 2x^2}$

Now we could obtain the exact formula for coefficients of the power series expansion of A. Which would require set of techniques such as partial fraction decomposition, explaining which is an another article, but these techniques are completly mechanical, so the hard part is to have the generating function in this form, rest is easy to find.

References