Generating Functions
1 Algebra and Infinity
2 Generating Functions
3 Recurrences
4 Regular Languages and Generating Functions
Finite versus Infinite
Finite state machines are a great example of a finite, algorithmically
attractive
representation of an infinite object (the acceptance language or, in case of
infinite words, even just a single accepted word).
Register machines and Turing machines also describe infinite objects, but
they
are much less amenable to manipulation by algorithms.
Are there any other compelling examples along the lines of finite state
machines? How about something more algebraic?
Classical Example: Making Change
Suppose we have an unlimited supply of coins of denominations
How many ways are there to make change for x ≥0?
Call this number C (x).
In other words, we want to count the number of solutions of the equation
The standard approach to computing C(x) is dynamic programming.
Counting
More precisely , in the bottom-up approach we compute a n × (x + 1) array
C(k, z) where 1≤k≤n and 0≤z≤x
with the intent that
C(k, z) = # of ways to make change for z using d1, . . . , dk
Then
where C(k, 0) = 1 and C(k, y) = 0 whenever y < 0 or k = 0.
So we can get C(z), z≤x, in
steps.
Example
The table for d = (2, 5, 10) and x = 18.
Computing a few more values produces the following plot. Ponder deeply.
C(x) for x≤100, d = (2, 5, 10).
Expanding Polynomials
Another way to get numerical answers is to multiply together polynomials
for d = d1, . . . , dn.
Claim
The coefficient of
is
C(s), for all s≤x.
This follows immediately from the definition of polynomial multiplication .
Notation
We write
for the coefficient of term zi in the polynomial p(z).
So
for all s≤x.
Going Infinite
The bound s≤x is annoying. It would be nice to be able
to deal with the
whole infinite sequence
We would like to set 
in
the definition of 
That’s actually OK, except that we are now dealing with a power series instead
of a polynomial.
Then
for all s≥0.
The Crucial Trick
So far, we have not really gained much: to compute the coefficients of the
product power series we have to multiply out polynomial of sufficiently high
degrees, just as before.
But note that
Instead of using infinitary power series we can use perfectly finitary
rational
functions!
Example (2,5,10)
Taylor Expansion
There is price we have to pay, though: given a rational function , it becomes
a
bit more difficult to extract the coefficients of the corresponding power
series.
For example, expansion about z = 0 produces
Evaluating the derivatives requires quite a bit of work.
Getting a nice closed form can be very hard.
Example
The rational function looks like
and C(s) has the form
where γ is this:
It is not even clear that this simplifies to a integer value (it does, for
all s≥0).
The best way to check is by machine.
Algebra and Infinity
2 Generating Functions
Recurrences
Regular Languages and Generating Functions
The Definition
Suppose we have a sequence
of numbers (naturals, integers, reals,
whatever).
Definition
The generating function of a is the power series
Note that z is just a variable and could be replaced by any other variable.
At first glance, A(z) may look slightly more complicated than a, so why bother?
Aside: The Calculus Angle
We will mostly ignore issues of convergence here, we are not really
interested in
evaluating the series A(z).
Still, note that for “reasonable”
and sufficiently small z we will
actually get a
function from, say, the reals to the reals.
Lemma
Let r > 0 such that
for all n > 0. Then A(z) converges for all z such
that |z| < 1/r .
One can use the machinery of analysis to determine properties of this
function
and, hopefully, get a better understanding of a.
In particular, one can use Taylor expansion to retrieve the
coefficients given
some suitable representation of the series, more later.
Algebra
The real goal is to the algebra of power series–rather than manipulating the
sequence directly, we manipulate the series. For example,
Manipulating Infinite Sequences
So we can perform certain operations on sequences:
• Add two sequences .
•Multiply a sequence by a scalar.
•Multiply a sequence by 1,2,3,. . .
•Shift a sequence to the right or left.
•Space out a sequence.
•Convolve two sequences.
Given a few basic sequences this allows us to construct a whole class of
sequences.
Standard Generating Functions
Roll Your Own
How do we concoct the generating function for
1, 1, 2, 2, 4, 4, 8, 8, . . .
No problem:
The Inevitable Urn Example
You have an urn containing 30 red, 40 blue and 50 white balls. How many
ways are there to extract 70 balls from the urn (order does not matter)?
Letting
we need to calculate [z70] p.
We could expand out the whole polynomial, but a better way is to rewrite the
geometric sums as
Urn
The denominator term 1/(1 − z)^3 can be expanded according to the binomial
theorem as
Since we are looking for z70 we only need the part
from the numerator , all other terms have higher degree. So the answer is
Sicherman Dice
A pair of standard dice produce the following relative frequencies for the 11
possible outcomes:
Weird Question: Can we get the same frequencies using non-standard
dice?
Let’s agree that the dice have 6 faces and the number of spots on each face is
positive.
A priori there are 12 variables to deal with, one for each face. Of course,
there
are constraints that simplify matters, but it’s still a bit tedious to try out
“random” spot assignments.
George Sicherman seems to be the first to have solved this problem
The High Road
We can describe an ordinary die as
So we would like to find positive exponents ai and bi such that
Better is to factor p:
Then the two new polynomials must factor as
where
Pinning Down the Coefficients
First note that we must have c1 = d1 = 1 since qi(0) = 0: each face must have
a positive number of spots.
We must have c2 = d2 = c3 = d3 = 1 since qi(1) = 6: there are six faces.
This leaves c4 and d4.
One possibility is, of course, c4 = d4 = 1 and we have
ordinary dice. The only
other possibility is, say, c4 = 0 and d4 = 2 producing two
dice
(1, 2, 2, 3, 3, 4) (1, 3, 4, 5, 6, 8)
That’s it, there are no other solutions.
Algebra and Infinity
Generating Functions
3 Recurrences
Regular Languages and Generating Functions
Recurrences
Generating functions suggest the following general approach towards solving
recurrences:
•Write the solution
•Apply the recurrence to the terms of the power series and massage things
into a nice closed form.
•Extract the terms of the sequence from the closed form of A(z), e.g., by
Taylor expansion.
Fibonacci
The recurrence here has the form
Hence we have the generating function
By applying the recurrence to the series we get
and therefore
Solution
Since F(z) is a simple rational function, we can determine the coefficients
of
the Taylor series easily using a partial fraction decomposition.
Here
Since
we have
Binary Trees
Let
be the number of (ordered) binary trees on n nodes (which is the
same as
the number of full binary trees on n + 1 leaves).
Brute force table:
Recurrence
The recurrence for binary trees takes the form
Let B(z) be the generating function and note that
Therefore
Taylor
Performing Taylor expansion is somewhat difficult in this case, though of
course
not a problem for a computer algebra system:
It turns out to be easier to use the Binomial Theorem to get a better
description.
and thus
Taylor
A simple calculation shows
Hence, bn = Cn, the nth Catalan number.
Algebra and Infinity
Generating Functions
Recurrences
4 Regular Languages and Generating Functions
Growth Functions
Recall a definition from a few weeks back:
Definition
Given a language
its growth function is defined by
For regular languages growth functions are particularly simple: they have
rational generating functions.
How does one compute
Full Transition Matrices
Suppose we have a DFA M on states [n] that accepts L. Define the full
transition matrix of M to be
where
A(i , j) = # transitions from i to j
Let
be the row unit vector with a 1 at the initial state.
Let
be the column vector with 1’s at the final states, 0’s elsewhere.
Claim
Note that this does not work for nondeterministic machines.
Example: Even/Even
The full matrix for the even/even DFA looks like so:
In this case it is easy to calculate Ak :
Hence
and for k > 0 we have
And Generating Functions?
It would seem natural to try to determine the generating function for
How about something like
Looks great, but A is a matrix, not a real; the fraction on the right hand
side
requires a bit of explanation (and might just be meaningless).
I is the identity matrix, I − Az is a matrix of linear polynomials in z. Such
a
matrix may well have an inverse, so we should interpret the fraction as a matrix
inverse.
Example: Even/Even
The inverse of (I − Az) for the even/even DFA looks like so:
Since q0 = 1 and F = {1} we only need the first term. Taylor expansion
produces
Works! But why?
An Explanation of Sorts
To do this real justice one has to take a closer look at the algebraic
structure of
all formal power series whose coefficients are n × n integer matrices (which is
often written
and has lots of interesting properties).
Less formally, we want to justify
Multiplying both side this simply means:
The last equation is easily verified; just multiply out the RHS.
Incidentally, in this formal power series structure there is a Kleene star:
,
the unique solution of X = AX + I .
General Case
Write
for the generating function counting the words that lead from q0 to
i . Let
be
the column vector of all these functions.
Then we need to solve the linear system
where e is the unit column vector indicating the initial state.
The generating function for
is then
Note that this type of computation can be handled easily on a computer
algebra system; it’s a bit unpleasant to do by hand.
Example: Subword Counter
Recall the problem of building a DFA for all words over {a, b} that contain
exactly three occurrences of the subword ab (subword, not factor).
The state complexity of this language is 7 and the matrix I − Az for the
minimal DFA has the form
1 is the initial state, 6 is a sink and 7 is final.
Solution
The generating function for
is
A little bit of pattern matching produces
Not exactly earth shattering, but very elegant.
Summary
•Generating functions are another example of a compact description of an
infinite object.
•Combinatorial operations on sequences correspond to algebraic operations
on the corresponding functions.
•Generating functions can be used to solve recurrence equations.
•There is a deep connection between rational generating functions and
regular languages; in particular growth functions of regular languages are
rational.
| Prev | Next |