An Introduction to Generating Functions

Go back to the Math Jam Archive

Copyright © 2017 AoPS Incorporated. This page is copyrighted material. You can view and print this page for your own use, but you cannot share the contents of this file with others.

Facilitator: Dave Patrick

DPatrick (19:26:10)
Welcome to today's Math Jam!

DPatrick (19:26:15)
Before we get started I would like to take a moment to explain our virtual classroom to those who have not previously participated in a Math Jam or one of our online classes.

DPatrick (19:26:26)
The classroom is moderated, meaning that students can type into the classroom, but only the moderators can choose a comment to drop into the classroom. This helps keep the class organized and on track. This also means that only well-written comments will be dropped into the classroom, so please take time writing responses that are complete and easy to read. Also, only moderators can enter into private chats with other people in the classroom.

DPatrick (19:26:45)
Additionally, the virtual classroom is TeX enabled. TeX allows users to make nice equations and other math expressions. If you would like to learn how to write in TeX/LaTeX, click on the ""LaTeX"" tab on the left side panel of our website: there is a tutorial and reference guide there.

DPatrick (19:26:54)
Using TeX in the virtual classroom is slightly different than using it on the message board or in a TeX editor. If anything you type up in a post that uses TeX then you must use a semicolon (;) to begin your post. For example, if you type

DPatrick (19:26:58)

DPatrick (19:27:04)
This message will look like this when posted in the classroom:

DPatrick (19:27:08)

DPatrick (19:27:18)
Just remember, if your post uses TeX, use the semicolon (;) to begin your post!

DPatrick (19:27:37)
Today, we will describe an algebraic device called a [b]generating function[/b]. A generating function is a gadget which encapsulates combinatorial information into an algebraic object. Simply put, it's a way to use algebra to solve counting problems.

DPatrick (19:27:57)
In fact, most of you have probably seen a generating function before, even if you didn't call it a ""generating function"".

DPatrick (19:28:02)
Recall the Binomial Theorem:

DPatrick (19:28:04)

DPatrick (19:28:19)

DPatrick (19:28:29)
But this coefficient also has a simple counting explanation. What it is?

justdudxit (19:28:58)
the number of objects from a pool of n taken k at a time

Barnacle (19:29:02)
The number of ways to choose k objects from a set of n?

monchaita (19:29:06)
choose k thing from n things

DPatrick (19:29:27)

DPatrick (19:29:44)

DPatrick (19:30:08)
This is a basic idea of generating functions: the coefficient of x^k counts some quantity which depends on k.

DPatrick (19:30:23)
We'll start off with a couple very simple examples.

DPatrick (19:30:29)
Suppose we're at a candy store. There are $2 bags of candy and $4 bags of candy. I'm either going to buy a $2 bag or I'm going to buy nothing. You're going to buy nothing, a $2 bag, or a $4 bag.

DPatrick (19:30:49)
We write my generating function for the amount of money I'm going to spend as 1 + x^2, where the powers of x are the possibilities of what I might spend (0 or 2). Again, the coefficients do the counting: I have 1 way to spend $0 and 1 way to spend $2, and no ways to spend any other amount of money.

DPatrick (19:31:02)
What is the generating function for your spending?

TheDreamer (19:31:09)

s0mp (19:31:12)

kingof20penguins (19:31:19)

Barnacle (19:31:28)

gopherhole112_2 (19:31:32)

DPatrick (19:31:40)
That's right.

DPatrick (19:31:44)
Since you will spend $0, $2, or $4, your generating function includes x^0, x^2, and x^4:

DPatrick (19:31:53)

DPatrick (19:31:59)
We have one term for each possibility: 0, 2, or 4, and the coefficient of each of these possibilities is 1, since there's only 1 way each possibility can occur.

DPatrick (19:32:26)
How can we find all the possibilities of the total amount of money we'll spend together from our 2 generating functions?

justdudxit (19:32:34)

NoSoupForYou (19:32:42)
Multiplying the functions together

gopherhole112_2 (19:32:54)
multiply them?

TheDreamer (19:33:00)
multiply the 2 generating functions

