# 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 d_{1}, . . . , d_{k}

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 = d_{1}, . . . , d_{n}.

**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 z^{i} 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 [z^{70}] 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 z^{70} 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 c_{1} = d_{1} = 1 since q_{i}(0) = 0: each face must have

a positive number of spots.

We must have c_{2} = d_{2} = c_{3} = d_{3} =
1 since q_{i}(1) = 6: there are six faces.

This leaves c_{4} and d_{4}.

One possibility is, of course, c_{4} = d_{4} = 1 and we have
ordinary dice. The only

other possibility is, say, c_{4} = 0 and d_{4} = 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, b_{n} = C_{n}, 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 A^{k} :

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 q_{0} = 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 q_{0} 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 |