0:00
Now let's finish up with a quick summary of the things that we've covered in this
lecture. the main topic has been the symbolic
method for labelled classes, and particularly the transfer theorem shows
how the constructions that we consider transfer to operations on generating
functions. So we consider the disjoint union
operation. And the main one, which is the labelled
product operation, where we, we relabel objects in all possible ways.
And we would get a product on the generating function, sequences of length
k, which we would generate in function a to the z to the k, sequence of any length
1 over 1 minus. Same with sets of length k or sets of any
size, and cycles of length k or cycles of any size.
And there's many others that people have defined, like the box product which has a
corresponding operation on the generating function.
with these basic operations and just a few examples, there's many, many other
examples in the book. we were able to define a whole host of
commonatorial classes. all with a relatively simple description
and then leading to Directly from the transfer theorem to exponential equations
that exponential generating functions have to satisfy.
And we have variations on these to lead to a, a huge variety of different common
notarial classes and still have a specific equation that the generating
functions have to satisfy. That fits with our overview to analyze
properties of a large combinatorial structures, we use the symbolic method to
get directly generating function equation.
now its, important to note that the equations that we get vary widely in
nature. Some of them are quite simple, some of
them are quite complicated. but those are the generating functions of
the counting sequences that we seek. so in the second part where we derive
asymptotics from generating functions, we're also going to need general tools
that can handle all of these different types, of generating functions.
2:28
But still, the derivations that give us the generating functions, were all,
really, essentially, quite simple. in fact to the point where again this
brings in also unlabeled classes. We we can automate the transfer from
specifications to generating functions. and in fact Philippe and, and his
students Bruno Salvy and Paul Zimmerman did so in the 90's.
in much of this work is reflected in modern symbol manipulation systems.
Another thing we can do is use specs to generate huge random structures.
one easy approach is to just take the spec and use a recursive program that is
based on the spec. and that's okay but it doesn't get you
really large structures because it takes quadratic time.
but there is a probabilistic method that gets for a given size, that gets a random
structure of, approximately, that size and works in linear time.
And this is, becomes, increasingly important, for checking, whether a
combinatorial model that someone might have of the real world, actually matches
with observed in the real world. Can generate, a large number of random
structures and check if they're properties correspond to the real world
thing, object that's being studied. whether it be a DNA sequence or a
computer network or whatever else you've found that people are studying nowadays.
so that's called Bolton sampling in that's reference for for that as well.
but I think again it's all about the utility of generating functions.
and really the bottom like is that Without something like the symbolic
method or generating functions. people were doing really horrendously
detailed and difficult calculations. and this approach really does eliminate
virtually all of them. That's the summary of the symbolic method
both for labelled and unlabelled methods.
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