DPatrick (19:33:13)
To find all the possibilities, we have to take each of my possibilities (0 and 2) and add them to each of yours (0,2,4). When we use our generating functions, these numbers are in the exponents. To get them to add, we multiply the generating functions like this:

DPatrick (19:33:20)

DPatrick (19:33:38)
When we expand, we get each of our cases:

DPatrick (19:33:54)

DPatrick (19:34:17)
Make sure you see how each of these terms corresponds to exactly one of the possibilities of the amount of money we spend (and the way we spend it).

DPatrick (19:34:36)

DPatrick (19:34:43)
What does this tell us about the number of ways we might spend $2 together?

gopherhole112_2 (19:34:52)
there are two ways

monchaita (19:34:53)

justdudxit (19:34:53)
there are 2 of them

theraj90 (19:34:53)
2 ways

eyefragment (19:34:53)
there are 2 ways

DPatrick (19:35:14)

DPatrick (19:35:36)
How many ways might we spend exactly $5 together?

monchaita (19:35:41)

justdudxit (19:35:41)

NoSoupForYou (19:35:42)

gopherhole112_2 (19:35:45)

Barnacle (19:35:45)
0 ways.

DPatrick (19:35:56)
There is no way we can spend $5 - the coefficient of x^5 is 0.

DPatrick (19:36:10)
One more: how many ways might we spend exactly $6 together?

NoSoupForYou (19:36:14)

theraj90 (19:36:15)

justdudxit (19:36:17)

peeta (19:36:19)

Calculus_2 (19:36:19)

math88fun (19:36:19)

Monkey (19:36:23)

DPatrick (19:36:32)
The coefficient of x^6 is 1 - we can only produce x^6 in one way, consequently, we can only spend $6 in one way.

DPatrick (19:36:41)
If you're still confused about how generating functions allow us to count, consider this picture:

DPatrick (19:36:48)

DPatrick (19:37:25)
Don't just memorize ""coefficients = number of ways...."" Understand why this is so -- we are using the multiplication of polynomials to work through our casework.

DPatrick (19:38:00)
Obviously this was a pretty trivial example, but it's good to work through a really transparent example like this to get an idea of what's going on.

DPatrick (19:38:14)
Let's try another basic example:

DPatrick (19:38:21)
After a cheap dinner with two of my friends, we all pitch in for a tip. Kai gives 1, 2, or 3 dollars. Anna and I each give 1 or 2 dollars.

DPatrick (19:38:24)

DPatrick (19:38:29)
(If you click on the link, a copy of the problem statement will appear in a separate window -- use it to follow along as we work through the problem.)

DPatrick (19:38:48)
We'll use generating functions to determine in how many ways we can come up with each possible amount.

DPatrick (19:38:56)
What is Kai's generating function?

justdudxit (19:39:01)

NoSoupForYou (19:39:05)

Monkey (19:39:07)

Barnacle (19:39:09)
x + x^2 + x^3

monchaita (19:39:19)

math88fun (19:39:20)

theraj90 (19:39:25)
x^1 + x^2 + x^3

eyefragment (19:39:27)

DPatrick (19:39:40)
Kai's generating function is x+x^2+x^3. (Three possibilities - $1, $2, $3, and one way for each)

DPatrick (19:39:46)
And my generating function?

justdudxit (19:39:50)

Monkey (19:39:51)

madpenguin5000 (19:39:56)

eyefragment (19:39:56)

Sabre_X (19:39:57)

math88fun (19:39:57)

danthemanvt (19:39:58)

Barnacle (19:39:58)

DPatrick (19:40:21)
My generating function is x+x^2. (My choices are $1 or $2, with one way for each.)

DPatrick (19:40:31)
Since Anna's options are the same as mine, Anna's is x+x^2 also.

DPatrick (19:40:36)
So, what is the generating function for all of us together?

Barnacle (19:40:54)

Sabre_X (19:40:56)

liangchene (19:40:57)

NoSoupForYou (19:41:02)

DPatrick (19:41:21)

DPatrick (19:41:40)
Each term of the expansion of this product corresponds to one possible way we can pay the bill. When we group terms of like powers, we find how many ways to pay the amount of the power.

