Fundamental methods of enumeration and asymptotic analysis, including the use of inclusion/exclusion, generating functions, and recurrence relations. Applications to strings over a finite alphabet and graphs.
MATH 4032 or permission of instructor
- Methods of Estimation - Basic estimates of factorials and binomial coefficients, sums of positive terms, dissecting, bootstrapping, inclusion/exclusion and the Bonferroni inequalities
- Generating Functions - Ordinary generating functions, exponential generating functions, Stirling and Bell numbers, composition and inversion of power series, Lagrange-Burmann inversion, multivariate generating functions, applications to labeled graphs and binary trees
- Recurrence Relations - Linear recurrence relations with constant coefficients, families of recurrences, Catalan numbers, applications to strings over a finite alphabet, linear recurrences with varying coefficients, nonlinear recurrences
- Asymptotic Methods - Analytic generating functions, Darboux's method, the residue theorem and sums as integrals, small singularities, the saddle point method