Enumerative Combinatorics

Department: 
MATH
Course Number: 
7012
Hours - Lecture: 
3
Hours - Lab: 
0
Hours - Recitation: 
0
Hours - Total Credit: 
3
Typical Scheduling: 
Usually every odd Fall

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.

Prerequisites: 

MATH 4032 or permission of instructor

Course Text: 

No text

Topic Outline: 
  • 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