[Tutorial] Generating Functions in Competitive Programming (Part 1)

[Tutorial] Generating Functions in Competitive Programming (Part 1)

Hi everyone! Inspired by the recent Codeforces Round 641, I decided to write an introductory tutorial on generating functions here. I am by no means an expert in generating functions so I will write about what I currently know about them. amiya has written a really interesting blog here on Codeforces about more advanced applications of generating functions, but I think there is no English tutorial on the basics of this topic yet (or at least on CP sites). Thus, I would like to share about this topic here.

I plan to split this tutorial into two parts. The first part (this post) will be an introduction to generating functions for those who have never learned about them at all, and some standard examples and showcases of generating functions. The second part will be a collection of several applications of generating functions in CP-style problems. If you are already familiar with generating functions, you may just skip to Part 2 directly.

In this part, many examples are from the book generatingfunctionology which I think is also a great introductory material to generating functions.

What are Generating Functions?

Let's say we have a sequence . We associate with a series which "encodes" the terms in with its coefficients.

Formally, for a sequence of numbers , we define the ordinary generating function (OGF) of to be .

For example, consider the Fibonacci sequence with the terms . Then, .

You may imagine that you are putting the (infinitely many) terms of the sequence in a line, and assigning a power of to each term of the sequence in order. Adding them up, you get an “infinite polynomial” which somewhat encodes the sequence. The nice thing about generating functions is that sometimes the series is nicer to play around with which will sometimes uncover surprising properties of the sequence.

There are other types of generating functions, such as the Exponential Generating Function (EGF) and Dirichlet Generating Function. We will look at some examples of EGF later in this post, but for the next few examples we will focus on OGFs.

Before that, we introduce a simple notation. For a series , we let (i.e. the coefficient of in ).

Simple Examples of OGFs

Let’s start with a very simple example. What is the OGF of the sequence ? By definition, we have . Does this series look familiar?

is actually a geometric series with common ratio ! Thus, we can use the geometric series formula to write .

Note: Don’t we need to care about convergence issues like ? Well, it depends on what you want to do with your series. We will work on formal power series most of the time, which allows us to ignore the issue of convergence. However, this also means that we can’t “substitute” as some fixed value without care. For example, when , the series diverges but for say , converges. In this post, we won’t deal with the analytic properties of the series most of the time. If you really need to substitute values though, the general rule of thumb is that you can do it if the series converges.

We can manipulate generating functions very much like how we would manipulate other algebraic expressions. Here is a classic example.

Example. Consider the sequence defined by , and for . Find the OGF of (we usually denote it with a capital letter, say ).

Clearly, is the -th Fibonacci number. We will use the recurrence relation to find the OGF of .

Firstly, we need to make the terms of the series appear. The easiest way to do this is to multiply the recurrence relation by to obtain .

Next, we sum up the terms on both sides over all valid (in this case ) to obtain:

This is equivalent to:

Thus, we obtain the OGF of Fibonacci numbers.

Let’s see another example of OGF of a common sequence.

Example. The Catalan numbers are defined by and for . Find the OGF of .

Again, our strategy is to multiply a power of to both sides and summing up for all . We obtain:

The LHS is easy to intepret: it is just .

How do we interpret the RHS? We claim that it is . Consider the expansion of . Which terms contribute to the coefficient of ? If we look at , we see that we can only obtain by picking from the first bracket and from the second bracket. Hence, the coefficient of in is , as desired.

