Generating Functions for the IMO

The background to this post is that these days I find myself using generating functions all the time, especially for describing the stationary states of various coalescence-like processes. I remember meeting them vaguely while preparing for the IMO as a student. However, a full working understanding must have eluded me at the time, as for Q5 on IMO 2008 in Madrid I had written down in big boxes the two statements involving generating functions that immediately implied the answer, but failed to finish it off. The aim of this post is to help this year’s team avoid that particular pitfall.

What are they?

I’m going to define some things in a way which will be most relevant to the type of problems you are meeting now. Start with a sequence $(a_0,a_1,a_2,\ldots)$ . Typically these will be the sizes of various combinatorial sets. Eg a_n = number of partitions of [n] with some property. Define the generating function of the sequence to be:

$f(x)=\sum_{k\geq 0}a_k x^k=a_0+a_1x+a_2x^2+\ldots.$

If the sequence is finite, then this generating function is a polynomial. In general it is a power series. As you may know, some power series can be rather complicated, in terms of where they are defined. Eg

$1+x+x^2+x^3+\ldots=\frac{1}{1-x},$

only when |x|<1. For other values of x, the LHS diverges. Defining f over C is fine too. This sort of thing is generally NOT important for applications of generating functions to combinatorics. To borrow a phrase from Wilf, a generating function is a convenient `clothesline’ on which to hang a sequence of numbers.

We need a notation to get back from the generating function to the coefficients. Write $[x^k]g(x)$ to denote the coefficient of $x^k$ in the power series g(x). So, if $g(x)=3x^3-5x^2+7$ , then $[x^2]g(x)=-5$ . It hopefully should never be relevant unless you read some other notes on the topic, but the notation $[\alpha x^2]g(x):=\frac{[x^2]g(x)}{\alpha}$ , which does make sense after a while.

How might they be useful?

Example: binomial coefficients $a_k=\binom{n}{k}$ appear, as the name suggests, as coefficients of

$f_n(x)=(1+x)^n=\sum_{k=0}^n \binom{n}{k}x^k.$

Immediate consequence: it’s trivial to work out $\sum_{k=0}^n \binom{n}{k}$ and $\sum_{k=0}^n(-1)^k \binom{n}{k}$ by substituting $x=\pm 1$ into f_n.

Less obvious consequence. By considering choosing n from a red balls and b blue balls, one can verify

$\binom{a+b}{n}=\sum_{k=0}^n \binom{a}{k}\binom{b}{n-k}.$

We can rewrite the RHS as

$\sum_{k+l=n}\binom{a}{k}\binom{b}{l}.$

Think how we calculate the coefficient of $x^n$ in the product $f(x)g(x)$ , and it is now clear that $\binom{a+b}{n}=[x^n](1+x)^{a+b}$ , while

$\sum_{k+l=n}\binom{a}{k}\binom{b}{l}=[x^n](1+x)^a(1+x)^b,$

so the result again follows. This provides a good slogan for generating functions: they often replicate arguments via bijections, even if you can’t find the bijection.

Useful for? – Multinomial sums

The reason why the previous argument for binomial coefficients worked nicely is because we were interested in the coefficients, but had a neat expression for the generating function as a polynomial. In particular, we had an expression

$\sum_{k+l=n}a_k b_l.$

This is always a clue that generating functions might be useful. This is sometimes called a convolution.

Exercise: prove that in general, if f(x) is the generating function of (a_k) and g(x) the generating function of (b_l), then f(x)g(x) is the generating function of $\sum_{k+l=n}a_kb_l$ .

Even more usefully, this works in the multinomial case:

$\sum_{k_1+\ldots+k_m=n}a^{(1)}_{k_1}\ldots a^{(m)}_{k_m}.$

In many applications, these $a^{(i)}$ s will all be the same. We don’t even have to specify how many k_i’s there are to be considered. After all, if we want the sum to be n, then only finitely many can be non-zero. So:

$\sum_{m}\sum_{k_1+\ldots+k_m=n}a_{k_1}\ldots a_{k_m}=[x^n]f(x)^n=[x^n]f(x)^\infty,$

provided f(0)=1.

Useful when? – You recognise the generating function!

In some cases, you can identify the generating function as a `standard’ function, eg the geometric series. In that case, manipulating the generating functions is likely to be promising. Here is a list of some useful power series you might spot.

$1+x+x^2+\ldots=\frac{1}{1-x},\quad |x|<1$

$1+2x+3x^2+\ldots=\frac{1}{(1-x)^2},\quad |x|<1$

$e^x=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\ldots$

$\cos x=1-\frac{x^2}{2!}+\frac{x^4}{4!}\pm\ldots$

Exercise: if you know what differentiation means, show that if f(x) is the gen fn of (a_k), then xf'(x) is the gen fn of ka_k.

Technicalities: some of these identities are defined only for certain values of x. This may be a problem if they are defined at, say, only a single point, but in general this shouldn’t be the case. In addition, you don’t need to worry about differentiability. You can definition differentiation of power series by $x^n\mapsto nx^{n-1}$ , and sort out convergence later if necessary.

Useful for? – Recurrent definitions

The Fibonacci numbers are defined by:

