| 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.
|