Hence, we have , which is a quadratic equation in ! Using the quadratic formula, we can obtain . Which sign should we choose? If we choose the + sign, then the numerator as , while the denominator , so the ratio will become infinite at . However, can be expanded as a power series at , so should converge at . Thus, we should choose the minus sign to obtain (indeed, by L'Hopital Rule it converges to at ).

Tip: Try looking for common sequences and see if you can derive the formula for their OGFs from scratch. It is really helpful if you can derive the intuition where you can see the functional equation directly from the recurrence.

OGFs in more than one variable

We don’t have to limit ourselves to one variable. We can have multivariable OGFs. Let’s look at the following simple example.

Example. The binomial coefficients is defined by the recurrences for , for and for . Find the OGF of .

We define the OGF . As usual, we try to relate with itself using the recurrence. We have

Hence, we have

From the bivariate OGF, we can deduce some interesting identities in one-variable. For example, we have

Hence, . However, , so . Note that this gives the same result as binomial theorem on .

It is more interesting to look at in terms of an OGF in . We have

Comparing coefficients, we obtain , so using the same argument as before, we have

This identity is interesting because it allows us to “expand” in terms of the OGF of binomial coefficients! In particular, we have , so . This identity is very useful especially when dealing with sums involving binomial coefficients where is fixed and varies.

Exponential Generating Function

So far we have looked at ordinary generating functions. Now, let me introduce a new type of generating functions called the exponential generating function.

Definition: Let be a sequence of numbers. Then, the EGF of (say is defined as .

In other words, the EGF is just the OGF but every term is now divided by . Why the weird choice of division by ? The next example will shed some light on this choice.

Example. Let denote the -th Bell number, which counts the number of ways to partition into disjoint sets. For example, , because there are ways to partition into sets: ; , ; , ; , ; , , . Find the EGF of .

Our first step is to look for a recurrence relation. Suppose you have this as a Div. 2 C problem. What is the simplest dp you can come up with?

We can fix the size of the set containing the element , say . Then, there are ways to choose the other elements of the set, and ways to partition the remaining elements. Hence, we obtain the simple recurrence formula

By precomputing binomial coefficients, this is an dp, which should be sufficient for a Div. 2 C. However, why stop here? Suppose the problem asks you to find for . Can you still solve this?

The answer is yes. Let’s use our recurrence to find the EGF of . Note that

Now we see why EGFs are convenient for us. If our convolutions involve binomial coefficients (which is often the case when we deal with combinatorial objects), then multiplying EGFs kind of “automatically” helps us multiply our terms by a suitable binomial coefficient (more details later).

Back to our problem, we want to write everything in terms of . RHS is easy, since it is just (Recall that is the Maclaurin series of ). However, the LHS needs a bit of work, since we have the unfortunate term instead of the term. To deal with this obstacle, we use a common trick when dealing with formal power series. Let us differentiate B(x), then multiply by . Verify that if is a formal power series with then .

Thus, looking back at our equation, we have

, which implies . If you are familiar with calculus, you will recognize that if we integrate both sides, we get . Since , and we have . Thus, is our desired EGF.

So, how to find in faster than time. The idea is that we can find the first terms of in time, so we just need to compute the first few terms of our EGF and read off the answer! In this 2-part article, I will omit explaining how to do certain well-known polynomial operations in time or time like , etc. There are already tutorials written for them (for example cp-algorithms). Hence, I will just quote that we can do those polynomial operations since that is not the main focus of this article.

Algebraic Manipulation of Generating Functions

Here are some common ways to manipulate generating functions and how they change the sequence they are representing. In this section, , will represent sequences and and are their corresponding generating functions (OGF or EGF depending on context which will be stated clearly). As an exercise, verify these statements.

Addition

For both OGF and EGF, generates the sequence .

Shifting

For OGF, generates the sequence where for . For EGF, you need to intergrate the series times to get the same effect.

For OGF, generates the sequence .

For EGF, generates the sequence , where denotes differentiated times.

Multiplication by

For both OGF and EGF, generates the sequence .

In general, you can get the new generating function when you multiply each term of the original sequence by a polynomial in by iterating this operations (but I do not include the general form here to avoid confusion).

Convolution

This is really the most important operation on generating functions.

For OGF, generates the sequence .

For EGF, generates the sequence (verify this!). This is also why EGF is useful in dealing with recurrences involving binomial coefficients or factorials.

Power of Generating Function

This is just a direct consequence of convolution, but I include it here because it is so commonly used.

For OGF, generates the sequence

For EGF, generates the sequence

Prefix Sum Trick

This only works for OGF, but is useful to know. Suppose want to generate the sequence . Then, we can take .

Why does this work? If we expand the RHS, we get . To obtain the coefficient of which is , we need to choose from the first bracket and from , so summing over all gives us .

List of Common Series

Before we delve into applications, I want to compile a short list of series that we will use frequently below. They are

Our goal in many problems will be to reduce the EGF or OGF involved in the problem into some composition of functions that we know above.

You can find a more complete list on Page 57 on generatingfunctionology.

Generating Functions in Counting Problems

Generating functions is a powerful tool in enumerative combinatorics. There are so many applications that I can only cover a small fraction of them here. If you are interested in more examples of counting using generating functions, you can try the books generatingfunctionology and Enumerative Combinatorics.

Here, I will show some classical examples of counting problems involving generating functions. In the next post, I will focus on CP problems which utilizes generating functions.

Catalan Numbers, revisited

We have shown before that the OGF of the Catalan numbers is . Suppose we want to find a closed-form formula for . Of course, it is well-known that , but let's pretend we don't know that yet. We want to "expand" our generating function , but there is a troublesome square root in our way.

This is where the generalized binomial theorem comes to our rescue. Before that, we need to define generalized binomial coefficients.

Definition. Let be any complex number and be a nonnegative integer. Then, .

This is the same as the usual binomial coefficients, but now we no longer require the first term to be a nonnegative integer.

Next, we show a special case of the theorem.

Theorem. Let be a real number and be a nonnegative integer, then

The proof is just differentiating the left side times and compare the constant term. I leave this as an exercise.

In particular, our mysterious function

Hence,

, as desired.

Some problems involving permutations

For a permutation , consider the graph formed by the edges . It is well-known that the graph is a union of several disjoint cycles.

Problem. Count the number of permutations of length with cycles.

These numbers are also called Stirling numbers of the first kind.

Let be the number of permutations of length which is a cycle. Let denote the EGF of . Let be our answer and be its EGF. The key observation here is that .

Suppose for a moment our cycles are labelled from to . For every permutation, label each element with the label of the cycle it is in. Let's fix the length of cycle to be (so ). Then, there are ways to permute the elements in the -th cycle and ways to assign cycle labels to the elements of the permutation. Finally, in our actual problem, the order of cycles doesn't matter, so we need to divide by in the end.

To summarize, the answer is . Verify that is , so (the disappears into because we are dealing with EGFs).

Let's assume this is a CP problem and we are asked to find the answer for . Then, we can calculate the answer directly using generating functions in since we can do exponentiation in ().

Actually, what we just did is a special case of the more general Exponential Formula. However, I feel that it is easier to understand the Exponential Formula from these specific examples and you should try to understand it intuitively until it becomes common sense.

Problem. Count the number of permutations of length such that all cycle lengths are in a fixed set of positive integers .

We use the same trick as the previous problem, but let if is not in .

This time, we need to find because we need to sum over all values of (number of cycles), which can also be computed easily.

Problem. Find the expected number of cycles of a permutation of length .

To compute the expected number of cycles, we count the sum of number of cycles over all permutations of length . Let denote the sum of number of cycles over all permutations of length and as the EGF of . Using the same function in the previous problems, we need to find (note the extra factor which is the difference between this and the previous examples)

However, . Hence, .

For , . By the Prefix Sum trick, .

Thus, . Since is the expected number of cycles of a permutation of length , our answer is , the -th Harmonic number!

We see that the exponential trick is viable when we are dealing with items that are made up from smaller pieces.

Stirling Numbers of the Second Kind

Problem. Find the number of ways to partition the set into subsets.

These numbers are also called Stirling numbers of the second kind.

Denote the answer by . The trick is to consider the polynomial (also known as deck enumerator) . What is ? We have . This sum has a similar combinatorial interpretation as the ones in the previous problems. Let's assume the partition sets are labelled from to . Then, denotes the size of the -th set and there are ways to assign a set to each element (by the multinomial theorem). However, we have counted each partition times, since in our final answer the sets shouldn't be ordered. Thus, .

Rearranging gives us . Hence, . Introducing the variable to correspond to the variable , we have .

Note: The polynomial is also known as a hand enumerator.

Thus, we have the simple formula . Note that , so we have (note how similar this is to the EGF of Bell numbers! In fact is the EGF of Bell numbers (can you see why?)).

To get the answer, we just need to find which you can compute using polynomial operations efficiently.

Graph Counting

Problem. Find the number of vertex-labeled undirected graphs with vertices so that each vertex has degree .

Every such graph must be a union of disjoint cycles (why?). As usual, we start by considering the generating function for one "component" in the item we need to count. Let denote the number of undirected cycles of length and denote its EGF. Then, .

Let denote the EGF of our answer. Using the same argument as before, we find that , so we get the formula , and you can compute the coefficient of to obtain the answer.

Let's look at a trickier example.

Problem. Find the number of bipartite vertex-labeled graphs with vertices.

It is tempting to try a similar approach as the previous problem. We can relate the number of bipartite graphs with the number of connected bipartite graphs. Can we count the number of connected bipartite graphs easily? Unfortunately, it does not seem to be too easy to count.

Instead, let us color each vertex of the graph with red or blue, and count the number of colored bipartite graphs (not necessarily connected). Suppose we choose vertices to color red and to color blue. Then, there are ways to choose the coloring and to choose the edges (since each edge must be between components). Thus, the number of colored bipartite graphs on vertices is . Call this number and its EGF as .

The next step is to relate the number of colored bipartite graphs with the number of colored connected bipartite graphs. Let denote the number of colored connected bipartite graphs on vertices and be its EGF. Using a similar argument as before, we have the relation , and thus .

Returning to our original problem, our next step is to count the number of connected bipartite graphs on vertices (call the count and EGF ). However this is easy, since each connected bipartite graph can be colored in exactly two ways (the coloring is fixed once we choose the color of a vertex). Hence, .

Finally, let be the number of bipartite graphs on vertices and be its EGF. Then, we have using the exponential argument. Thus, , which is a nice formula!

Placing Rooks and PIE

Let's look at a last example which demonstrates the use of the Inclusion-Exclusion Principle (PIE).

Consider a chessboard where some cells are colored black and others are colored white. Suppose we magically know the sequence , the number of ways to place non-attacking rooks on white cells of the chessboard (i.e. no two are on the same row or column, no rooks are on black cells). Let denote the number of ways to place non-attacking rooks on the chessboard so that exactly of the rooks are on white squares. Can we find in terms of ?

The trick is that exact conditions are usually harder to count while "at least" conditions are easier to count. For a fixed subset of white cells , denote as the number of ways to place non-attacking rooks on the chessboard such that there is at least one rook on each cell in . Let .

We relate with . Consider a subset of size and a way to place non-attacking rooks so that the white cells they occupy is exactly . Every -element subset of contributes to the sum . Thus, we obtain the recurrence .

Let and be the OGFs of and . We can derive a simple relation between and . Indeed, we have

. Thus, we have the simple relation .

It turns out that is usually much easier to find. In our problem, , since we can first choose our set as any set of non-attacking rooks on white cells, then place the other rooks in ways. Thus, we obtain and . Hence, we can read from the coefficients of .

Proving Some Interesting Theorems via Generating Functions

This is not entirely CP related but here are some cool theorems you can prove easily with generating functions.

Partition in odd parts = Partition in distinct parts

A partition of into parts is a multiset of positive integers of size which sum up to . For example, is a partition of into parts. Note that the order of elements do not matter, so and are the same partition.

You might have heard of the well-known problem of proving that the number of partitions of into odd parts is equal to the number of partitions of into distinct parts. Here, we prove a generalization of it.

Problem. Prove that the number of partitions of into parts of size not divisible by is equal to the number of partitions of into parts such that there are at most parts of each size.

Note that when we reduce this to the standard problem.

Fix and let be the OGF of the first object and be the OGF of the second object. Observe that choosing a partition is the same as choosing the number of times we use each integer in our multiset, so

Binet's Formula (and solving Linear Recurrences)

Let denote the -th Fibonacci number (with , , ). You may have heard of Binet's Formula, which states that .

This might look very random, but it actually comes directly from the generating function. Recall that is the OGF of . The trick here is to use partial fractions (we will explore another example in the next part). Let be the roots of the equation (where , ). Then, we can write . With some calculation, we can obtain .

Comparing coefficients, we get . Recalling that and gives us Binet's Formula.

Note that this method is generalizable for general linear recurrences.

Probability that a random permutation has no cycle length which is the square of an integer

Problem. What is the probability that a random permutation has no cycle length which is the square of an integer?

This problem seems pretty random (no pun intended), but I include it here to show the power of generating functions.

Firstly, suppose we know that our permutation is of length and there are cycles of length (so ). How many such permutations are there? With some simple counting, we can obtain the formula (Hint: Assume the cycles are labelled first, and assign the elements into cycles, then arrange the elements within each cycle. Divide some factorials to handle overcounts).

The sequence defined above is also called the cycle type of a permutation.

Let denote the number of permutations of length with cycle type and denote the probability that a permutation of length has cycle type . Hence, and

Now, the trick is to consider the infinite-variable generating function in :

From our discussion above, we know how to find , thus we can write as

Hence, for a fixed cycle type , .

Let us return to our problem. Call a cycle type good if for all perfect squares . We want to find . We can "substitute" for all non-perfect squares to indicate that we don't care about the power of if is not a perfect square. so we reduce our problem to finding (noting that for all perfect squares )

If we let be the OGF of , then by the Prefix Sum trick, our limit is equal to (assuming the sum converges).

Intuitively, we can get the "sum to infinity" by substituting into , and we are only interested in the terms without (for a perfect square), so we let these , to obtain

, which is actually our answer (recall that ).

Snake Oil Trick in Proving (or Finding) Combinatorial Identities

To end the first part of this tutorial, I will briefly introduce a trick to simplify combinatorial identities using generating functions. The idea is that instead of dealing with the sum directly, it is easier to deal with the series obtained from the generating functions.

Problem. Find the sum for a fixed positive integer .

Suppose the answer to our problem is . The idea is that it is easier to consider the OGF of , which is . We have

Now, we switch summation signs to obtain

The key idea is to make the inner sum easy to compute, and we know how to compute , since it is just in disguise with !

Thus, we factor out to obtain

Do you recognize the last expression? It is actually where is the OGF of the Fibonacci numbers! Thus, , and by comparing coefficients we get , the -th Fibonacci number!

There are many other similar applications of the Snake Oil Method but I won't go into detail here. In general, this method might be useful in CP if you encounter some math problems and reduce the problem into double or triple summation of binomial coefficients but you need an solution. Sometimes, you can forcefully simplify your summations using the Snake Oil method. We will use the trick of introducing a power series and swapping summation signs again to simplify some expressions in the next part of this article.

As an exercise, try to prove the following identity with the Snake Oil method:

(there is an obvious bijective proof, can you see why this is true?). This identity is very useful in simplifying sums involving binomial coefficients.

This ends the first part of my tutorial on generating functions. The next part will focus more on applications on GFs in CP problems, so stay tuned!

UPD: Part 2 is now available here.

P.S. Let me know if I made any errors or typos in the post (which is likely to happen).