Combinatorics (Table of contents)
# Generating Functions

## Two examples

## Definition of the generating function

**Definition** Given a sequence \((a_n)_{n=0}^{\infty}\) the generating function corresponding to the sequence \((a_n)\) is the function defined as
\[F(X)=\sum_{n=0}^{\infty} a_nX^n.\]
**Example**
Find the generating function for the sequence \((a_n)\) defined as \(a_n=1\) for all \(n\geq 0\).
**Example**
Find the generating function for the sequence \(a_n\) defined as \(a_n=n\) for \(n\geq 0\).
**Definition** If \(a\in\mathbb R\) and \(k\in\mathbb N\) then \[\binom{a}{k}=\frac{a(a-1)\cdots(a-k+1)}{k!}.\]
**Theorem**
If \(a\in\mathbb R\) then:
\[\left(1+X\right)^a=\sum_{k=0}^{\infty}\binom{a}kX^k.\]
**Exercise** 1. Evaluate \(\binom{3}{8}\), \(\binom{\frac12}{3}\), and \(\binom{-5}9\).
**Exercise** 2
Consider the sequence \((a_n)_{n=0}^{\infty}\) defined as \(a_n=1\) for \(0\leq n\leq 3\) and \(a_n=0\) for \(n\geq 4\). Denote by \(F\) the generating function for the sequence \((a_n)_{n=0}^{\infty}\). Determine \(F(2)\).
**Exercise** 3
Consider the sequence \((a_n)_{n=0}^{\infty}\) defined as \(a_n=n\) for \(0\leq n\leq 5\) and \(a_n=0\) for \(n\geq 6\). Denote by \(F\) the generating function for the sequence \((a_n)_{n=0}^{\infty}\). Determine \(F(-2)\).
## Using generating functions to solve problems in combinatorics

**Example**
Find the number of ways of distributing \(15\) apples to \(5\) students.
**Example**
\(N_k\) is the number of pairs \((a,b)\) of non-negative integers such that \(ka+(k+1)b=n+1-k\).
**Example**
## Exponential generating function

**Definition** The exponential generating function corresponding to the sequence \((a_n)_{n=0}^{\infty}\) is the function defined as \[H(X)=\sum_{n=0}^{\infty} \frac{a_n}{n!}X^n.\]
**Example**
Suppose that there are \(p\) different kinds of objects, each in infinite supply. Let \(a_k\) be the number of different ways to arrange \(k\) of these objects in a line. Find \(a_k\) explicitly by using exponential generating functions.
**Example**
Let \(n\) and \(k\) be positive integers with \(k\geq n\) and \(k-n\) an even number.
Let \(2n\) lamps labelled \(1\), \(2\), \(\dots\), \(2n\) be given, each of which can be either *on* or *off*. Initially all the lamps are off. We consider the sequence of steps: at each step one of the lamps is switched (from on to off or from off to on). Let \(N\) be the number of such sequences consisting of exactly \(k\) steps and resulting in the state where lamps \(1\) through \(n\) are all on, and lamps \(n+1\) through \(2n\) are all off. Let \(M\) be the number of such sequences consisting of \(k\) steps and resulting in the state where lamps \(1\) through \(n\) are all on, and lamps \(n+1\) through \(2n\) are all off, but where none of the lamps \(n+1\) through \(2n\) is ever switched on. Determine the ratio \(\frac NM\).

The fastest way to learn and understand the method of generating functions is to look at the following two problems. You have to read the solutions below the problems, even if you find them boring.

Problem (Combinatorics)
Find the number of ways to distribute 4 identical apples to 3 different students. All apples have to be distributed, and each student is allowed to have from 0 to 4 apples. | \(\quad\) |
Problem (Algebra)
Find the coefficient of \(X^4\) in the expansion of the polynomial \begin{eqnarray*}P(X)&=&\left(1+X+X^2+\cdots+X^{100}\right)^3.\end{eqnarray*} |

