# Lecture Slides

Here are lecture slides that accompany *Analytic Combinatorics*.,
under development and schedule for completion in April 2012.

These slides are for the first half of an undergraduate course
taught at Princeton, developed to provide an overview
of *An Introduction to the Analysis of Algorithms* and
*Analytic Combinatorics*.

The course format is "introduce-read-discuss". We *introduce* a
set of topics in lecture; students *read* about the topics and
work selected exercises between lectures, and we *discuss* any
questions about the reading and the exercises at the beginning of the
next lecture. Each lecture ends with a slide or two giving assignments
to be completed before the next lecture and to be discussed at the
beginning of the next lecture. Some lectures
contain in-class exercises.

While much of the reading material may be difficult for a typical undergraduate to master on such a quick pass through, a substantial fraction of the coverage is elementary. One purpose of the discussion format is to help students learn to master the elementary material so as to make the book content more accessible.

Lecture slides are available
both in 1-up format (accessible by
clicking the lecture name when it is activated as a link) and in
“4-up” format (accesible by editing the extension
`-2x2` to the filename in your browser).
*Example:* Lecture 1
slides are in the file `AC01-OGFs.pdf`, accessible by clicking
“Combinatorial Structures and OGFs” in the “Topic” column.
The 4-up version is in the file `AC01-OGFs-2x2.pdf`.

CHAPTER | TOPIC | READING | EXTRA |
---|---|---|---|

1 | Combinatorial Structures and OGFs | 15-94 | |

2 | Labelled Structures and EGFs | 95-149 | |

3 | Combinatorial Parameters and MGFs | 151-219 | |

4 | Complex Analysis, Rational and Meromorphic Asymptotics | 223-288 | |

5 | Applications of Rational and Meromorphic Asymptotics | 289-374 | |

6 | Singularity Analysis of Generating Functions | 375-438 | |

7 | Applications of Singularity Analysis | 439-540 | |

8 | Saddle-Point Asymptotics | 541-608 | |

9 | Mellin Transform Asymptotics | 311, 762-767 |

## Errata in Lecture slides

**Lecture 1, slide 9.**$S_N$ should be $M^N$ not $N^M$**Lecture 1, slide 16.**Final expression for $G_N$ is incorrect (see Slide 15).**Lecture 1, slide 30.**$A(z)^k$ should be $A(z^k)$ (in video)**Lecture 1, slide 31.**$A(z)^k$ should be $A(z^k)$ (in video)**Lecture 1, slide 42.**$1-z^M$ -> $(1-z)^M$ in denominator of GF for compositions into $M$ parts.**Lecture 1, slide 43.***distinct*powers of 2 in second question.**Lecture 1, slide 47.**Replace $z^{10}$ by $z^{20}$ in last two rows.**Lecture 1, slide 53.**"z+" is missing from RHS of three equations at the bottom.**Lecture 1, slide 55.**Missing right paren in eqn for $H(z)$.**Lecture 3, slide 35.**$uG^D$ -> $uG$ on RHS of construction.**Lecture 3, slide 46.**"the number of different letters in w" -> "the number of letters that appear exactly k times in w"**Lecture 7, slide 6.**Expression for $\phi^\prime(u)$ should have "2" in the numerator.**Lecture 7, slide 10.**$\lambda + 2\lambda$ -> $\lambda + 2\lambda^2$.**Lecture 7, slide 31.**delete "standard scale" label.