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.

Â