One distribution of apples to students is when A gets 2 apples, B gets 1, and C gets 1. We can write the ordered triple (2,1,1) to correspond to this distribution. We will list all possible ways of giving apples to students, and we will do this by considering different cases. |
The terms in the first parenthesis are black, the terms in the second are blue, and the terms in the third parenthesis are red. This will make it easier to keep track of things when we start multiplying them out. The coefficient of \(X^4\) is obtained when all terms of this form are added: \(X^2\) \(\cdot\) \(X\)\(\cdot\)\(X\), \(X\) \(\cdot\) \(1\)\(\cdot\)\(X^3\), etc. We again need a systematic listing of all the terms. | |

- \(1^{\circ}\) The student A gets 0 apples:
- \(1^{\circ}.1\) The student B gets 0 apples:
- Now, student C has to get all 4 apples. This completes the case \(1^{\circ}.1\). We will denote this distribution by (0,0,4).
- \(1^{\circ}.2\) B gets 1 apple:
- The student C must get 3 apples. The distribution is (0,1,3).
- \(1^{\circ}.3\) B gets 2 apples:
- C must have 2 apples, giving the distribution (0,2,2).
- \(1^{\circ}.4\) B gets 3 apples:
- C must get 1, and the distribution is (0,3,1).
- \(1^{\circ}.5\) B gets 4 apples:
- C must get 0, and the distribution is (0,4,0).
- \(1^{\circ}.1\) The student B gets 0 apples:
- \(2^{\circ}\) A gets 1 apple:
- \(2^{\circ}.1\) B gets 0 apples:
- The student C must get 3, and the distribution is (1,0,3).
- \(2^{\circ}.2\) B gets 1 apple:
- C must get 2, the distribution is (1,1,2).
- \(2^{\circ}.3\) B gets 2 apples:
- C must get 1, the distribution is (1,2,1).
- \(2^{\circ}.4\) B gets 3 apples:
- C must get 0, the distribution is (1,3,0).
- \(2^{\circ}.1\) B gets 0 apples:
- \(3^{\circ}\) A gets 2 apples:
- \(3^{\circ}.1\) B gets 0 apples:
- The student C must get 2, and the distribution is (2,0,2).
- \(3^{\circ}.2\) B gets 1 apple:
- C must get 1, the distribution is (2,1,1).
- \(3^{\circ}.3\) B gets 2 apples:
- C must get 0, the distribution is (2,2,0).
- \(3^{\circ}.1\) B gets 0 apples:
- \(4^{\circ}\) A gets 3 apples:
- \(4^{\circ}.1\) B gets 0 apples:
- The student C must get 1, and the distribution is (3,0,1).
- \(4^{\circ}.2\) B gets 1 apple:
- C must get 0, the distribution is (3,1,0).
- \(4^{\circ}.1\) B gets 0 apples:
- \(5^{\circ}\) A gets 4 apples:
- Now both B and C have to get 0 apples each, giving the distribution (4,0,0).
Now we can count and see that we considered a total of \(15\) cases. Hence there are \(15\) ways of distributing \(4\) apples to \(3\) students. |
- \(1^{\circ}\) The contribution from the first parenthesis is \(1=X^0\):
- \(1^{\circ}.1\) The contribution from the second parenthesis is \(1=X^0\).
- The contribution from the third parenthesis has to be \(X^4\), and the summand in this case is \(1\) \(\cdot\) \(1\)\(\cdot\)\(X^4\).
- \(1^{\circ}.2\)
The contribution from the second parenthesis is \(X\)
- The third gives \(X^3\), and the summand is \(1\) \(\cdot\) \(X\)\(\cdot\)\(X^3\).
- \(1^{\circ}.3\) Second parenthesis gives \(X^2\)
- The third gives \(X^2\), and the summand is \(1\) \(\cdot\) \(X^2\)\(\cdot\)\(X^2\).
- \(1^{\circ}.4\) Second parenthesis gives \(X^3\)
- The third gives \(X\), and the summand is \(1\) \(\cdot\) \(X^3\)\(\cdot\)\(X\).
- \(1^{\circ}.5\) Second parenthesis gives \(X^4\)
- The third gives \(X^0=1\), and the summand is \(1\) \(\cdot\) \(X^4\)\(\cdot\)\(1\).
- \(1^{\circ}.1\) The contribution from the second parenthesis is \(1=X^0\).
- \(2^{\circ}.1\) The second gives \(1\)
- The third gives \(X^3\), and the summand is \(X\) \(\cdot\) \(1\)\(\cdot\)\(X^3\).
- \(2^{\circ}.2\) The second gives \(X\)
- The third gives \(X^2\), and the summand is \(X\) \(\cdot\) \(X\)\(\cdot\)\(X^2\).
- \(2^{\circ}.3\) The second gives \(X^2\)
- The third gives \(X\), and the summand is \(X\) \(\cdot\) \(X^2\)\(\cdot\)\(X\).
- \(2^{\circ}.4\) The second gives \(X^3\)
- The third gives \(1\), and the summand is \(X\) \(\cdot\) \(X^3\)\(\cdot\)\(1\).
- \(3^{\circ}.1\) The second gives \(1\)
- The third gives \(X^2\), and the summand is \(X^2\) \(\cdot\) \(1\)\(\cdot\)\(X^2\).
- \(3^{\circ}.2\) The second gives \(X\)
- The third gives \(X\), and the summand is \(X^2\) \(\cdot\) \(X\)\(\cdot\)\(X\).
- \(3^{\circ}.3\) The second gives \(X^2\)
- The third gives \(1\), and the summand is \(X^2\) \(\cdot\) \(X^2\)\(\cdot\)\(1\).
- \(4^{\circ}.1\) The second gives \(1\)
- The third gives \(X\), and the summand is \(X^3\) \(\cdot\) \(1\)\(\cdot\)\(X\).
- \(4^{\circ}.2\) The second gives \(X\)
- The third gives \(1\), and the summand is \(X^3\) \(\cdot\) \(X\)\(\cdot\)\(1\).
- Now both second and third parenthesis have to contribute \(1\), and the term is \(X^4\) \(\cdot\) \(1\)\(\cdot\)\(1\).
The sum of the previous terms is \(15X^4\). |