DPatrick (19:42:07)
What is this product when expanded?

Monkey (19:42:13)

justdudxit (19:42:33)

Barnacle (19:43:01)
x^3 + 3x^4 + 4x^5 + 3x^6 + x^7

gopherhole112_2 (19:43:01)

DPatrick (19:43:20)

DPatrick (19:43:38)
As a quick check, do the coefficients add up to the right number?

math88fun (19:43:49)

Monkey (19:43:53)

Barnacle (19:43:54)
1+3+4+3+1=12 = 3*2*2

NoSoupForYou (19:44:00)
yes: 2*2*3=12

DPatrick (19:44:14)
Indeed, they add up to 12, which is what we expected (since there are 12=3*2*2 possibilities for us to raise the cash for the tip).

DPatrick (19:44:35)
Now we can read off some answers to some questions, such as: How many ways can we pay $6?

monchaita (19:44:42)

Monkey (19:44:42)

NoSoupForYou (19:44:44)

Barnacle (19:44:45)

danthemanvt (19:44:48)

theraj90 (19:44:48)

Sabre_X (19:44:49)
3 ways

gopherhole112_2 (19:44:51)

lowest_reynolds (19:44:52)
3 ways.

math88fun (19:44:53)

DPatrick (19:45:01)
The coefficient of x^6 is 3, so there are 3 ways to form x^6 in our generating function, and hence there are 3 ways for us to pay $6.

DPatrick (19:45:13)
Similarly, there is 1 way to pay $3, 3 ways to pay $4, 4 ways to pay $5, and 1 way to pay $7.

DPatrick (19:45:50)
Once again, we see the key idea: the coefficients of the generating function contain our counting data.

DPatrick (19:46:05)
Let's try a slightly more complicated example:

DPatrick (19:46:12)
We have 25 people at our party. We all agree to pitch in $1 or $2 each for snacks, except for BigSpender, who will pay $3, $5, or $9. In how many different ways can we come up with exactly $39 for snacks?

DPatrick (19:46:17)

DPatrick (19:46:38)
How do we build the generating function?

Barnacle (19:46:59)
(x+x^2)^24 * (x^3 + x^5 + x^9)

gopherhole112_2 (19:47:02)

eyefragment (19:47:04)
We would need to find the coefficient of x^39 in (x+x^2)^24*(X^3+x^5+x^9)

theraj90 (19:47:13)
(x+x^2)^24 * (x^3+x^5+x^9)

sammath (19:47:15)

DPatrick (19:47:25)

DPatrick (19:47:37)
Each of the first 24 people has x+x^2 as the generating function, since they spend either $1 or $2.

DPatrick (19:47:47)
BigSpender's generating function is x^3 + x^5 + x^9.

DPatrick (19:48:14)
So combining the first 24 functions along with BigSpender's, we have:

DPatrick (19:48:16)

DPatrick (19:48:59)
Care to multiply that out?

Barnacle (19:49:09)

Sabre_X (19:49:09)

DPatrick (19:49:19)
Me neither.

DPatrick (19:49:26)
But we need only find the coefficient of x^39 because all we're interested in is how many ways we can come up with $39.

Monkey (19:49:09)
Use binomial theorem.

liangchene (19:49:31)
use binomial theorem

sammath (19:49:44)
we dont have to, we can use binomial theorem for each of bigspenders different possibilities, 3, 5, and 9

DPatrick (19:50:07)
Right, we can reduce our work considerably by using the Binomial Theorem.

liangchene (19:50:11)
39 = 3 + 36 = 5 + 34 = 9+30

DPatrick (19:50:45)
Right, so we need the sum of the coefficients of the x^36, x^34, and x^30 terms in (x+x^2)^24.

DPatrick (19:50:57)
How do we find these coefficients?

math88fun (19:51:08)
binomial theorem

sammath (19:51:11)
using the binomial theorem

justdudxit (19:51:23)
you can factor out an x^24 to make the job easier

DPatrick (19:51:31)

DPatrick (19:51:47)

DPatrick (19:51:55)

DPatrick (19:52:05)

DPatrick (19:52:30)
So we need the sum of the coefficients of the x^12, x^10, and x^6 terms of (1+x)^24.

