0:04

Today we're going to talk an introduction to analytic combinatorics.

It might seem a bit strange in a course entitled Analytic Combinatorics to

not get to this topic until the middle of the course.

But as you'll see it builds upon all the things that we've talked about to

this point.

It gives us a coherent starting point from where we can go forward in

the analysis of algorithm and the analysis commentarial structures.

And I hope that by the end of this lecture you will have a pretty good idea of what

analytic combinatorics actually is.

0:37

I'll just start with a brief overview.

With the analytic combinatorics it's a calculus for

the quantitative study of large combinatorics structures.

In most of the work behind analytics combinatorics is set forth In

our book Analytic Combinatorics that will be the basis for part two of this course.

But it also plays an important role in the analysis of algorithms and

the tie between elementary combinatorics and

the kind of analysis that we need to really study computer programs.

So the basic features of analytic combinatorics is that

we begin with formal combinatorial constructions.

So that is we have a mathematical way to specify what it is that we're studying.

The generating function that we've talked about in the third lecture

is really the central object of study in the analytic combinatorics.

Number one, because we have transfer theorems that can immediately give us

generating function equations from the combinatorial constructions.

And number two, because we can take transfer theorems to give

us estimates of the values of things right from the generating function.

As I mentioned last time our asymptotics results are going to extend in principle

to any desired precision on the standard scale.

And most important is that it's a calculus that is we can handle

variations on fundamental constructions very easily.

In those kinds of variations help us cover a very broad variety

of problems for study.

So this is just a graphic depiction, we start with combinatorial constructions.

And we use a symbolic transfer theorem to get a generating function equation.

And that process is sometimes known as the Symbolic Method.

Then from the generating function equation, we use analysis and

we use analytic transfer theorem to get our coefficient asymptotics directly.

[COUGH] Essentially,

this process allows us to avoid a lot of the detailed calculations that we've

been doing in the analysis of algorithms and combinatorial structures.

For example, in analytic combinatorics if you want to know the number

of binary trees within nodes.

There's a combinatorial construction and we'll go through the details of this.

That immediately transfers to a generating function equation,

that immediately transfers to coefficient asymptotics for

the result, without going into all of the detail.

That's the overview.

We'll end the lecture with this slide too, and

you'll understand everything that goes behind the transfers.

So the beginning point is this symbolic method,

so we'll start by talking about the symbolic method.

3:38

Now, it's in approach number one, for defining common thorough constructions but

mainly for translating them to generating function equations.

And the way that we do that is define a class of combinatorial objects.

Define some notion of what the size of an object is.

Then define a generating function whose coefficient

count objects of the same size.

Now that's what we've been doing in generating function counting

in several examples already.

4:18

And then from those operations, we're going to have translations for

each operation that defines a construction to an operational generating function.

And this is just the kind of notation that we use.

Upper case letter for combinatorial objects.

Some notation, like absolute value for size.

And then generating function we'll add the same letter as the class,

except it'll be a function of a variable, usually z.

And then the operations actually will involve familiar symbols.

4:54

So now we have to get started somewhere, so there's a very formal basis

that after these definitions we'll do examples and you'll see the need for this.

But it's a good thing to talk about them right at the beginning so

what is a combinatorial class?

It's just a set of objects, and a size function.

Now, we have to have something to begin with, and we call those atoms.

Those are objects of size one.

We also, for convenience, have a atom of size zero.

Which is a neutral object, and that's useful for

describing, you will see that is useful for recursive definitions.

So a combinatorial construction uses the union, product and

sequence operations that I will talk about in a minute to define a class.

In terms of atoms in other classes.

And we start with the very based building blocks over in the right where

the notation capital Z is in a contains a single atom.

Then there's notation capital E which is a neutral class

that contains an atom of size zero and then there's also an empty class.

And again, it's not worthwhile to spend time on these definitions right now but

to refer back to them when we use them later on if necessary.

So here's a very simple example of a combinatorial class with natural numbers.

So the definition of a natural number is a set of atoms or

since you can't tell the difference between atoms, that's what we mean by

unlabeled and we're getting to that detail and more, much more detail later.

It's a set or sequence, it's the same thing.

So, there's only one object of each size.

7:04

So that's a simple example of a common notarial class.

And actually it seems trivial when the base the early ones do seem trivial it's

when you put them together that you get interesting useful mathematical results.

So for example, this kind of notorial

class is a basis of study of things like partitions of natural numbers,

how many ways can you break them up into sum and compositions and so forth?

