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 . 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:
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
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 to denote the coefficient of in the power series g(x). So, if , then . It hopefully should never be relevant unless you read some other notes on the topic, but the notation , which does make sense after a while.
How might they be useful?
Example: binomial coefficients appear, as the name suggests, as coefficients of
Immediate consequence: it’s trivial to work out and by substituting into f_n.
Less obvious consequence. By considering choosing n from a red balls and b blue balls, one can verify
We can rewrite the RHS as
Think how we calculate the coefficient of in the product , and it is now clear that , while
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
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 .
Even more usefully, this works in the multinomial case:
In many applications, these 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:
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.
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 , and sort out convergence later if necessary.
Useful for? – Recurrent definitions
The Fibonacci numbers are defined by:
Let F(x) be the generating function of the sequence F_n. So, for n=>1,
and F(0)=1, so we can conclude that:
Exercise: Find a closed form for the generating function of the Catalan numbers, defined recursively by:
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 such that . 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:
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:
while the generating function for odd parts is given by:
Writing the former as
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 , then you can encode this with the bivariate generating function
The coefficients are then extracted by 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 and by judicious choice of x in f(x). By taking half the sum or half the difference, we can obtain
Can we do this in general? Yes actually. If you want , this is given by:
where 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.