DPatrick (19:52:35)
Now it's easy, right?

liangchene (19:52:44)
C(24,12) C(24,10) C(24,6)

Barnacle (19:52:53)
24c12 + 24c10 + 24c6

TheDreamer (19:52:53)

DPatrick (19:53:24)
Right, this was our very first example at the beginning: the coefficient of x^k in (1+x)^n is C(n,k).

DPatrick (19:53:40)
So our 3 coefficients are C(24,12), C(24,10), and C(24,6).

DPatrick (19:54:16)

math88fun (19:47:41)
4800008 ways

chess64 (19:53:47)

Monkey (19:53:57)
We end up with the monstrous 4800008.

NoSoupForYou (19:54:32)
The answer is 4800008

DPatrick (19:54:39)
That's right.

DPatrick (19:55:16)
Here's a more abstract problem which we can solve using generating functions:

DPatrick (19:55:20)
Use generating functions to find the number of solutions in nonnegative integers to the equation b + c + d = 40.

DPatrick (19:55:24)

DPatrick (19:55:48)
What is the generating function for b?

justdudxit (19:55:59)

TheDreamer (19:56:03)

Monkey (19:56:08)

Barnacle (19:56:11)
x^0 + ... + x^40

gopherhole112_2 (19:56:17)

eyefragment (19:56:22)
well, each value, (b,c,d) can range from 0 to 40, thus we have (1+x+x^2...x^40) for each, where 1 represents x^0 (since 0 is allowed)

DPatrick (19:56:56)
Do we want to cap our generating function at the x^40 term?

math88fun (19:57:05)

Barnacle (19:57:08)
yes, becuase otherwise c,d have to be negative

NoSoupForYou (19:57:11)

justdudxit (19:57:20)
you can, but its not complete otherwise

DPatrick (19:57:52)
Well, I'm going to argue that we don't.

DPatrick (19:58:20)
If we look just at the condition on b alone, all it says is that ""b is a nonnegative integer"".

DPatrick (19:58:27)
The constraints of the problem placed solely on b don't cap b at 40.

DPatrick (19:58:41)
Now of course itThe equation does, but only when combined with constraints on c and d.

DPatrick (19:58:46)
oops...let me try that again!

DPatrick (19:59:06)
Of course the equation does require that b<=40, but only when combined with constraints on c and d.

DPatrick (19:59:27)
Plus, as we'll see in a bit, the algebra is actually easier and nicer if we don't cap b at 40.

DPatrick (19:59:49)

chess64 (19:59:57)
But it won't work for larger b, so how does that make sense?

sammath (20:00:02)
but after you multiply the generating functions together, everything that was involved with b is greater than 40 will have an exponent greater than 40

DPatrick (20:00:44)
That's right -- when we look for the x^40 term later, any terms above x^40 in the generating function of b won't contribute.

DPatrick (20:01:04)
This may seem confusing now, but hopefully it will become clearer as we proceed with the problem.

Barnacle (20:01:19)
so is it not a problem if we DID cap at 40?

DPatrick (20:01:44)
Well, the algebra would actually turn out to be a little messier, as we'll soon see.

DPatrick (20:02:16)

DPatrick (20:02:26)
So what is our generating function for b + c + d?

justdudxit (20:02:35)
cube that

eyefragment (20:02:45)

Barnacle (20:02:46)

NoSoupForYou (20:02:53)

DPatrick (20:03:08)

DPatrick (20:03:24)
We seek the x^40 term in this expansion. How shall we find it?

sammath (20:03:34)
binomial theorem

NoSoupForYou (20:03:48)
binomial theorem?

math88fun (20:03:48)
Once again binomial theorem

DPatrick (20:04:35)
How do we use it here?

hilbert (20:03:37)
each of those equals 1/(1-x) because they are geometric series

DPatrick (20:04:56)
Hmmm...let's come back to this very interesting observation a bit later.

DPatrick (20:05:50)

Monkey (20:06:26)

Barnacle (20:06:37)

monchaita (20:06:49)

NoSoupForYou (20:06:54)

kingof20penguins (20:07:01)

