Re-learning the Generating Functions by Over-Using them!

Published in

Cantor’s Paradise

8 min readNov 20, 2022

If you are like me, you were also confused the first time you saw generating functions. In this article, we are going to over-use them to solve some trivial problems, in order to reach a better understanding of them. In other words, this article is essentially a witness to the quote

If you have a hammer everything looks like a nail!

Over-usage of a hammer! Photo by Theo Crazzolara on Unsplash

Lazy in writing or thinking?

Imagine you are asked to solve this problem.

Problem 1. Find the coefficient of x⁹ in

What would you do?

If you are lazy in thinking, you will just expand it.

You should multiply each term from the first parenthesis to each term in the second one, which gives you 6×6=36 terms. Then you should simplify the result and find the coefficient of x⁹.

If you are lazy in writing, you will try to be smarter.

First, you will notice that you don’t need to expand the whole statement. All you need is to find the pairs of terms that give x⁹. In other words, you need to find the pairs of non-negative integers (even, odd) such that even+odd = 9. The list is as follows:

And since all of the coefficients are 1, their count, 5, will be the coefficient of x⁹.

But what if, you were lazy in both thinking and writing?! In that case, you need some good friends to help you!

Magical machine

Imagine you have a magical machine that can expand the polynomials on your behalf. It is not a fantasy, Symbolab or even a simple python code can do this for you! Then you could just leave everything to your magical friend! Just type the equations there and ask for the result!

Indeed, this magical friend is so helpful, that you can (ab)use it for other problems. Imagine you were asked to solve the inverse problem:

Problem 2. Find the number of ways that we can partition 9 into an even and an odd non-negative integer.

This is super easy to solve directly. But when you have such a good hammer, you can use it everywhere! All you have to do is to translate this problem into the language of your magical friend. They will do the rest. This specific problem, we already know how to translate it, so let’s practice with other problems.

Multiple of Se7en

Before, I said that the help of this friend will save us some mental energy. It is not quite accurate, since the translation of a problem into the language of our friend needs some creativity.

Problem 3. Find the number of ways that we can write 100 as the sum of a multiple of 7, and a non-negative integer less than 7.

You can think of a direct solution, and I bet that solution is much easier than the translation. But let’s translate it for fun.

We need two paratheses since we want to split 100 into two numbers. One should contain the powers of x that are multiples of 7, and the other one should contain powers of x that are less than 7. So, this should work:

After the expansion, the coefficient of term x¹⁰⁰ will be the number of ways we can write 100 = a+b where 7|a and b<7.

The magical friend can take it over from here. But imagine that our friend is not working. Maybe your internet connection is not good, or python doesn’t work, or your friend doesn’t like you anymore. What should you do? Abandoning this solution and solving it directly?! NO!! Let’s expand it ourselves but in a smart way.

If you remember formulas from geometric series, you will notice that

(1+x⁷+x^{14}+x^{21}+\ldots)= \frac{1}{1-x⁷}

This means that what we are trying to expand is

where the last equality is also coming from the geometric series.

So, what now? We were looking for the coefficient of x¹⁰⁰, and this shows that the coefficient is 1. There is only one way of writing 100 into the sum of a multiple of 7 and a non-negative integer less than 7.

We did it! We solved the problem, in the way of our friend, without their help!

But wait! The calculation shows that the coefficient is 1, not only for 100 but also for every other number n. Why is that? Well, I tricked you! It was a trivial question. There is only one way and that is:

n = \lfloor \frac{n}{7} \rfloor + (n \mod 7)

So, essentially because of the uniqueness of division.

Sum of distinct powers of two

Let’s try another one.

Problem 4. Find the number of ways that we can write the number 100 as the sum of distinct powers of 2.

This is a bit harder to translate. There is no condition on the number of powers of 2. So, we should have an unlimited amount of parenthesis. But we need the powers to be distinct, so we should either pick each power 0 or 1 time. Then this is a good candidate:

In order to make a term of x¹⁰⁰ in the expansion, you need to pick distinct powers of 2 that sum up to 100. The number of ways that you can do that, will be the coefficient of x¹⁰⁰.

In our initial plan, the friend was taking over from here, but we are on plan B. We have to do it ourselves! Let’s be creative again.

The trick is to add/remove a factor of (1-x). That will eat up all of the terms due to a beautiful chain reaction of identities.

\frac{1-x}{1-x}(1+x)(1+x²)(1+x⁴)\cdots=\frac{1}{1-x}(1-x²)(1+x²)(1+x⁴)\cdots= \frac{1}{1-x}(1-x⁴)(1+x⁴)\cdots=\frac{1}{1-x}

But again we can use

to see that the coefficient of x¹⁰⁰ is indeed 1, and this is true also for other numbers than 100. Why is that? Well, what we were looking for was exactly the binary representation of the number 100, which is

This time the uniqueness of binary representation.

Another(?) point of confusion

As I said, generating functions was confusing to me, but I remember another moment when a statement confused me.

Back in high school, I knew n-choose-k, the number of choices for selecting k elements among n elements. But at some point, I learned about binomials and was surprised to see a combinatorial object like n-choose-k in the expansion of powers of binomials! What do I mean? Let me formulate my surprise into a problem.

Problem 5. Find a formula for n-choose-k using generating functions!

So, how to translate it? We have n objects to choose from, so let’s put n parenthesis. For each of those objects/parentheses, we want to either select or skip that thing. So, we can think of

In order to make a term of x^k in the expansion, we need to select k of those parentheses to choose the term x from it and choose the term 1 from the rest of the parenthesis, and this is exactly n-choose-k.

So, now what? How to calculate that coefficient without our friend? Here is where another friend comes to rescue us: derivates. All we have to do is to take k derivatives of that phrase and let x=0 . Doing this, every term except for x^k will vanish, and what will remain is k! times than the coefficient of x^k . The k-th derivate of (1+x)^n is

Therefore the coefficient of x^k is

\frac{n(n-1)(n-2)\ldots(n-k+1)}{k!}=\frac{n!}{k!(n-k)!}

which is the well-known formula for n-choose-k .

Finally a non-trivial problem

As a bonus, let me share an example that is not super easy to solve without generating functions, but I also would like to invite you to take a minute to do so! Usually, when I ask friends to do that, they aim for solving it using induction. That seems like the way to go if you can some base cases, but soon you will realize it is not that easy to connect the steps. You can give it a shot and let me know in the comments if you had any success.

Problem 6. In how many ways, we can buy k fruits with the following conditions?

The number of oranges should be divisible by 5
The number of apples should be divisible by 2
The number of bananas should be at most 4
The number of watermelons should be at most 1

I bet, after all of those examples, you feel comfortable with writing down its generating function.

(1+x⁵+x^{10}+\cdots)(1+x²+x⁴+\cdots)(1+x+x²+x³+x⁴)(1+x)

And now, you can see the first and the third parathesis are a good match together, as also the second and the fourth ones. It is essentially a double version of Multiple of Se7en.

So the phrase above is equal to

\frac{1}{1-x⁵}\times\frac{1}{1-x²}\times\frac{1-x⁵}{1-x}\times\frac{1-x²}{1-x}=

where the last equation is coming from taking a derivative from

Therefore, the number of ways to buy k fruits with those conditions is k+1. You may enumerate them for small values of k. That’s fun! By the way, how to solve it without generating functions? Tell me in the comments.

Hope you enjoyed this hammering session. I will post a dedicated post for problem number 7, which will surprise you with the extent of the simplification we can get using generating functions.

Stay tuned!