Generating Functions

In probability theory, statistics and the theory of Markov chains, the clothesline at hand is woven of the analytic yarn, the Maclauren series strain. It's almost tangible and can be checked point by point wherever the series converges. In combinatorics, the rather delicate threads come from the abstract variety of formal series.

The series is formal in that it is defined as an algebraic, not an analytic concept. Formally speaking, we append to the set of numbers (mostly real numbers on these pages) a new term x, whose nature is quite irrelevant for the construction. The new term and the numbers can be added and multiplied, and both operations are postulated to be commutative: a + x = x + a, ax = xa, for all numbers a. Addition is also required to be distributive with respect to the multiplication. Thus expanded set of real numbers becomes a ring, a mathematical construct with two commutative operations -- addition and multiplication, in which the objects do not always have a multiplicative inverse. They do iff a₀ is not 0. For example,

so that we can state that

Mulitplicative Inverse Property

The series (*) has a multiplicative inverse iff a₀0.

Proof

Let's simply show how to constructively find the inverse f ^-1 in the form

Such an inverse should satisfy f·f ^-1 = 1 + 0x + 0x² + .... Term by term this gives

From the first equation, b₀ = 1/a₀. From the second equation, b₁ = -a₁b₀/a₀. From the second equation, b₂ = -(a₁b₁ + a₂b₀)/a₀, and so on. In this manner indeed, since a₀0, all coefficients b can be found successively.

In analytic terms, x is a variable with the range over the numbers, real or complex, and the identity holds whenever the series on the right is convergent, i.e., whenever |x| < 1. However, in the formal theory we are not concerned with the question of convergence. In this sense, the term generating function is not quite consistent in that the operation of substituting a number for x in order to establish the value of the series at that point, is not legal.

As another example, the binomial theorem

says that the expression (1 + x)ⁿ is the generating function of the sequence of the binomial coefficients C(n,0), C(n,1), ..., C(n,n). Just from this expression we can derive a famous property of the binomial coefficients:

with n factors, gives an immediate interpretation of the coefficients C(n, k) in the binomial theorem. The product on the right requires to select either 1 or x from each of the n factors (1 + x). Thus C(n, k) is the number of ways to select k x's.

The binomial theorem makes frequent appearances not only in combinatorics but also in other branches of mathematics, see, for example, a proof of Lucas' Theorem.

What is the generating function of the series 1, -1, 1, -1, ... ? Obviously, it's

Then

such that the generating function of the series 1, 0, 1, 0, ... is given by

(4)	1/(1 - cx) = 1 + cx + c2x2 + c3x3 + ...,

so that 1/(1 - cx) is the generating function of the series 1, c, c², c³ ...

It's possible to go a step further and ask, What is the generating function of the sequence 1, (1 + x), (1 + x)², (1 + x)³, ... ? An answer must by necessity contain an additional object, other than x, say y, which brings us to the generating functions of more than one argument. For example, from (4) we obtain by substitution

(5)	1 + (1 + x)y + (1 + x)2y2 + (1 + x)3y3 + (1 + x)4y4 ... = 1/(1 - (1 + x)y).

And further,

[xk]1/(1 - (1 + x)y) = 1/(1 - y)·[xk]1/(1 - x·y/(1-y))   = 1/(1 - y)·(y/(1-y))k   = yk/(1-y)k+1.

On the other hand, in (5), we may expand the terms (1 + x)ⁱ according to the binomial theorem

from where [x^k]1/(1 - (1 + x)y) can also be found to be

We thus obtain another useful formula:

which of course could be rewritten in terms of x:

(6)	∑nC(n,k)xn = xk/(1-x)k+1.

Consider now the recurrence relation:

As is well known, the sum is a triangular number, s_n = n(n + 1)/2. There is a very simple proof that was discovered by young Gauss to the astonishment of his teacher. Presently, I'll establish the formula with the help of generating functions.

First let's find the generating function of {s_n},

Multiply (7) by x^n-1 and sum up:

or

1. H. S. Wilf, Generatingfunctionology, Academic Press, 2^nd edition, 1994 (Also available free online.)

Generating Functions

1. A Property of the Powers of 2
2. An USAMTS problem with light switches
3. Euler's derivation of the binary representation
4. Examples with series of figurate numbers
5. Examples with finite sums with binomial coefficients
6. Fast Power Indices and Coin Change
7. Number of elements of various dimensions in a tesseract
8. Straight Tromino on a Chessboard
9. Ways To Count

Copyright © 1996-2008 Alexander Bogomolny