Design and Analysis of Algorithms Neal Young

Computer Science 45

Notes on generating functions My intention here is to just give you a brief introduction to pique your interest and familiarize you with the ideas. Check out the reference by Vitter and Flajolet [3] for further and more comprehensive info on generating functions. Another reference for discrete math in general is the text Concrete Math [2]. I expect you could find Mathematica or Maple packages to play with on the net, one possible lead is [1].

Example - the symbolic method.

How many distinct n-node binary trees are there? The ordinary generating function for the set of binary trees is

displaymath172

where tex2html_wrap_inline174 is the number of binary trees of size n. In the function b, there is one term tex2html_wrap_inline180 of ``size'' n for each tree of size n. Postponing for a minute the question of what purpose this serves, can we find a simpler form for the function b? Here is a simple set of rules defining the binary trees:

  1. The tree consisting of a single node is a binary tree.
  2. If a tree T is a binary tree, then the tree formed by creating a new root r and making T the single subtree of r is a binary tree.
  3. If trees tex2html_wrap_inline196 and tex2html_wrap_inline198 are binary trees, then the tree formed by creating a new root r and making tex2html_wrap_inline196 and tex2html_wrap_inline198 the left and right subtrees of r is a binary tree.
From this set of rules we can see the following equivalence:

displaymath208

Here `` tex2html_wrap_inline210 '' represents a single node and `` tex2html_wrap_inline212 '' means there is a size-preserving bijection (a one-to-one and onto function f such that the size of x equals the size of f(x)) between the set on the left and the set on the right. Replacing each root `` tex2html_wrap_inline210 '' by a ``z'' (a term of ``size'' 1) and replacing the set union by addition yields the corresponding equivalence:

displaymath224

Solving for b(z) using the quadratic formula yields

displaymath228

From this closed form and a little algebra, we can see that b(z) is well-defined as long as tex2html_wrap_inline232 -- for larger values, the term inside the square root becomes negative. Amazingly, from this it follows directly (for reasons discussed below) that tex2html_wrap_inline174 grows roughly like tex2html_wrap_inline236 . With a little more work, an exact form for tex2html_wrap_inline174 can be obtained.

Example - recurrence relations.

The Fibonacci numbers are defined by the following recurrence:

displaymath240

The corresponding generating function is tex2html_wrap_inline242 Can we find a simple form for f(z)? Using the recurrence, we get

eqnarray37

Solving for f yields

displaymath248

From this we can see that f is well-defined as long as z is less than tex2html_wrap_inline254 -- the smallest root of tex2html_wrap_inline256 . From the general principle described below, it follows that tex2html_wrap_inline258 grows roughly like tex2html_wrap_inline260 .

Estimating the rate of growth from the smallest singularity.

In the above examples, we used the following rule of thumb:

principle49

We can summarize this by saying that the best exponential approximation to the rate of growth of tex2html_wrap_inline258 is tex2html_wrap_inline284 , where r is the smallest singularity of f(z), in other words, r is the largest value such that for all z<r, f(z) is well-defined.

Why is this the case? If f(a) is well-defined, then the infinite sum tex2html_wrap_inline298 converges. Its terms must tend to zero as n tends to infinity:

displaymath302

This establishes the first part of the principle: tex2html_wrap_inline304 .

On the other hand, let b and c be as in the second part of the principle: f(b) is not well-defined and b<c. Suppose for contradiction that tex2html_wrap_inline258 is tex2html_wrap_inline316 . Then tex2html_wrap_inline318 , so that

displaymath320

This contradicts our assumption that f(b) was not well-defined.

Symbolic derivations - general principles.

Here are a few general principles for deriving generating functions: Suppose sets A and B have generating functions a(z) and b(z), respectively.

(The rule for Cartesian products assumes that the ``size'' of an element tex2html_wrap_inline362 is the sum of the sizes of tex2html_wrap_inline364 and tex2html_wrap_inline366 . This was the case in the binary tree example. The subsequent rules have a similar assumption.)

Why are these principles true? Take the Cartesian product rule for example. For every element tex2html_wrap_inline368 and tex2html_wrap_inline370 , there is a term tex2html_wrap_inline372 in a(z) and a term tex2html_wrap_inline376 in b(z), where i and j are the sizes of tex2html_wrap_inline364 and tex2html_wrap_inline366 , respectively. In the product a(z)b(z), the pair tex2html_wrap_inline362 thus contributes a single term tex2html_wrap_inline392 of ``size'' equal to the size of the pair tex2html_wrap_inline362 . More formally, we can write

displaymath396

Since the number of pairs of size n in tex2html_wrap_inline340 is tex2html_wrap_inline402 , this proves the principle.

A canonical example.

How many k-digit decimal numbers are there whose digits sum to n? Let D be the set of digits tex2html_wrap_inline410 . For this problem, we think of each digit as having a size equal to itself. With this interpretation, the generating function for d(z) is tex2html_wrap_inline414 .

