Generating Functions

Two examples

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.
 
Problem (Algebra)
 
Find the coefficient of \( X^4 \) in the expansion of the polynomial \[ P(X)=\left(1+X+X^2+X^3+X^4+X^5+\cdots+X^{100}\right)^3.\]

Solution. Let us give the names to our students: A, B, and C.

picture2

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.

Solution. The polynomial looks complicated and we need a systematic approach. Let us first rewrite it in a way that is esthetically more pleasing:

\[ P(X)=\left(1+X+X^2+\cdots+X^{100}\right)\] \[ \quad \quad \quad\cdot \left(1+X+X^2+\cdots+X^{100}\right)\] \[ \quad\quad\quad \cdot \left(1+X+X^2+\cdots+X^{100}\right).\]

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).

  • \( 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).

  • \( 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).

  • \( 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} \) 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 \).

  • \( 2^{\circ} \) The first parenthesis contributes \( X \).

    • \( 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} \) The first parenthesis contributes \( X^2 \).

    • \( 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} \) The first parenthesis contributes \( X^3 \).

    • \( 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 \).

  • \( 4^{\circ} \) The first parenthesis contributes \( X^4 \).

    • 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 \).

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.\]

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 \).

Example
 
Find the generating function for the sequence \( (a_n) \) defined as \( a_n=1 \) for all \( n\geq 0 \).

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.

Example
 
Find the generating function for the sequence \( a_n \) defined as \( a_n=n \) for \( n\geq 0 \).

It is useful to know that \begin{eqnarray*}\left(\frac1{1-X}\right)^{\prime}&=&\frac1{(1-X)^2}, \quad\quad\quad \mbox{ and} \\ \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.

Definition
 
If \( a\in\mathbb R \) and \( k\in\mathbb N \) then \[ \binom{a}{k}=\frac{a(a-1)\cdots(a-k+1)}{k!}.\]

Here is the binomial formula:

Theorem
 
If \( a\in\mathbb R \) then: \[ \left(1+X\right)^a=\sum_{k=0}^{\infty}\binom{a}kX^k.\]

Quiz

It is a good idea now to take a moment and do the following quiz to review the definitions we just covered in the previous section.

Using generating functions in combinatorial problems

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.

Example
 
Find the number of ways of distributing \( 15 \) apples to \( 5 \) students.

Example
 

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

\( N_k \) is the number of pairs \( (a,b) \) of non-negative integers such that \( ka+(k+1)b=n+1-k \).
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.

Example
 

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 \).

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 \).

Homeworks/Quizzes

Quiz 1 (Introduction to generating functions: Definitions)

Quiz 2 (Using generating functions in combinatorics)


2005-2017 IMOmath.com | imomath"at"gmail.com | Math rendered by MathJax
Home | Olympiads | Book | Training | IMO Results | Forum | Links | About | Contact us