We don't get into that too much.

Show in part one but we will in part two.

7:38

Here's something that we study all the time in Computer Science.

A bit string.

A bit string is a sequence of zero or one bits and that's very familiar.

Just defining this familiar class had to get used to our notation and conventions.

So, how many bit strings are there of length n?

Well, there's two to the n.

So what's the OGF?

It's 2 to the n, z to the n, which is 2z to the n, or 1 over 1- 2z.

So that's another example of a combinatorial class.

Here's one, a familiar one, recast in terms of analytic combinatorics.

So a binary tree is empty or

it's a node in two binary trees, that's better in sequence, the order matters.

8:42

That was a subject of quite a bit of lecture three.

And its got the this OGF and that derivation is all given in lecture three.

So those are three examples of combinatorial classes, and

now I want to show constructions and how we build those things.

So for unlabeled classes, and again,

I'll talk about the distinction with labeled in a minute.

We're just going to use three different constructions.

If A and B are combinatorial classes of unlabeled objects then we have the disk

joint union, a Cartesian product in the sequence operations.

On here is the meaning of each one of those.

A + B is just copies of objects from A and B.

You take one from A, and one from B.

And that's the disjoint union.

Cartesian product is ordered pairs of copies of objects, one from A and

one from B.

And sequence is sequences of objects from A.

So, those are the constructions, and

these are just examples of how a construction might work.

So for bit strings, maybe you could use the usual distributive law.

So (00 + 01) is got copies of 00 and 01.

Same on the right, and if we do the Cartesian product of those,

we have to take each possibility on the left and

sequence with each possibility on the right.

So, there’s six possibilities there.

So that's an example of a use of the Cartesian product and

disjoint union operations.

So, here’s one just with unary numbers,

so an atom Cartesian product with

a sequence of atoms gives that list.

And there is binary trees.

11:04

But unlabeled, again, we'll talk about later what we mean by that.

But what's most important is the idea of a transfer theorem.

And this is the first basis of the symbolic method.

The idea is, while we're constructing the classes,

we're also developing equations for their generating functions, because, for

every operation, we have a corresponding operation on the generating function.

And for simple unlabeled classes they're quite simple.

So for example, for disjoint union.

If we take disjoint copies of objects from A and B and we form the disjoint union,

the OGF for that class is the sum of the OGFs of

the two classes that were operands.

For Cartesian product it's the product.

All right, we'll do a proof of this in just a second.

And for sequence, it's 1 over 1 minus.

So whatever construction we make,

we can translate that to an operation on the generating function.

So, anything that we can construct we have a generating function for.

12:13

And these are the proofs, and

these are very straight forward from the kind of generating function

counting arguments that we did when we talked about generating functions.

If gamma belongs to A + B, then they're disjoint copies.

So some of them belong to A, some of them belong to B.

You split the sum in those two ways and you have A(z) + B(z).

For cross product, that's a convolution, again,

they break up into independently, into the ones from A and the ones from B.

The size, since you've taken one from each,

the size of gamma is the size of the alpha 1 plus the size of the beta 1.

And those are independent so that's the product.

13:02

In sequence follows from the idea that sequence is like a product of 2,

product of 3, product of 4,

it's just the geometric series gives the proof of the sequence.

So that's the transfer theorems and that's the proofs.

And from this point forward, with the symbolic method,

we don't have to worry about sums involving convolutions anymore.

Whereas, we can get so our practice of doing convolutions and so forth.

But with this, we can do multiple convolutions and

we don't have to worry about carrying around those details.

We know what the generating function is going to be.

So let's just look at how it applies for binary trees.

15:26

And this is just using the union and Cartesian product rules.

You can read it in English or you can read it in math.

It says a binary tree is an external node, or

it's a tree connected to an internal node, connected to a tree.

And that's what we mean by a binary tree, this just makes it rigorous,

so that's the construction.

So that's a description of a class of all binary trees, a recursive description but

it's a description of a class of all binary trees.

And now what's significant is, we can use the transfer theorem to immediately

translate to the generating function equation.

Z sub box in the generating function is 1.

Generating function for Z sub dot is Z.

Generating function for the two Ts is T(z).

Any Cartesian product of those,

it translates to the product of the generating functions.

So no sums involved there.

We don't have to do sums anymore to get generating function equations of

this nature.

16:33

Now the next step is to extract coefficients.

We're going to talk about that a little later,

I'll just remark that this is something that we studied already.

Then finally get out to the answer that the coefficient of Z to the n and

