Analytic Combinatorics teaches a calculus that enables precise quantitative predictions of large combinatorial structures. This course introduces the symbolic method to derive functional relations among ordinary, exponential, and multivariate generating functions, and methods in complex analysis for deriving accurate asymptotics from the GF equations.
Words and Strings
Loading...
En provenance du cours de Princeton University
Analytic Combinatorics
15 notes
À partir de la leçon
Labelled Structures and EGFs
This lecture introduces labelled objects, where the atoms that we use to build objects are distinguishable. We use exponential generating functions EGFs to study combinatorial classes built from labelled objects. As in Lecture 1, we define combinatorial constructions that lead to EGF equations, and consider numerous examples from classical combinatorics.
Rencontrer les enseignants
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
Next we, we're going to look for combinatorial constructions corresponding
to labelled objects called words And these are another way to look at the
strings that we considered in the last lecture.
And again, there's many more details on applications and motivating applications
and results in part one of the course. in this part we're going to focus on, on
the math and on the analytical combinatorics, to show that the symbolic
method works for a broad variety of combinatorial classes.
so last time we talked about strings, it's a sequence of N characters drawn
from an M-character alphabet. So that there's M to the N different
strings, as just a sequence of characters.
This time we're going to talk about that same object, but we're going to look at
it as a word. So it's a sequence of M label sets that
have N objects in total. There are also M to the N words, and so
it's a sequence of sets. Now these are really two different ways
of looking at the same object. Because if you take the string and you
take every occurrence of the letter I as being the Ith set in the sequence.
So for example one in this string appears in position seven and that's the only
place it appears so that corresponds to the set seven Two appears in one, three,
and eight. So that corresponds to the set, one,
three, and eight. there's no three.
four appears in position two and four and five in positions five, six, and nine.
You can see a direct correspondence between strings and sequences of sets.
We refer the sequences of sets as words. so that's the correspondence again just
what I just described. so what's the difference between strings
and words? there's no difference, it's only the
point of view. last time when we talked about strings,
we were concerned about sequences of characters in relation to one another in
the sequence, like how many sequences of zeros in a row are there or is does a
pattern occur. for this lecture in words, we're more
concerned with the sets of indices and not so much in the the sequence, and
there's applications where that point of view it the one that, that we want to
push. so another way to look at the same thing
is the, the balls and urn model, which is classical in, in commonotoric.
so if we have n labeled balls and we throw them into m urns you can think of
when ball i, goes into urn j, that means j character in the string is the i
character in this string is j. Hm, so when five goes into earn one, and
we just write a one in the string. so this balls in, and, and we don't,
balls and earn sequences is simply corresponds to strings.
and we don't care about the the order in which the balls are in the urns, they're
sets of indices. Though balls and urns sequences are
equivalent to both strings of words and so, sometimes, we use that model, for
describing these objects. Its more like words in terms of its a
sequence of sets of objects. so how many words are there?
or if you throw in Bolst and Merns, how many configurations are there?
Well, you can tell by the language that I'm using that this is going to be very
simply described with the symbolic method.
so we'll call the combinatorial class a w sub n since we have a sequence on m urns.
so and then the size function is just the total number objects.
and so the generating function is straight forward from the definition.
and so we've got all those examples that I just talked about.
But the key thing is that the combinatorial construction says that a
word on M letters is a sequence of M urns the sequence of sets.
and so the generating function, the, the set of objects is e to the z, sequence of
size M is that to the nth power. So the generating function is e to the m
z. Coefficient of z to the n in that in
times n factorial is m to the n. So that's the basic construction and
counting, for words. and again using the standard paradigm, we
can build of this same construction. to study variations, and there's many and
important applications of variations. but again, just to summarize, a string
is, we think of as unlabeled objects that are just a sequence.
we use OGF and our enumeration is, it's a sequence of M different unlabeled
objects. So the generating functions, 1 over 1
minus e and the end, that's what we talked about last time.
And we use that to study algorithms like string searching algorithms where as a
word is labeled objects, it's exponential-generating functions.
It's sets of objects, but you can also write it as a string the generating, the
construction is a sequence of sets of objects, size M.
and we get the same count, and we use that to study hashing algorithms, and
more generally, occupancy problems in combinatorics.
but we can do variations. again, just as for permutations, to get
results for problems and applications problems using the, the same symbolic
method that we use for the basic problem. And these are two very famous variations,
and again, if you want to see many more details about these, go to part one of
the course. So a birthday sequence is a word where no
letter appears twice. we throw the balls in the urns and we
never get two balls in an urn. a coupon collector sequence is a word
where every letter appears at least once. so birthday sequence is about if you have
a room with n people in it. And you want, and there's 365 different
birthdays. what's the chance that no two people have
the same birthday? coupon collector sequence is how many
things do you have to see before you get everything in the collection?
And there's many, many applications of both of these.
And they're classic in commonotorics. So let's look at a simple modification of
that basic construction to study the problem of how many birthday sequences
are there. so that's our words where no set has more
than one element and, and again, it's easy to define the class and, and the
generating functions, and the construction is simply a birthday
sequence with alpha to M letters, is a sequence, of length M, of either empty
urns or urns with one ball in them. So that means the EGF of birthday
sequences, is just one plus Z to the N. And a counting sequence is, coefficient
of N factorial. And N factorial times coefficient is Z to
the N in that, which is m times m plus, minus 1 and so forth.
And then if you want to get the probability that a random words of
birthday sequence, you divide by that m to the n and so forth.
So that's again, just a simple example of modifying the basic construction to be
able to quickly get a generating function for such sequences.
Or, a, the other, another example is coupon collectors, at the other end of
the spectrum. So, that's a string that uses all the
letters in the alphabet. So, it's a sequence of sets.
None of them are empty, so by now you can practically write down this construction
yourself. A birthday sequence is a sequence of
length and of set, that are all of 5 bigger than 0.
The transfer theorem immediately gives a generating function equation, so a set of
size, greater than zero, is E to the Z minus one.
Subtract off the first term the set of zero and then sequence of m of those is
either the z minus 1 to the n. So that's a generating function that
describes the the, for the coupon collector sequences, exponential
generating function. and so here's some other related
combinatorial classes. so another name for coupon collector
sequence is an m surject, surjection. That's an m word with no empty set.
if we take off the constraint on m and you just say it's a word that's an m
sur-, surjection for some m So that is, there's some value of N that
uh,[COUGH] it's a sequence of sets, none of which are empty, for some size of the
sequence. So these are examples of surjections.
so how many sur, surjections are there of length N?
So this one's all 1s. This one's all 1s and 2s.
and then the rest of them are 1s, 2s, and 3s.
but from analytic combinatorics, it's easy to write down the construction for
this. for M-surjections, we had sequence of
length M and we got that generating function.
For surjections in general we take out the constraint on m so that means a seq-
the set greater than 0 is e to z minus 1. Sequence of those is 1 over 1 minus that.
So it's 1 over 2 minus e to the z. That's the generating function for
surjections. Now to extract an estimate for the
coefficient of z to the M and N. Again it's best done with complex
asymptotics that we'll talk about in the second part of this course.
Turns out to be about N factorial over 2 log 2 of the n plus 1.
Again, a very simple modification to the basic construction but it leads us to a
generating function equation that we can later analyze.
And by the way, the analysis at the other end is going to have come from similar
general transfer theorems. so, this is the, types of variations that
we, see on words. So, we start with the basic construction,
and, so maybe we generalize it to talk about coupon collectors, where we insist
that all the letter counts are bigger than a certain amount.
or my birthday where there, all the letter counts are less than a certain
amount. and these things are relevant in the
analysis of of computer algorithms and many other applications.
or you can do the constraint really in any way that, you know, you want the
occupancies to all be odd or all be even or prime numbers, whatever you want.
leads to a generating function equation. and then we talked about surjections,
though again starting with a basic thing we get a galaxy of related constructions,
that the constructions are quite simple and they lead to generating functions of
all different character. and that's a introduction to the analytic
commonatorics of words and strings, and how to use the symbolic method to get
exponential generating functions for a variety of commonatorial classes.
Explorer notre catalogue
Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.
Coursera propose un accès universel à la meilleure formation au monde,
en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.
© 2018 Coursera Inc. Tous droits réservés.