The generating function for the sequence \(1\), \(0\), \(0\), \(\dots\), is the function \(F(X)=1\), while the generating function for the sequence \(1\), \(1\), \(1\), \(0\), \(0\), \(0\), \(0\), \(\dots\), is \(F(X)=1+X+X^2\).

*Remark.*
Infinite series that we are dealing with do not converge for all values of \(X\). We don’t worry about that stuff in this introductory article. In the theory of generating functions we may either choose to always restrict ourselves to the interval of convergence of these series, or we may consider them as *formal power series* in which case they are members of infinite dimensional vector spaces for which we can properly defined the desired operations.

It is useful to know that \begin{eqnarray*}\left(\frac1{1-X}\right)^{\prime}&=&\frac1{(1-X)^2}, \quad\quad\quad \mbox{ and} \newline \left(\frac1{1-X}\right)^{(k)}&=&\frac{ k!}{(1-X)^{k+1}}.\end{eqnarray*}

We often refer to the following general binomial theorem (which is easily proved using Taylor’s expansion from calculus). In order to state it, we first define a *general binomial coefficient*.

Here is the binomial formula:

The following exercise will help you understand this new notion of binomial coefficients.

The next two exercises is about the definition of generating function.

We’ll start and end with an example that explains how to use generating functions to solve a with students and apples similar to the one above.

Let \(n\) be a positive integer. Assume that:

Find \(N_1+N_2+\cdots+ N_{n+1}\).

The following example illustrates how to use multi-variable calculus in solving combinatorial problems with generating functions.

By a partition of an integer \(n\geq1\), we mean a representation of \(n\) as a sum of one or more positive integers where the summands must be put in nondecreasing order. (E.g., if \(n=4\), then the partitions are: \((1,1,1,1)\), \((1,1,2)\), \((1,3)\), \((2,2)\), and \(4\).)

For any partition \(\pi\), define \(A(\pi)\) to be the number of \(1\)’s which appear in \(\pi\), and define \(B(\pi)\) to be the number of distinct integers which appear in \(\pi\). (E.g., if \(n=13\) and \(\pi\) is the partition \((1,1,2,2,2,5)\) then \(A(\pi)=2\) and \(B(\pi)=3\).)

Prove that for any fixed \(n\), the sum of \(A(\pi)\) over all partitions \(\pi\) of \(n\) is equal to the sum of \(B(\pi)\) over all partitions \(\pi\) of \(n\).