that function is [COUGH] asymptotic to 4 to the n / square root of pi N cubed.

But for now, when talking about the symbolic method,

we're going to consider how do we get those generating function equations.

That's the first part of analytic combinatorics, the symbolic method.

And we'll look at lots of examples of that.

And then later, we'll talk about how do we get the coefficients out.

17:17

So that's our binary tree analysis, recast in terms of the symbolic method.

All of the calculations that we did before are in there,

but it's a much, much, much more general setting, and

we'll see how important that is as the course goes on.

Just as a similar example,

what about if we want to count binary trees by external nodes?

So that's a different combinatorial class because it's got a different size

function, and we denote that with box of t.

And the atoms are a little bit different because we consider external nodes

to be size 1 and internal nodes to be a size 0.

And the generating functions are different.

So, it's the same construction, but the atoms are different, so

we get a different generating function equation.

It's a really similar generating function equation, actually T box (z) is Zt(z).

If you plug in Zt(z) in that equation and divide by Z,

you get the same equation as before.

Well, this is a proof that the number of binary trees within

external nodes is the same as the number of binary trees within -1 internal nodes.

There's easier proofs of that, but

this is showing the consistency of the analysis and the ease

of developing a commonatorial construction to get a generating function equation.

19:19

For binary strings, we have two atoms, either 0 bits or 1 bits, we'll call

them Z0 and Z1, they both have size 1, and they both have generating function Z.

So how many binary strings within bits, well,

a binary string is a sequence of 0 and 1 bits.

That's what that says.

That's the definition of binary strings.

And now we go to the transfer theorem, Z0 + Z1 is 2z,

sequence of 2z, 1/1-.

A binary string is a sequence of 0 and 1 bits.

And the transfer immediately gives us B(z) = 1 / 1- 2z.

And that checks the coefficient of Z to the N of B(z) is 2 to the N,

as we expected.

Very simple and elementary, as we'll see in just a minute, this translates to

a more interesting and much more difficult to solve problems.

20:50

So again, very simple constructions, immediate transfer to GF equations.

And then it's just going to be a matter of extracting coefficients.

[COUGH] So here's now first example

of a problem that might be more difficult to solve.

And it's representative of very general treatment that we'll do in Chapter 8.

How many N-bit minor strings have no two consecutive 0s?

Actually, there's lots of practical applications,

where such questions are quite important for looking for lots of consecutive 0s,

some types of communications devices have problems in such situations,

and you'd have codes that don't do that.

And so these things are well studied.

And this is a simple example, but it gets to be a much more complicated very soon.

That's what we'll talk about in Chapter 8.

But still, let's take a look at solving this with the symbolic method.

Okay, so it's the same, it's binary string, so it's the same set-up.

Our class is the class of binary strings that don't have any 00.

We have the same set-up for generating function, and the atoms are all the same.

So what does the construction look like?

Well, a binary string with no 00 is either empty or at 0,

or it's 1 or 01, followed by a binary string with no 00.

You can check if that's a way to describe the class.

You have to think about it a little bit, but it's not too bad.

And what's important, though, is that we don't have just in English language

description, we have a combinatorial construction.

Combinatorial construction immediately translates to a generating

function equation.

See 0 cross Z1 is Z squared, Z1, our generating function is Z.

At + Z0, generating function is 1+z.

So put all that together, now we have a generating function equation for

B00(z) that we can solve, and that's 1+z / 1-z- z squared.

And again [COUGH] extracting coefficients,

now these are problems that we know how to solve.

In this case, it turns out, and we'll look at the details later,

in this case, it turns out to be Fibonacci numbers.

1 / 1-z-z squared is Fn.

Z is F / 1-z-z squared is Fn+1.

If you add Fn to n+1, you get Fn+2, and that checks with the anti-Fibonacci

number, checks with the numbers that we found on the previous slide.

Many of you probably noticed that it was Fibonacci numbers at that point.

And it's clear that this argument, and this process is going to extend easily for

binary strings with other kinds of restrictions.

The trick is coming up with a construction that precisely describes your class, but

often, that's not difficult.

And again, we'll look at a general treatment of this later on in the course.

24:32

We need to specify what the class is, we need to specify what the size function

is and the atoms, and write down the generating function.

Then we'll do a construction that mirror some English language description usually,

and that will immediately translate to an OGF equation.

And then the last step is to extract the coefficients, and

we'll talk about that at the end, so lots of examples to follow.

But before considering some more, I want to talk about labelled objects.

But that's an introduction to symbolic method.