Generating Functions

A generating function is a clothesline on which we hang up a sequence of numbers for display.

Generatingfunctionology,
H. S. Wilf
Academic Press, 1994, p. 1

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.

By definition, the (ordinary) generating function of the sequence {an}, where, by convention, the index n ranges from 0 to , is a formal series

(*) f(x) = a0 + a1x + a2x2 + a3x3 + ...

Two such series are equal iff they have exactly same sequence of coefficients. [xn]f(x) is the usual notation for the coefficient an in f. Thus, two series f and g are equal iff [xn]f = [xn]g, for all n = 0, 1, 2, ...

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 a0 is not 0. For example,

  (1 - x)(1 + x + x2 + x3 + ...) = 1,

so that we can state that

(1) 1/(1 - x) = 1 + x + x2 + x3 + ...

Mulitplicative Inverse Property

The series (*) has a multiplicative inverse iff a00.

Proof

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

  f -1 = b0 + b1x + b2x2 + b3x3 + ...

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

  a0b0 = 1
a0b1 + a1b0 = 0
a0b2 + a1b1 + a2b0 = 0
...

From the first equation, b0 = 1/a0. From the second equation, b1 = -a1b0/a0. From the second equation, b2 = -(a1b1 + a2b0)/a0, and so on. In this manner indeed, since a00, 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

  (1 + x)n = 1 + C(n,1)x + C(n,2)x2 + C(n,3)x3 + ... + C(n,n-1)xn-1 + xn

says that the expression (1 + x)n 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:

(2) C(n,k) = C(n-1,k) + C(n-1,k-1).

What it takes is to equate [xk](1 + x)n with [xk](1 + x)n-1·(1 + x), or more explicitly, the coefficients of xk on both sides of the identity

(2') (1 + x)n = (1 + C(n-1,1)x + C(n-1,2)x2 + C(n,3)x3 + ... + C(n-1,n-1))·(1 + x).

The representation of the function (1 + x)n as a product of monomials (1 + x)

  (1 + x)n = (1 + x)·(1 + x)· ... ·(1 + x),

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

  1/(1 + x) = 1 - x + x2 - x3 + ...

Then

  1/(1 - x) + 1/(1 + x) = 2·(1 + x2 + x4 + ...)

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

(3) 1/(1 - x2) = 1 + x2 + x4 + ...

Note that (3) might have been obtained from (1) with the substitution of x2 for x. Perversely, it can be shown that the substitution, although deemed illegal at the outset, leads to correct identities as long as the result includes either finite or formal quantities. With a substitution, we for example get without much ado
(4) 1/(1 - cx) = 1 + cx + c2x2 + c3x3 + ...,

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

It's possible to go a step further and ask, What is the generating function of the sequence 1, (1 + x), (1 + x)2, (1 + x)3, ... ? 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)i according to the binomial theorem

  1/(1 - (1 + x)y) = ∑n∑kC(n,k)xkyn,

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

 
[xk]1/(1 - (1 + x)y) = ∑nC(n,k)yn

We thus obtain another useful formula:

  ∑nC(n,k)yn = yk/(1-y)k+1.

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:
(7) sn = sn-1 + n, s0 = 0.

It's obvious that sn is the sum of the first n natural numbers:

  sn = 1 + 2 + 3 + ... + n.

As is well known, the sum is a triangular number, sn = 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 {sn},

  f(x) = s0 + s1x + s2x2 + s3x3 + ...

Multiply (7) by xn-1 and sum up:

  ∑nsnxn-1 = ∑nsn-1xn-1 + ∑nnxn-1,

or

(8) f(x)/x = f(x) + ∑nnxn-1.

If we introduce g(x) = ∑nnxn-1 and assume that taking derivative is a legitimate operation (which it is) in the ring of formal series, we may proceed as follows

  g(x) = ∑nnxn-1 = (∑nxn)' = [1/(1 - x)]' = 1/(1 - x)2.

In combination with (8), this gives f(x)·(1 - x)/x = 1/(1 - x)2, from where

(9) f(x) = x/(1 - x)3.

Now, letting k = 2 in (6)

  x/(1-x)3 = ∑nC(n,2)xn-1,

which in part means that [xn]x/(1-x)3 = C(n+1,2) = (n+1)n/2. Exactly the same result as above.

References

  1. H. S. Wilf, Generatingfunctionology, Academic Press, 2nd 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

|Contact| |Front page| |Contents| |Geometry| |Store|

Copyright © 1996-2010 Alexander Bogomolny

 37225096

Search:
Keywords:

Google
Web CTK