so today we're going to talk just about the symbolic method and for the next

couple of lectures. and again, there's some easier examples

that moves a bit slower in part 1 and in analysis of algorithms in the purple

book, Analytic Combinatorics, has a very rigorous treatment.

this lecture is somewhat in between, it's an overview that assumes some familiarity

with generating functions and basic mathematics; like, like it's covered in

part 1 of this course. If you move, find that we're moving a bit

quickly refer back to Analysis of Algorithms book.

[COUGH] . If you find that we're moving a bit

slowly read chapters one, two, and three of Analytic Combinatorics.

And then within a lecture or two we'll all be moving at the same pace, I think.

So basic definitions. A combinatorial class is a set of

combinatorial objects and an associated size function.

That's our starting point that's our object of study.

in the, today what were going to talk about is a, as a primary object of study,

the ordinary generating function associated with the class.

And that's a formal power series, where you have a variable c and use some for

all objects in the class z the to size of that object, that's the ordinary

generating function. So the size function is like an absolute

value just says that's like the size of the object.

[COUGH]. And then the class name, the class name

is usually a capital letter with the same letter as the generating function.

and then the object name is usually a lower case letter of the same letter.

[COUGH]. Now there's a very elementer elementary

identity that's fundamental to all the manipulations of the symbolic method.

And that is, this generating function where we look at all the objects, raise z

to the size of the object. that's equal to summing for all n the

number objects of size n times z to the end.

because if there's A sub N objects size N, then there's A sub N terms on that

left hand side one for each object of size N and collect them together you get

A sub N Z to the N. And that's a fundamental identity that

we're going to work with. And our goal is to find good estimates of

this value A sub N. And we refer to that as with the notation

square brackets Z to the N, that means the coefficient of Z to the N in A of z,

that's A sub N. and again I mention the conventions,

usually we try to use a roman letter for the class name.

for the generating function name, it's the same letter with an argument.

Uh,[COUGH] for in the book we use a slightly different font.

object variable is just lower case of the same letter and then the coefficient is

subscripted of the same letter. Uh,[COUGH] and size we usually use

capital N or little N and this kind of adopts a fantasy that we have a different

letter for each class but actually there's only 26 letters.

And we look at way way more classes, so sometimes we have a conflicts in these

names. but we do the best we can.

Now so with the symbolic method, what we can do is specify the class and at the

same time characterize the generating function.

that's the process that we want to talk about today.

Uh,[COUGH] so there's a number of basic combinatorial objects that are

characterized well by ordinary generating functions and they're called unlabeled

classes, and we'll talk about that distinction later.

so integers or strings which are sequences of characters, recursive

structures, trees, languages. and then compositions and partitions

which are compositions are positive integers sum to add, and partitions are

unordered compositions and we'll look at all of those soon.