CO 601Fundamentals of Enumerative Combinatorics

Elementary counting, bijections. Sets, weights, decompositions. The ordinary generating series, sum, product, composition and differentiation lemmas; formal use in combinatorial identities. The algebra of formal power series. Strings on a finite alphabet. Unique factorization of strings. Pattern and noncommutative methods. The Maximal Decomposition Theorem. Rational and algebraic generating series, linear recurrence equations. Integer partitions. Functional equation. Ferrers graph, geometric decompositions, Euler's Pentagonal Number Theorem. Vector spaces over GF(q), linear transformations, finite forms of partition theorems, Gaussian coefficients. Inversions in permutations. The exponential generating series, rule of sum and product, composition and differentiation lemmas. Disjoint cycles and permutations, functions, set partitions, graphs. Lagrange's Implicit Function Theorem. Lattice paths, Wiener-Hopf Factorization. Lattice polygons, polyominos, trees and functions. Formal use in combinatorial identities. Enumeration under group action, Orbit-Stabilizer Theorem, Burnside's Lemma, Polya's Theorem. Necklaces, abstract trees and trees embedded in the plane.