Welcome to Week 1 of Analytic Combinatorics. Each Friday, I’ll send
an email like this one describing lectures and problem sets for the
week.
You can see that the whole course is posted on the booksite, but
we need the flexibility to respond to current conditions, so please be
aware that assignments are not "official" until you get this Friday e-mail.
Each Friday's e-mail is the authoritative source of precisely
what is assigned and when it is due.
Each lecture corresponds to a chapter in Flajolet-Sedgewick, so
everyone is encouraged to study the corresponding chapter in the book
conjunction with the lectures. The coverage in the book is somewhat
encyclopedic, so we are only expecting that people will turn to the
material associated with what's in the lecture, perhaps scanning
through the rest to see what's there and perhaps find something else
of interest.
There are three lectures to watch this week, but two of them contain
now-familiar material from Lecture 5 of Analysis of Algorithms.
Lecture 0 presents a motivating application, random sampling.
Lectures 1 and 2 lay out the basic tools that we use in
analytic combinatorics to specify classes of combinatorial objects and
to define generating functions that enumerate them. Since much of this
material was introduced in Lecture 5 of Analysis of Algorithms, you may
wish to review these lectures at higher-than-usual speed, or just review
the slides to decide which subsections to watch.
----------
Lecture 0: Random Sampling. Since the advent of computers, mathematicians
and scientists have been fascinated by the idea that computation can
be used to generate large random samples of combinatorial structures
in order to study their properties. Doing so accurately and efficiently
is a research challenge that very often can be effectively addresses
with analytic combinatorics.
Lecture 1: Combinatorial Structures and OGFs. Our first lecture is
about the symbolic method, where we define combinatorial constructions
that we can use to define classes of combinatorial objects. The
constructions are integrated with transfer theorems that lead to
equations that define generating functions whose coefficients
enumerate the classes. We consider numerous examples from classical
combinatorics.
Lecture 2: 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.
----------
Your assignment for this week, due at 11:59PM on
Thursday, March 24, 2022
is to write up and submit solutions to
Note I.23 and Note II.11 on the "Analytic
Combinatorics" booksite. Please note that "Notes" in the book are
often written as statements instead of questions, so the versions on
the booksite are slightly reworded to clarify what you need to do.
Then, generate a large combinatorial structure of your choice, preferably
one that is easily visualized or one that has an interesting property that
you might want to study. The bigger, the better. Write a short description
of your experience.
Also, as usual, submit a potential exam question on the week's material.
Submit files named
“AC1-Q1.pdf"
“AC1-Q2.pdf"
"AC1-Qsample.pdf"
"AC1-QQ.pdf"
via codePost.
RS