Analytic combinatorics

Thursday 9:00-9:45 and 13:10-13:55 in S6 or in the corridor next to room 323

The lecture deals with advanced topics related to generating functions, and the applications of complex analysis in combinatorics. For detailed synopsis see SIS.

The exam will take the form of a homework assignment. Download the assignment here. The deadline for submission of solutions is the end of February 2013. See the assignment itself for more specific rules.

Topics covered so far:

 11. 10. Formal power series: their basic operations, existence and uniqueness of reciprocals (multiplicative inverses). Composition of series, existence of composition inverses. Formal derivative and its properties.  The notion of combinatorial class, its counting function. 18. 10. Combinatorial classes (weighted or not), their ordinary generating functions. Combinatorial interpretation of power series operations (addition and multiplication) on generating functions: disjoint union and Cartesian product. Lagrange inversion formula, with a sketch of a combinatorial proof. 25. 10. Finished the sketch of proof of LIF. Example: planted trees with arbitrary degrees are counted by Catalan numbers. Another example: computing the expected waiting time for an occurrence of a fixed word in a random bit sequence. 1. 11. Labelled combinatorial classes, exponential generating functions. Operations: disjoint sum, labelled product, composition. Examples: EGF for set partitions (possibly with bounded number of blocks or bounded block-size), fixed-point-free permutations, 2-regular graphs. Computing efficiently the number of connected graphs on a given number of vertices. Counting spanning trees of a complete graph using EGFs and LIF. 8. 11. Convergent series, their exponential growth rate and radius of convergence. Analytic functions, their operations, uniqueness of analytic continuations. 15. 11. Examples of functions constructed as analytic continuations: the exponential, the (co)sine, the square root. Singularities on the boundary of the convergence disk, Pringsheim's theorem on non-negative series. Determining the exponential growth rate from the position of singularities; example: rooted trees. Classification of isolated singularities. Meromorphic functions. The ratio of two analytic functions is meromorphic. Computing the coefficients of rational functions via partial fractions. 22. 11. Example of a rational generating function: expressing integers as a sum of 3k (or 4k) summands. Approximation of meromorphic functions by rational functions. Example: estimating the probability that a permutation has no cycle of length at most k. 29. 11. Curves in the complex plane, complex integration, existence of primitive functions for analytic functions, curve homotopy and its relationship to integration, Cauchy coefficient formula. 6. 12. Residues; their application in computing complex integrals. Example: various ways to estimate the number of ordered set partitions. 13. 12. Saddle-point-type bounds. Example: estimates for n!. Asymptotics of coefficients of non-integral powers of (1-x), gamma function: definition (for positive reals) and basic properties, its relationship to estimates of binomial coefficients. 20. 12. Transfer theorem for functions approximated by a power of (1-x). Example: trees in which each vertex has at most two children, permutations with all cycles of odd length. 3. 1. Multivariate generating functions, combinatorial classes with parameters. Examples: integer compositions counted by length and number of occurrences of  '1'; planted trees counted by number of leaves and root degree. 10. 1. Notable discrete probability distributions (geometric, negative-binomial, binomial, Poisson), their probability generating functions. Pointwise convergence of PGFs implies convergence of associated discrete random variables in distribution (without proof). Convergence in distribution for discrete variables derived from combinatorial classes with parameters (with discrete limiting distributions). Examples: binomial random variables with constant expectation converge to Poisson distribution; number of cycles of fixed length in a random large permutation is asymptotically Poisson; number of returns to the x-axis in a random Dyck path is asymptotically negative-binomial.