The set of k-digit numbers is then tex2html_wrap_inline418 . The generating function for tex2html_wrap_inline418 is tex2html_wrap_inline422 . Here the ``size'' we associate with a k-digit number is just the sum of the sizes of the digits.

The singularity principle says that the nth coefficient grows like tex2html_wrap_inline428 -- this time it's not so useful! On the other hand, note that for fixed k, this generating function has only finitely many terms, so we have to be a little more careful when asking questions about the asymptotics.

Arbitrary-degree rooted trees.

Let tex2html_wrap_inline432 be the number of distinct rooted trees of size n. We can define the set of rooted trees as follows:

  1. A single node is a rooted tree.
  2. If tex2html_wrap_inline436 is any finite sequence of rooted trees, then a new rooted tree can be formed by creating a new root node r and making the roots of the trees in the sequence the children of r.
In fact, the first rule is the special case of the second that occurs when k=0, so we can omit it. This gives the equivalence for the set T of rooted trees:

displaymath446

(Recall that tex2html_wrap_inline448 represents finite sequences of elements of T.) The generating function t(z) thus satisfies

displaymath454

Solving for t(z) using the quadratic formula yields

displaymath458

From the singularity principle, it follows that tex2html_wrap_inline432 grows roughly like tex2html_wrap_inline462 .

Exact answers.

The singularity principle is useful for getting rough estimates of the exponential rate of growth of the coefficients of a generating function. Even more can be said about a generating function from its singularities, however, the proper tool for this is complex analysis and we don't pursue it further here.gif

Instead we give a few simple examples where exact expressions can be obtained for the coefficients.

A few standard series.

Differentiation.

Suppose you have a simple form f(z) for the generating function tex2html_wrap_inline510 , and you want a simple form for tex2html_wrap_inline512 -- that is, you want to introduce a linear term. Note that tex2html_wrap_inline514 , so that the answer you want is just zf'(z). For instance, applying this to the generating function tex2html_wrap_inline518 gives tex2html_wrap_inline520 .

You can also use differentation to get the exact form for the coefficients. The general rule is

theorem96

Here tex2html_wrap_inline526 represents the kth derivative of f. To prove it, first use induction to show that tex2html_wrap_inline532 , then substitute k=n and z=0 (so all terms but the leading one drop out) to get tex2html_wrap_inline538 .

Repeated differentation can often be messy, but not always. For example,

theorem104

This holds for arbitrary m, not just integer values. To prove it, just note that differentiating tex2html_wrap_inline550 n times yields tex2html_wrap_inline554 and then apply the preceding theorem.

Substitution.

From tex2html_wrap_inline556 it follows by substituting 2z for z that tex2html_wrap_inline562 . Similarly by substituting tex2html_wrap_inline564 for z one obtains tex2html_wrap_inline568 .

Partial fractions.

Recall that the generating function for the Fibonacci numbers is

displaymath248

Factor the denominator and separate into partial fractions:

eqnarray121

Here 1/a and 1/b are the roots of tex2html_wrap_inline256 : tex2html_wrap_inline578 . Letting tex2html_wrap_inline580 denote the coefficient of tex2html_wrap_inline180 in f(z), we have

eqnarray132

References

1
J. S. Devitt. Combinatorial objects and their generating functions: A Maple class room environment. In Thomas Lee, editor, Mathematical Computation with Maple V: Ideas and Applications: Proceedings of the Maple Summer Workshop and Symposium, University of Michigan, Ann Arbor, June 28-30, 1993, pages 20-26, Boston, MA, USA, 1993. Birkhäuser.

2
Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Concrete Mathematics. Addison-Wesley, Reading, MA, USA, second edition, 1994.

3
Jeffrey Scott Vitter and Philippe Flajolet. Average-Case Analysis of Algorithms and Data Structures, chapter 9. Elsevier Science Publishers B.V., 1990. ISBN 0-444-88075-5.

About this document ...

This document was generated using the LaTeX2HTML translator Version 96.1 (Feb 5, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -no_navigation -split 0 gen-fns.

The translation was initiated by Neal Young on Fri Apr 18 09:47:38 EDT 1997

...here.
Some refinement is possible even without complex analysis. Here's a hint about pinning down the polynomial term.

Suppose that f(r) is well-defined but f(z) is not well-defined for z>r. Compare the sum tex2html_wrap_inline470 (which converges) to the sum tex2html_wrap_inline472 (which diverges). This will give you better upper bounds on tex2html_wrap_inline258 . Suppose further that f' (the derivative of f) is not well-defined at r. Compare the sum tex2html_wrap_inline482 (the derivative at r, which diverges) to tex2html_wrap_inline486 (which converges). This will give you better lower bounds.

If you are not so lucky that f(r) is well-defined and f'(r) isn't, then consider integrating or differentiating f several times so that the resulting function has the property you want. Recall that each differentation introduces a linear term in each coefficient, whereas integration factors one out.

 


Neal Young
Fri Apr 18 09:47:38 EDT 1997