Asymptotic combinatorics

In mathematics, analytic combinatorics is one of the many techniques of counting combinatorial objects. It uses the internal structure of the objects to derive formulas for their generating functions and then complex analysis techniques to get asymptotics. This particular theory was mostly developed by Philippe Flajolet, and is detailed in his book with Robert Sedgewick, Analytic Combinatorics. Earlier contributors to the key ideas and techniques include Leonhard Euler, Arthur Cayley, Srinivasa Ramanujan, George Pólya, and Donald Knuth.

Consider the problem of distributing objects given by a generating function into a set of n slots, where a permutation group G of degree n acts on the slots to create an equivalence relation of filled slot configurations, and asking about the generating function of the configurations by weight of the configurations with respect to this equivalence relation, where the weight of a configuration is the sum of the weights of the objects in the slots. We will first explain how to solve this problem in the labelled and the unlabelled case and use the solution to motivate the creation of classes of combinatorial structures.

The Pólya enumeration theorem solves this problem in the unlabelled case. Let f(z) be the ordinary generating function (OGF) of the objects, then the OGF of the configurations is given by the substituted cycle index

In the labelled case we use an exponential generating function (EGF) g(z) of the objects and apply the Labelled enumeration theorem, which says that the EGF of the configurations is given by

...
Wikipedia