DPatrick (20:07:30)
That's right -- and I really like the way that NoSoupForYou wrote it!

DPatrick (20:07:45)

DPatrick (20:07:51)

DPatrick (20:08:17)

gopherhole112_2 (20:08:39)

justdudxit (20:09:00)
the coefficient of x^n will be the nth triangular number

Monkey (20:09:19)
(1+3x+6x^2+10x^3+15x^4+...). It's triangular numbers.

monchaita (20:09:21)

sammath (20:09:22)

liangchene (20:09:24)

TheDreamer (20:09:25)
1+3x+6x^2+10x^3...(triangle number coefficients)

sammath (20:09:27)
the triangular numbers!

DPatrick (20:09:44)

DPatrick (20:09:55)

DPatrick (20:10:16)

Monkey (20:10:34)
Answer's 861=(41)(42)/2.

justdudxit (20:10:38)
so the answer is 861

DPatrick (20:11:15)
Indeed, the coefficient of x^40 is 1+2+...+41 = 41(42)/2 = 861.

Barnacle (20:11:04)

TheDreamer (20:11:13)
why does this turn out to be 42choose2?

DPatrick (20:11:26)
Good observation!

DPatrick (20:11:40)

Monkey (20:11:01)
What happens if we like 6th powered this polynomial?

DPatrick (20:12:20)
Another good question!

DPatrick (20:12:27)

Barnacle (20:12:56)
3c3 + 4c3*x + 5c3*x^2 + ...

gopherhole112_2 (20:13:07)
C(3,3) C(4,3) C(5,3)...

chess64 (20:13:13)
the sum of triangular numbers?

DPatrick (20:13:38)
That's right!

DPatrick (20:13:47)

DPatrick (20:14:18)

DPatrick (20:14:42)

DPatrick (20:15:10)

Monkey (20:14:21)
Is the pattern always going to be n choose n+(n+1 choose n)x+(n+2 choose n)x^2+...?

DPatrick (20:15:53)
Indeed it is! You can prove it using induction and the Hockey Stick Theorem.

DPatrick (20:16:01)

Barnacle (20:15:57)
does the value of x have any significance in these problems or is it just a carrier for our coefficients/exponents?

DPatrick (20:17:18)
Your latter explanation is the right one: it's just a way to carry the coefficients and exponents around.

DPatrick (20:17:31)
But it also lets us do some nifty algebraic tricks.

DPatrick (20:17:38)
Let's go back to hilbert's observation from earlier:

DPatrick (20:17:42)

DPatrick (20:17:59)
Thus, we can write

DPatrick (20:18:06)

DPatrick (20:18:27)
Infinite geometric series and generating functions often come together.

TheDreamer (20:18:42)
doesn't this only work if x<1?

peeta (20:18:56)
only 0<x<1

DPatrick (20:19:36)
Yes, that's correct, but we don't care what the value of x is! this goes back to Barnacle's question: we're really just thinking of the x as a way to carry the coefficents and exponents around.

Sabre_X (20:19:45)
but isnt x an irrelevant value anyway? so might as well make it 0<x<1

DPatrick (20:20:01)
That's exactly the way you should look at it!

Barnacle (20:19:07)

justdudxit (20:19:28)
you mean -1<x<1

TheDreamer (20:20:02)

DPatrick (20:20:38)
You're right, but again, the beauty of the thing is that we don't really have to worry about it: as long as it works for some values of x, we're fine!

DPatrick (20:21:18)
So far we've been doing fairly simple problem, that would have been fairly easy to solve without generating function. We'll finish up with an example starts to show the power of generating functions -- how they simplify the work quite a bit.

DPatrick (20:21:39)
I'm doling out 100 lollipops to 5 kids. Two of the kids only want at most 1 lollipop. Two kids will take any odd number of lollipops, and one kid will take any number of lollipops (including 0). How many different ways can I distribute the lollipops (consider the kids to be distinguishable, but the lollipops are not)?

DPatrick (20:21:58)

DPatrick (20:22:10)
How can we set this up with generating functions?

DPatrick (20:22:29)
What is the generating function for the 0-or-1 lollipop kids?

math88fun (20:22:33)