$F_0=F_1=1,\quad F_{n+1}=F_n+F_{n-1},\quad n\geq 1.$

Let F(x) be the generating function of the sequence F_n. So, for n=>1,

$[x^n]F(x)=[x^{n-1}]F(x)+[x^{n-2}]F(x)=[x^n](xF(x)+x^2F(x)),$

and F(0)=1, so we can conclude that:

$F(x)=1+(x+x^2)F(x)\quad\Rightarrow\quad F(x)=\frac{1}{1-x-x^2}.$

Exercise: Find a closed form for the generating function of the Catalan numbers, defined recursively by:

$C_n=C_0C_{n-1}+C_1C_{n-2}+\ldots+C_{n-1}C_0.$

Can you now find the coefficients explicitly for this generating function?

Useful for? – Partitions

Partitions can be an absolute nightmare to work with because of the lack of explicit formulae. Often any attempt at a calculation turns into a massive IEP bash. This prompts a search for bijective or bare-hands arguments, but generating functions can be useful too.

For now (*), let’s assume a partition of [n] means a sequence of positive integers $a_1\geq a_2\geq\ldots\geq a_k$ such that $a_1+\ldots+a_k=n$ . Let p(n) be the number of partitions of [n].

(* there are other definitions, in terms of a partition of the set [n] into k disjoint but unlabelled sets. Be careful about definitions, but the methods often extend to whatever framework is required. *)

Exercise: Show that the generating function of p(n) is:

$\left(\frac{1}{1-x}\right)\left(\frac{1}{1-x^2}\right)\left(\frac{1}{1-x^3}\right)\ldots$

Note that if we are interested only in partitions of [n], then we don’t need to consider any terms with exponent greater than n, so if we wanted we could take a finite product instead.

Example: the mint group will remember this problem from the first session in Cambridge:

Show that the number of partitions of [n] with distinct parts is equal to the number of partitions of [n] with odd parts.

Rather than the fiddly bijection argument found in the session, we can now treat this as a simple calculation. The generating function for distinct parts is given by:

$(1+x)(1+x^2)(1+x^3)\ldots,$

while the generating function for odd parts is given by:

$\left(\frac{1}{1-x}\right)\left(\frac{1}{1-x^3}\right)\left(\frac{1}{1-x^5}\right)\ldots.$

Writing the former as

$\left(\frac{1-x^2}{1-x}\right)\left(\frac{1-x^4}{1-x^2}\right)\left(\frac{1-x^6}{1-x^3}\right)\ldots$

shows that these are equal and the result follows.

Other things – Multivariate Generating Functions

If you want to track a sequence in two variables, say $a_{m,n}$ , then you can encode this with the bivariate generating function

$f(x,y):=\sum_{m,n\geq 0}a_{m,n}x^my^n.$

The coefficients are then extracted by $[x^ay^b]$ and so on. There’s some interesting stuff on counting lattice paths with this method.

Sums over arithmetic progressions via roots of unity

Note that we can extract both $\sum a_n$ and $\sum (-1)^na_n$ by judicious choice of x in f(x). By taking half the sum or half the difference, we can obtain

$a_0+a_2+a_4+\ldots=\frac12(f(1)+f(-1)),\quad a_1+a_3+a_5+\ldots=\frac12(f(1)-f(-1)).$

Can we do this in general? Yes actually. If you want $a_0+a_k+a_{2k}+\ldots$ , this is given by:

$a_0+a_k+a_{2k}+\ldots+\frac{1}{k}\left(f(1)+f(w)+\ldots+f(w^{k-1})\right),$

where $w=e^{2\pi i/k}$ is a $k$th root of unity. Exercise: Prove this.

For greater clarity, first try the case k=4, and consider the complex part of the power series evaluated at +i and -1.

Mutual information and moment generating functions (cs.stackexchange.com)
Generators functions only yields first item (stackoverflow.com)
Poisson Tails (eventuallyalmosteverywhere.wordpress.com)
Bell polynomials (eventuallyalmosteverywhere.wordpress.com)
Exponentials kill polynomials
Bijections etc.

2 thoughts on “Generating Functions for the IMO”

arbias on July 11, 2013 at 2:24 am said:

When you want to evaluate a real definite integral involving some tricky limits by use of complex analysis techniques, you can use the Cauchy residue theorem, which is heavily linked to the Cauchy integral formula and Laurent series. Residues are coefficients in Laurent series of given functions – understanding the generating function here is crucial. Generating functions can be used when integrating. Generating functions are useful when operating on functions.

When using statistical methods, often we will use the exponent function or various other functions as some form of estimate (the Nelson-Allen estimate is a great example). For small values of $x$ the generating function may be useful to save time and to know where we can “cut” off the precision and begin the approximation. Generating functions are useful for approximation.

Reply ↓
Pingback: BMO1 2021 | Eventually Almost Everywhere

Eventually Almost Everywhere

A blog about probability and olympiads by Dominic Yeo

Generating Functions for the IMO

2 thoughts on “Generating Functions for the IMO”

Leave a Reply Cancel reply

Related articles

Share this:

Like this:

Related

2 thoughts on “Generating Functions for the IMO”

Leave a Reply Cancel reply