A generating functions approach to counting
by t0rajir0u, Jan 22, 2008, 1:47 AM
Problem (Balls and Urns): How many ways are there to distribute 
indistinguishable balls among 
distinguishable urns? In other words, how many ordered tuplets 
of non-negative integers satisfy
?
Solution: The answer to this problem is well-known, but the approach that I will take (by generating functions) is in my opinion very instructive.
First, we define the notion of a generating function. Given a sequence
, we wish to study it by studying the function
.
We will use the notation![$ [x^k] F(x)$](//latex.artofproblemsolving.com/7/8/e/78efcce5963c74b069841b10cf5a96b3755c4be1.png)
to denote the coefficient of 
in the series expansion of 
. Thus ![$ [x^k] A(x) = a_k$](//latex.artofproblemsolving.com/5/7/5/575543ad126aec25bb94d1b4d3251d3b686aa8cc.png)
.
Lemma: If
are the generating functions of 
, respectively, then
![$ [x^k] A(x) B(x) = \sum_{i + j = k} a_i b_j$](//latex.artofproblemsolving.com/3/c/1/3c1e7045d4a0020a89c2860a5edb924bf39a5dcd.png)
.
In other words, multiplying the generating functions of two sequences produces a convolution of their terms. This turns out to be very useful in counting.
Consider the sequence
that gives the number of ways we can put balls into a single urn. Since the balls are indistinguishable, there is only one way to do this, so the corresponding generating function is
.
The sequence we are really interested in gives us the number of ways we can put balls into urns. As we have stated, this is the number of solutions to . But this is exactly the type of expression that appears in the lemma! In fact, the generating function we are really after is
.
But how do we go about finding the coefficients of this function?
The familiar Binomial Theorem
is taught to apply when is a non-negative integer. In fact, it applies for non-integer, non-rational, even non-real ; we just need 
to be the Newton polynomial (as per the previous entry) in .
General Binomial Theorem: For
, we have
.
Proof: We can arrive at this conclusion by the familiar method of finding a Taylor series.
The generating function we were after is
. But now that we have the general binomial theorem, we can calculate this as
.
Now, note that
$ \begin{eqnarray*} { - r \choose k} ( - 1)^k & = & \frac { - r( - r - 1)...( - r - (k - 1))}{k!} ( - 1)^k \\ & = & \frac {r(r + 1)...(r + (k - 1))}{k!} \\ & = & {r + k - 1 \choose r - 1} \\ \end{eqnarray*}$
hence our final generating function can be written
.
This tells us that the number of ways to distribute balls among urns is 
. 
The "balls-and-urns" formula above shows up in a surprising number of combinatorial problems, and both it and the generating functions approach are worth learning. For a more thorough discussion, I highly recommend the online book generatingfunctionology.
Practice Problem 1: Prove Binet's formula using the generating function
. (This proof is also in generatingfunctionology, and is in my opinion the most elegant one (although I enjoy the matrix method as well ).)
Practice Problem 2: Prove the balls-and-urns formula by a combinatorial argument.
Practice Problem 3 (Putnam 2007 A3): Let
be a positive integer. Suppose that the integers 
are written down in random order. What is the probability that at no time during this process, the sum of the integers that have been written up to that time is a positive integer divisible by 
Your answer should be in closed form, but may include factorials.
indistinguishable balls among 
distinguishable urns? In other words, how many ordered tuplets 
of non-negative integers satisfy
?
Solution: The answer to this problem is well-known, but the approach that I will take (by generating functions) is in my opinion very instructive.
First, we define the notion of a generating function. Given a sequence
, we wish to study it by studying the function
.We will use the notation
![$ [x^k] F(x)$](http://latex.artofproblemsolving.com/7/8/e/78efcce5963c74b069841b10cf5a96b3755c4be1.png)
to denote the coefficient of 
in the series expansion of 
. Thus ![$ [x^k] A(x) = a_k$](http://latex.artofproblemsolving.com/5/7/5/575543ad126aec25bb94d1b4d3251d3b686aa8cc.png)
.Lemma: If
are the generating functions of 
, respectively, then![$ [x^k] A(x) B(x) = \sum_{i + j = k} a_i b_j$](http://latex.artofproblemsolving.com/3/c/1/3c1e7045d4a0020a89c2860a5edb924bf39a5dcd.png)
.In other words, multiplying the generating functions of two sequences produces a convolution of their terms. This turns out to be very useful in counting.
Consider the sequence
that gives the number of ways we can put balls into a single urn. Since the balls are indistinguishable, there is only one way to do this, so the corresponding generating function is
.The sequence we are really interested in gives us the number of ways we can put
balls into urns. As we have stated, this is the number of solutions to . But this is exactly the type of expression that appears in the lemma! In fact, the generating function we are really after is
.But how do we go about finding the coefficients of this function?
The familiar Binomial Theorem
is taught to apply when is a non-negative integer. In fact, it applies for non-integer, non-rational, even non-real ; we just need 
to be the Newton polynomial (as per the previous entry) in .General Binomial Theorem: For
, we have
.Proof: We can arrive at this conclusion by the familiar method of finding a Taylor series.
The generating function we were after is
. But now that we have the general binomial theorem, we can calculate this as
.Now, note that
$ \begin{eqnarray*} { - r \choose k} ( - 1)^k & = & \frac { - r( - r - 1)...( - r - (k - 1))}{k!} ( - 1)^k \\ & = & \frac {r(r + 1)...(r + (k - 1))}{k!} \\ & = & {r + k - 1 \choose r - 1} \\ \end{eqnarray*}$
hence our final generating function can be written
.This tells us that the number of ways to distribute
balls among urns is 
. The "balls-and-urns" formula above shows up in a surprising number of combinatorial problems, and both it and the generating functions approach are worth learning. For a more thorough discussion, I highly recommend the online book generatingfunctionology.
Practice Problem 1: Prove Binet's formula using the generating function
. (This proof is also in generatingfunctionology, and is in my opinion the most elegant one (although I enjoy the matrix method as well ).)Practice Problem 2: Prove the balls-and-urns formula by a combinatorial argument.
Practice Problem 3 (Putnam 2007 A3): Let
be a positive integer. Suppose that the integers 
are written down in random order. What is the probability that at no time during this process, the sum of the integers that have been written up to that time is a positive integer divisible by 
Your answer should be in closed form, but may include factorials.
for 
April 2009
March 2009