Analytic combinatorics (NDMI087)
The lecture will take place on Monday at 9am in the room S8. The
exercises will take place on Tuesdays at 9am in S321 (third floor
corridor). Homework will be avalable as a substitute for those who
cannot attend the exercises. Note that the exercise session is once
every fortniight, starting on March 7. The course will be in English.
Brief synopsis: power series, ordinary and exponential generating
functions, basics of complex analysis, application of complex-analytic
tools in combinatorics. No prior knowledge of complex analysis is
needed. Some prior familiarity with generating functions, e.g. from the
basic course in Combinatorics and graphs, may be beneficial.
Literature:
Topics covered so far:
- 27. 2.: Formal power series (over a ring of coefficients with no
zero divisors): basic properties, existence of multiplicative inverses,
convergence of sequences of power series, composition of power series.
- 6. 3.: The notion of composable series, properties of composition:
continuity, associativity. Existence of neutral element with respect to
composition, existence of composition inverse. Ordinary (possibly
weighted) combinatorial classes, ordinary generating functions.
- 7. 3.: First recitation
- 13. 3.: Combinatorial interpretation of the sum, product and related operations with ordinary generating functions.
- 20. 3.: Labelled combinatorial classes and their exponential
generating functions. Combinatorial interpretation of the operations
with EGFs.
- 21. 3.: Second recitation
- 27. 3.: Basics of complex analysis of power series: growth rate,
radius of convergence. Analytic functions (in a point). Basic facts
about analytic functions (their sum, product etc. are analytic). Local
uniqueness: if two analytic functions agree in a point, then on a small
neigborhood of teh point they either agree everywhere, or agree nowhere
else.
- 3. 4.: Functions analytic on a domain. The sum of a convergent
power series is analytic in every point inside the circle of
convergence (without full proof). Basic topological notions: discrete
set, connected set, domain (=open, nonempty, connected set). The notion
of analytic continuation. Uniqueness of analytic continuations on a
domain.
- 4. 4.: Third recitation
- 10. 4.: Class cancelled. Next class will be the recitation class on April 18.
- 18.4.: Recitation consisting of a repetition of the lecture from 3. 4.
- 24. 4.: Relationship between radius of convergence and analytic
continuations: an analytic function cannot be continued to every point
on the boundary of its disk of convergence. An analytic function whose
series expansion in 0 has only nonnegative coefficients and radius of
convergence R cannot be continued into R. Rational functions, their
expansion into partial fractions and the corresponding coefficient
asymptotics. Meromorphic functions.
- 4. 5.: Fourth recitation