Generating Functions
A generating function is a clothesline on which we hang up a sequence of numbers for display. Generatingfunctionology, |
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 {a_{n}}, where, by convention, the index n ranges from 0 to , is a formal series
(*)
f(x) = a_{0} + a_{1}x + a_{2}x^{2} + a_{3}x^{3} + ...
Two such series are equal iff they have exactly same sequence of coefficients. [x^{n}]f(x) is the usual notation for the coefficient a_{n} in f. Thus, two series f and g are equal iff
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:
(1 - x)(1 + x + x^{2} + x^{3} + ...) = 1,
so that we can state that
(1)
1/(1 - x) = 1 + x + x^{2} + x^{3} + ...
Mulitplicative Inverse Property
The series (*) has a multiplicative inverse iff a_{0}0.
Proof
Let's simply show how to constructively find the inverse f ^{-1} in the form
f ^{-1} = b_{0} + b_{1}x + b_{2}x^{2} + b_{3}x^{3} + ...
Such an inverse should satisfy
a_{0}b_{0} = 1
a_{0}b_{1} + a_{1}b_{0} = 0
a_{0}b_{2} + a_{1}b_{1} + a_{2}b_{0} = 0
...
From the first equation, b_{0} = 1/a_{0}. From the second equation,
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
As another example, the binomial theorem
(1 + x)^{n} = 1 + C(n,1)x + C(n,2)x^{2} + C(n,3)x^{3} + ... + C(n,n-1)x^{n-1} + x^{n}
says that the expression (1 + x)^{n} is the generating function of the sequence of the binomial coefficients
(2)
C(n,k) = C(n-1,k) + C(n-1,k-1).
What it takes is to equate [x^{k}](1 + x)^{n} with
(2')
(1 + x)^{n} = (1 + C(n-1,1)x + C(n-1,2)x^{2} + C(n,3)x^{3} + ... + C(n-1,n-1)x^{n-1})·(1 + x).
The representation of the function (1 + x)^{n} as a product of monomials
(1 + x)^{n} = (1 + x)·(1 + x)· ... ·(1 + x),
with n factors, gives an immediate interpretation of the coefficients
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 + x^{2} - x^{3} + ...
Then
1/(1 - x) + 1/(1 + x) = 2·(1 + x^{2} + x^{4} + ...)
such that the generating function of the series 1, 0, 1, 0, ... is given by
(3)
1/(1 - x^{2}) = 1 + x^{2} + x^{4} + ...
Note that (3) might have been obtained from (1) with the substitution of x^{2} 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 + c^{2}x^{2} + c^{3}x^{3} + ...,
so that 1/(1 - cx) is the generating function of the series
It's possible to go a step further and ask, What is the generating function of the sequence 1,
(5)
1 + (1 + x)y + (1 + x)^{2}y^{2} + (1 + x)^{3}y^{3} + ... = 1/(1 - (1 + x)y).
And further,
[x^{k}]1/(1 - (1 + x)y) | = 1/(1 - y)·[x^{k}]1/(1 - x·y/(1-y)) |
= 1/(1 - y)·(y/(1-y))^{k} | |
= y^{k}/(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}∑_{k}C(n,k)x^{k}y^{n},
from where [x^{k}]1/(1 - (1 + x)y) can also be found to be
[x^{k}]1/(1 - (1 + x)y) = ∑_{n}C(n,k)y^{n}
We thus obtain another useful formula:
∑_{n}C(n,k)y^{n} = y^{k}/(1-y)^{k+1}.
which of course could be rewritten in terms of x:
(6)
∑_{n}C(n,k)x^{n} = x^{k}/(1-x)^{k+1}.
Consider now the recurrence relation:
(7)
s_{n} = s_{n-1} + n, s_{0} = 0.
It's obvious that s_{n} is the sum of the first n natural numbers:
s_{n} = 1 + 2 + 3 + ... + n.
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}},
f(x) = s_{0} + s_{1}x + s_{2}x^{2} + s_{3}x^{3} + ...
Multiply (7) by x^{n-1} and sum up:
∑_{n}s_{n}x^{n-1} = ∑_{n}s_{n-1}x^{n-1} + ∑_{n}nx^{n-1},
or
(8)
f(x)/x = f(x) + ∑_{n}nx^{n-1}.
If we introduce g(x) = ∑_{n}nx^{n-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) = ∑_{n}nx^{n-1} = (∑_{n}x^{n})' = [1/(1 - x)]' = 1/(1 - x)^{2}.
In combination with (8), this gives
(9)
f(x) = x/(1 - x)^{3}.
Now, letting k = 2 in (6)
x/(1-x)^{3} = ∑_{n}C(n,2)x^{n-1},
which in part means that
References
- H. S. Wilf, Generatingfunctionology, Academic Press, 2^{nd} edition, 1994 (Also available free online.)
|Contact| |Front page| |Contents| |Algebra|
Copyright © 1996-2018 Alexander Bogomolny