monchaita (20:22:37)

eyefragment (20:22:40)
just (1+x)

NoSoupForYou (20:22:41)

DPatrick (20:22:53)
Right -- my question was ambiguous.

DPatrick (20:23:03)
The generating function for each 0-or-1 lollipop kid is (1+x), so for both of them together it's (1+x)^2.

DPatrick (20:23:15)
How about the ""any number of lollipops"" kid?

NoSoupForYou (20:23:28)

chess64 (20:23:31)

monchaita (20:23:33)

justdudxit (20:23:33)

sammath (20:23:35)

DPatrick (20:23:52)

DPatrick (20:24:02)
And how about the ""odd number of lollipops"" kids?

theraj90 (20:23:36)

math88fun (20:24:11)

madpenguin5000 (20:24:14)

theraj90 (20:24:18)

NoSoupForYou (20:24:24)

Sabre_X (20:24:26)

monchaita (20:24:27)

justdudxit (20:24:27)

DPatrick (20:24:51)

Sabre_X (20:25:00)
so (1+x)^2 * (1+x+x^2...) * (x+x^3+x^5...)^2 would be for the whole problem

DPatrick (20:25:29)

Barnacle (20:25:29)
and we want coefficient for x^100

DPatrick (20:25:38)

DPatrick (20:25:44)
Our expression is pretty ugly. Can we simplify it?

DPatrick (20:26:06)
(This is where the magic happens!)

Monkey (20:25:55)
factor out an x for odd kids.

Barnacle (20:26:02)
Factor an x out of the odd lollipops kids

DPatrick (20:26:22)
Good start.

DPatrick (20:26:47)

chess64 (20:26:29)
Sum of Geometric sequences?

DPatrick (20:27:09)
Right -- now we want to use the fact that we have geometric sequences.

kingof20penguins (20:27:15)
turn 1+x+x^2..... into 1/(1-x)?

DPatrick (20:27:25)

DPatrick (20:27:32)
What about the other infinite term?

justdudxit (20:27:46)

NoSoupForYou (20:27:46)

liangchene (20:27:52)

Monkey (20:27:54)

kingof20penguins (20:27:55)
turn it into 1/(1-x^2)?

Sabre_X (20:27:56)

DPatrick (20:28:01)

DPatrick (20:28:19)

DPatrick (20:28:44)
Can we simplify further?

Barnacle (20:28:40)
oh difference of squares in the last term of the product

TheDreamer (20:28:49)
cancel out by factoring 1-x^2

DPatrick (20:29:00)
Indeed, we can!

DPatrick (20:29:06)

chess64 (20:29:22)

DPatrick (20:29:37)
Isn't that cool?

DPatrick (20:29:46)

eyefragment (20:30:20)
yes, since 1/(1-x)^3 was previously found

justdudxit (20:30:20)
we've seen this before....

DPatrick (20:30:31)
Indeed we have!

DPatrick (20:30:51)

DPatrick (20:31:25)

DPatrick (20:31:38)
This is typically how we use the power of generating functions: set the problem up, then use the tools of algebra to simplify it.

DPatrick (20:32:06)
We have just scratched the surface of generating functions. If you'd like to learn more, generating functions are covered in greater detail in the Art of Problem Solving's Intermediate Counting & Probability course. You can also read more about generating functions in the following sources, arranged from most basic to most advanced:

DPatrick (20:32:13)
[i]The Art of Problem Solving[/i], Volume 2, Chapter 17

[i]Partitions of Integers[/i] by Joseph Laurendi. This paper (by an AoPS student) is available on our website at

[i]generatingfunctionology[/i], by Herbert S. Wilf. Yes, that really is the name of the book. This book can be downloaded (for free!) from
[b]Warning[/b]: this book is quite advanced.

DPatrick (20:32:46)
Thanks for attending today's Math Jam! Have a nice evening!

Copyright © 2017 AoPS Incorporated. This page is copyrighted material. You can view and print this page for your own use, but you cannot share the contents of this file with others.


Stay Connected

Subscribe to get news and
updates from AoPS, or Contact Us.
© 2017
AoPS Incorporated
Invalid username
Login to AoPS