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.