Next, we're going to talk about another 
important class of combinatorial classes 
that has to do with labelled objects. 
And now let's, let's explain the 
distinction between the labelled and the 
unlabeled ones that we talked about and 
then look at some interesting problems. 
so labeled combinatorial classes the 
objects have an atoms, but we consider 
the atoms to be all different. 
and so just to make that clear, we label 
them, consider them to always be labeled 
with the integers 1 through n. 
so for just [COUGH] schematically, for 
unlabeled objects you can consider those 
two objects to be different. They, they 
have a different structure. 
but when they're labeled there, [COUGH] 
there's different ways to label them that 
make different objects. 
For example, that's two different ways to 
label that square 
that. 
[COUGH] So, in the one on the left 1's 
connected to the 2 and 4. The one on the 
right, 1's connected to 3 and 4. 
They're different. 
in this one, it's, it's not always clear 
how many different ways there are to 
label things. 
in the one on the right, then there's 
three different ways to label that. 
Either one, two or, three, 
there's actually four ways. 
1, 2, 3, or 4 are going to be the ones 
that's connected to everybody else. 
so there's a big difference in 
studying the number of different objects, 
because labels provide so many more 
possibilities. 
in fact, when we're working with labeled 
objects, we use exponential generating 
functions for that reason and that'll 
become clear as we move along. 
All right. 
So lets look at some basic simple 
examples again of labelled objects. 
so that's what we call an urn and so an 
urn is a set of labelled atoms. 
So it's set, the orders don't make any 
difference, so again, there is only one 
of each kind. 
We could use this definition of unary 
numbers and later on, you'll see why we 
use this characterization of it, it'll be 
very clear. 
so there's only one of each kind, but now 
we're going to use exponential generating 
functions. 
So the exponential generating function 
for urns is e^z. 
That's one of each kind, Z to the N over 
N factorial summed is e to the z. 
So that's a first basic example. 
next one is a familiar one. 
It's permutations. 
A permutation is a sequence of labeled 
atoms. 
Sequence means the order is significant, 
atoms are labeled, so every possible 
ordering of the atoms is going to give a 
different object. 
So there's two different objects of size 
2, either 1, 2 or 2, 1. Six different 
objects of size 3, 24 different objects 
of size 4, and so forth. 
so what's the exponential generating 
function for permutations? 
Well, there's N factorial permutations of 
size N. 
and so, the exponential generating 
function is that divided by n factorial 
times z to the n, 
which just leaves us with sum of z to the 
n or 1 / 1-z. 
That's another basic common combinatorial 
class. 
[COUGH] the N factorial serves to stop 
the generating function from blowing up 
too much because of all the different 
possibilities induced by the orderings. 
here's another one, 
a cycle. 
A cycle is a cyclic sequence of labeled 
atoms. 
so that's everything is connected in a 
circle but now there's fewer of each type 
that's and in fact, actually if you study 
it for a minute if you just fix on the 
largest to smallest element, then you can 
see that the others are permutation, so 
actually the counting sequence is N - 1 
factorial. 
so what's the exponential generating 
function for cycles? 
well, it's the sum of N - 1 factorial C 
to the N factorial, which everything 
cancels but an N, so it's natural log of 
1 / 1 - z since another basic 
combinatorial class. 
Now, it's a varied characteristic of 
analytic combinatorics to start with 
extremely simple derivations in classes 
like this. 
but then combine them in the interesting 
ways to provide answers to analytic 
problems of interest. 
so what about the analog to the Cartesian 
product operation? 
Well, it's it's much more complicated for 
labelled classes. 
when we take the product of two classes, 
so say, this first example. One we, we 
call it the star product. 
One star product of 1, 2, 3. 
what we're going to get is object of size 
4, 
but they have to be numbered from 1 to 4. 
And 
what the combinatorics requires is that 
we do that numbering 1 to 4 but we do it 
in all consistent ways. 
So, in this case, the second argument is 
a sequence that's in increasing order. 
So when we renumber, we have to put that 
in increasing order on each one of the 
possibilities. 
So we can assign 1 2, 3, and 4 to the 
first one and then the remaining labels, 
we assigned to the remaining three atoms 
but they have to be in increasing order. 
and here's a more com, complicated 
example where we take the star product of 
a 2-cycle and a 3-cycle. 
Again, when we do that we get five. 
we have objects consist of five atoms 
that have the structure set of 2-cycle 
and a 3-cycle. 
The atoms have to all be numbered with 1 
through 5 and we have to do it in all 
possible ways. 
So in this case there is you can choose 
any label, there is only one way to label 
the 2-cycle. 
and you can choose five choose two or ten 
different ways to label the two cycle. 
so first row, first column is with the 
top one being 1, you can have 2, 3, 4, 5, 
to the bottom one. 
second column, the top one being 2, 3, 
and 4. 
Then, after you've labeled the two cycle, 
then you take the remaining labels and 
assign them to the 3-cycle, but you have 
to be consistent and maintain the order. 
So for example with 3, 4, in this case 
with 3, 4 is labeled 2-cycle the 
remaining labels are 1, 2, and 5 and they 
have to go in that order. 
So that's the star product operation 
relabeled in all consistent ways. 
and when we get to applications we'll see 
why that's not just intuitive that's 
fundamental to working with labeled 
objects. 
so we'with labelled objects, since you 
can tell the difference in the ordering 
we have more basic constructions and it's 
a much richer set of operations that we 
are going to work with. 
And actually the ones that I'm giving 
both for labelled and unlabelled are only 
the beginning. 
research is ongoing and people have 
developed many, many more constructions 
that I'm going to present here. 
so [COUGH] we talked about, so, plus is 
the same. 
You take copies of objects from A and B, 
but you relabel in all consistent ways. 
star product is where you take ordered 
pairs of copies. 
sequence is similar to what we did for 
unlabeled. 
it's A + A star A + A star star A, and so 
forth. but you could have sets of objects 
like we did for urns and you can have 
objects arrange in a cyclic sequence for 
example. 
so those are the constructions that we 
can use richer set of constructions and 
leads to much richer set of objects to 
talk about. 
and again, what's important is that we 
have a transfer theorem. 
If we have combinatorial classes and we 
know they're EGFs, 
then the whatever operations we pick from 
that list, we're going to know the EGF or 
the result of that operation. 
As before, if we do disjoint union, we 
have the sum. 
if we do the labeled star product we have 
the product to the generating functions. 
if we do a sequence of k objects, it's 
like A(z)^k. 
a sequence of any number of objects is 
summing those is 1 over 1-. 
If we have a set, it's A(z)^k over k 
factorial and so that's a set of size k. 
And a set of any size, is sum of those is 
e^A(z). 
cycle is A(z)^k over k and cycles of any 
length. 
Cycles of size k is, that cycles of any 
length is log of 1 over 1 - A(z). 
So, so if we know the generating function 
for combinatorial class, when we perform 
one of these operations, we know the 
generating function for the result and 
that's extremely powerful 
transfer theorem that's a basis for the 
symbolic method. 
So let's just look at the basic 
constructions of the basic objects using 
these operations. 
So urns urn is a set of atoms and that 
immediately translates to e^z from the 
transfer theorem, for sets. 
and as we saw that, that gives a comic 
sequence Un = 1. 
cycles a cycle is this, a cycle of atoms 
and again, immediately from the transfer 
theorem, that tells us that the 
generative function is log 1 / 1 - z and 
therefore, the comic sequence is n 
factorial times coefficieny to the n in 
that, which is n - 1 factorial. 
permutations as with bit strength is two 
different ways to define permutations. 
You can say, a permutation is a sequence 
of atoms and then read immediately from 
the transfer theorem, that the generative 
functions for permutations has to be one 
of 1 - z or you can say, a permutation is 
either empty or the store product of an 
atom in a permutation. 
and that will generate all possible 
permutations. 
That immediately translates to P(z) = 1 + 
z * P(z). 
and then solving for P(z) gives the same 
result. 
and the, and then the kind of sequence is 
N factorial times the coefficient Z to 
the N in that, which is just N factorial. 
So those are just the starting point for 
some basic constructions. 
the proofs of the transfer theorems, 
again, they come just immediately from 
the definitions and from generating 
function, counting, the way that we 
talked about earlier. 
so A+ again, they separate into the 
disjoint sets and that immediately gives 
the result. 
for star, it's a convolution of, of the 
type that we've seen before but let's 
take a look. 
so to do all different relabellings, so 
we take one alpha from A and beta from B, 
and to do all different relabellings it's 
alpha plus beta choose alpha just like 
with the example I did with the cycles. 
and then [COUGH] so that's a number of 
ways you can relabel. 
and then the size of [COUGH] the, an 
object composed of an alpha and a beta is 
Z to the alpha plus beta. 
And again, the factorials for alpha plus 
beta factorial. 
and then if you take that complicated sum 
the alpha plus beta factorials cancel. 
and you can seperate out Z to the alpha 
or alpha vectorial Z to beta over beta 
factorial to get that it's a product. 
Again, that's a complicated convolution, 
but this is the only time we have to do 
it. 
and for the other operations I have a 
slide that's gotten lots of dense math on 
it, 
but its pretty simple. 
so as we saw before A(z)^k is the number 
of k-sequences as a generating function 
for exponential generating function for 
the number of k-sequences of size N so 
and then, that's just as we saw several 
times before. 
and if you add those all up for a 
sequence of any length you get 1 / 1 - z. 
But if you have all the k-sequences of 
size N, then you're going to have each 
k-cycle of size N appear k times there in 
each cyclic orientation. 
So that means that A(z) over, to the k 
over k is the EGF for k-cycles for cycles 
with k objects. And then summing all 
those up gives the result for cycles of 
any length. 
Similarly, if you have all k-sequences of 
size N, you're going to have all sets up 
here, k factorial times. 
So that means that A(z) to the k over k 
factorial is the exponential generating 
function for the number of k sets of size 
N and then summing all those up give the 
result that for any set, it's E to the A 
of Z. 
so these are worthy of study, but they're 
very straightforward and immediate from 
the definitions and the basic ideas of 
generating function counting. 
so let's look at much more interesting 
example. 
So the idea is that we have these 
operations, we can combine them in 
various interesting ways. 
And actually, as we'll see in part 2 
there's every way of combining these 
basic operations leads to a combinatorial 
class that people have studied in detail. 
and, but there's many more operations we 
can throw in as well. 
So let's look at, 
this is a famous one. 
How many different sets of cycles are 
there of labeled atoms? 
For example, for [COUGH] three atoms, 
you could have a cycle of size 3 and 
there's two different ways to label that, 
or you could have one cycle of size 1 and 
another cycle of size 2 and there's three 
possibilities for labeling that, 
or you could have three cycles of size 1. 
So it's a total of six sets of cycles of 
labeled atoms. 
and if you work it out for four, 
on the right is all the possibilities of 
sets of cycles of four atoms. 
You can have them be four singles and 
cycles or you could have 1-cycle of size 
4 and there's six different ways to label 
that one or you could have something in 
between all the possibilities are laid 
out here. 
you might recognize the numbers and yes, 
there's N factorial sets of cycles of N 
labelled atoms. 
And what we'll look at next is how we 
learn that from analytic combinatorics. 
And it's not just instructive, it forms 
the basis for us to solve problems that 
we couldn't otherwise solve as you'll 
see. 
So let's use are, regular methodology, we 
have to articulate what our class is. So 
it's P star, is the class of all sets of 
cycles of atoms the number of atoms is 
the size, the EGF, as usual brings 
together this coefficient is even over N 
factorial, is the number of sets of 
cycles of i and atoms the atoms are just 
labeled atoms for label classes, it's 
always the same. 
[COUGH] What's our construction? 
A, nothing more than saying a set of 
cycles of atoms is a set of cycles of 
atoms. that's what, that's what the math 
says, and it immediately translates from 
the transfer theorems to cycle of z 
translates to natural log 1 over 1 - z. 
Set of something is E to that power and 
that's just 1 over 1 - z. 
so therefore the counting sequence is N 
factorial is N factorial, that's the same 
as for permutations. 
and again, that's a very quick result, it 
just comes from the combinatorial 
description a set of cycles that we can 
get the generating function for sets of 
cycles immediately from the transfer 
theorem. 
Now, this is a well-known combinatorial 
bijection. 
a permutation is a set of cycles. 
And to see that, you'd start anywhere. 
Say we'll start at four so here, we have 
the permutation and then we have the 
index of the sequence. 
Where is it in the sequence? 
So if we start at the fourth thing in the 
sequence or the fourth enter in the 
permutation, it says 10 so we go to 10. 
and ten says [COUGH] that tenth entry in 
the sequence is 6 so we go to 6. 
and the sixth entry in the sequence is 
15, so we go to 15. 
and the point is as you see from this 
example, eventually, you're going to get 
back to where you started that's a cycle. 
we can depict that thing just like this. 
just when you go from 4 to 10 to 6 to 15 
back to 4. 
and if you do that if you've already done 
it, if you've already done an item and 
ignore it otherwise, do this process. 
You can convert any permutation into a 
set of cycles and it's a worthwhile 
exercise to figure out how to reconstruct 
a permutation from a set of cycles, 
but that's a well-known bijection. 
So that brings us to our first actual 
problem that you might not know the 
answer to or you might, because it's a 
classical problem but we'll get to one 
you don't know the answer to. 
and that's the derangements problem and 
this is a famous problem from the 
the eighteenth century and usually well, 
at that time, it was cast in this way. 
So, you have in people, who go to the 
opera, and they leave their hat on a 
shelf in the cloak room, but they all 
look the same. 
and so when they leave, they each grab a 
hat at random. 
And the question is, what's the 
probability that nobody gets their own 
hat? 
so 
[COUGH] in, in, in terms of combinatorics 
we refer to this as a derangement. 
Nobody gets their own hat, that means 
there's no singleton cycle. 
so that means that, that getting, getting 
your own hat means if you're in position 
four it's the, fourth item. 
[COUGH] so, and that's a singleton cycle. 
so the question is what's the probability 
that, that a permutation is a derangement 
or how many derangements are there? 
now just as an amusing aside this problem 
has been posed in the centuries since in 
many different ways. 
that's the classical opera way. 
so some people say, well, a professor 
returns exams to students and by passing 
them out at random. 
What's the probability that nobody gets 
their own exam? 
so lot's of people use that way of posing 
a problem in combinatorics classes or a 
more fun way to do it is the drunken 
sailor. so you have a group of sailors 
that are a bit inebriated and whenever, 
when they get back home, they wind up 
sleeping in a random cabin. 
So what's the probability that nobody 
winds up in their own cabin or maybe more 
relevant to college students is got an n 
students that live in a single room and 
they get in a state of inebriation. 
what's the probability that nobody ends 
up in their own room? 
that's all the same problem. 
and to solve that problem, what we want 
to do is to count derangements. 
So derangements or permutations with no 
singleton cycles. So this is our table of 
sets of cycles, which are equivalent to 
permutations with the ones that have 
singleton cycles graded out. 
So there's nine permutation of side four 
that have no singleton cycles. 
probability that nobody [COUGH] winds up 
with their own hat is only four, it's 
nine over 24. 
and so this maybe is not a familiar 
sequence, 
so let's see how to analyze that with the 
symbolic method. 
now we just go through our [COUGH] our, 
our regular regiment. 
We're going to define D to be the class 
of all derangements size is number of 
atoms standard labelled atoms. 
generating function is always the same 
exponential generating function. 
And so, what's the combinatorial 
construction? 
so one way to phrase it is this way. 
A derangement is a set of cycles where 
the length of the cycles is greater than 
one and we just indicate that with cycle 
greater than one of atoms. 
A permutations is a set of cycles of 
atoms this one excludes the ones of 
length one. 
[COUGH] that one immediately transfers, 
so derangements or permutations in those 
singleton cycles is what it says. and so 
set is z to the whatever it is, and 
what's the generating function for the 
cycles of length greater than one. Well, 
generating function for all cycles is z + 
z^2 / 2 + z [INAUDIBLE] like that, and 
we're just leaving out the first term. 
so that immediate translation and that's 
the same as log of one over one minus z 
minus z. 
that [COUGH] is that infinite series is 
exactly log(1/r-z)-z). 
one over one minus z minus z. 
And if we simply that, we get 
e^-z(-z/(1-z)). 
/ 1 - z. 
We need translation to the generating 
function. 
another way to derive it which maybe is 
even easier to understand is we can say 
that a what is a permutation? 
A permutation is a set of singleton 
cycles crossed with a derangement. 
and so, that's, that's another way to 
phrase it. 
And then that one immediately translates 
to e to the z, 
d of z equals one over one minus z and 
solve for d of z, you get the same 
result. 
so symbolic method gives us the 
generating function. 
Now, extracting coefficients from this 
one is a little more complicated. 
we actually did it already in our lecture 
on asymptotics. 
so that's the result is that it's 
asymptotics to one over e. 
and let's just look at each of the 
elements of that. 
So first of all 
we're looking since we want a 
probability, it's convenient that we're 
using exponential generating functions 
and our probability denominator is n 
factorial. 
so we're taking advantage of that 
[COUGH] coincidence. It's not really a 
coincidence, but in this case it it works 
out. 
So to get the probability, we just look 
at the coefficient of z to the n in the 
generating function not in factorial time 
z to the n, because it's going to divide 
it right out. 
so [COUGH] that's d to the n over n 
factorial. 
So, and what's that coefficient? Well, 
it's a convolution e to the minus z times 
one one, one minus z. 
you, you just do the convolution of the 
coefficient of the z to the n in that is 
the sum of k from zero to n and minus one 
to the k over k factorial. 
and that's a straight convolution and 
then that's a sum that we looked at as 
one of our examples for bounding the tail 
in the asymptotics lecture to show that's 
asintotic to one over e, that's very 
close to one over e. 
we're going to look at an easier way to 
get this at the end of this lecture. 
but the symbolic method gets us there and 
then provides a practical solution to 
this kind of problem. 
the actual chance that if you go to a 
party and 
get yourself in a state of inebriation 
and wind up in a random room. 
you've got a pretty good probability that 
nobody ends up in their own room, 
36%. 
or maybe a way to tell your parents about 
this problem is when students graduate 
and throw their hats in the air and 
everybody catches a random hat, 36% 
probability nobody gets their hats back. 
actually your parents probably want you 
to get your, or the rental company 
probably wants you to get your own hat 
back. 
and so there's the idea of generalized 
derangements so if, if you've got a 
random hat, you can always get your own 
hat back by following the cycle. 
So student four wound up with ten's hat, 
she can go to ten, and ten's got six's 
hat, then she can go to six. Six has 15's 
hat, then she go to 15 and 15 there's her 
hat. 
so, following the cycle we'll get your 
hat back. so then, now we have the more 
general problem, what's the probability 
that all cycles are a blank bigger than 
N, that everybody is going to have to 
would have to follow at least N talk to 
at least N friends or N people, N random 
people to get their hat back, so that's a 
generalized derangements problem. 
What's the probability that all cycles 
are a blank bigger than N? 
now that problem it's much more difficult 
to analyze, but with the symbolic method 
we can get right to the generating 
function. So, it's just generalizing the 
arguement that I just gave D sub N is the 
class of all generalized deragements. no 
cycles of [INAUDIBLE] are equal to M and 
everything else is the same. 
so the construction is it's a set of 
cycles that are bigger than N of atoms. 
that translates directly to generating 
functions you just started Z to the M 
plus one, so it's the same series now 
starting at Z to the M plus one or that's 
log of one over one minus Z minus Z 
squared over Z, Z squared over two all 
the way up to Z to the M over M. 
And simplifying that, we have e to the 
minus z minus e squared over two minus z 
cubed over three and so forth up to z to 
the m over m over one minus z. 
So that's the generating function that we 
get immediately from the symbolic method. 
and very, and, and quite simpyl. 
without the symbolic method you might 
have some trouble getting to this 
generating function on your own. 
This, certainly other, certainly recent a 
lot of these things is possible to do, 
because what's behind the symbolic method 
is so simple. 
but the symbolic method really makes it 
so that a child can do it. 
so that's the 
a generating function equation. 
Now, to find the answer to this problem, 
we need to extract coefficients from this 
equation. Now, that one not so clear that 
would be an M way convolution, and you 
know, go ahead and try to extract 
coefficients from that one. 
So that's going to motivate, how could we 
find the coefficient, how can we estimate 
the coefficient of Z to the N in that 
complicated function that's going to 
motivate the second part of analytic 
commonotorics. The analytic transfer 
thorems, but that's the basic 
introduction to symbolic method for 
labeled objects.