In combinatorics, the symbolic method is a technique for counting combinatorial objects.
It uses the internal structure of the objects to derive formulas for their generating functions.
The method is mostly associated with Philippe Flajolet and is detailed in Part A of his book with Robert Sedgewick, Analytic Combinatorics, while the rest of the book explains how to use complex analysis in order to get asymptotic and probabilistic results on the corresponding generating functions.
During two centuries, generating functions were popping up via the corresponding recurrences on their coefficients (as can be seen in the seminal works of Bernoulli, Euler, Arthur Cayley, Schröder, Ramanujan, Riordan, Knuth, Comtet [fr], etc.).
It was then slowly realized that the generating functions were capturing many other facets of the initial discrete combinatorial objects, and that this could be done in a more direct formal way: The recursive nature of some combinatorial structures translates, via some isomorphisms, into noteworthy identities on the corresponding generating functions.
Following the works of Pólya, further advances were thus done in this spirit in the 1970s with generic uses of languages for specifying combinatorial classes and their generating functions, as found in works by Foata and Schützenberger[1] on permutations, Bender and Goldman on prefabs,[2] and Joyal on combinatorial species.
The symbolic method in combinatorics constitutes the first step of many analyses of combinatorial structures, which can then lead to fast computation schemes, to asymptotic properties and limit laws, to random generation, all of them being suitable to automatization via computer algebra.
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 We are able to enumerate filled slot configurations using either PET in the unlabelled case or the labelled enumeration theorem in the labelled case.
We now ask about the generating function of configurations obtained when there is more than one set of slots, with a permutation group acting on each.
Suppose, for example, that we want to enumerate unlabelled sequences of length two or three of some objects contained in a set X.
, which denotes in the obvious way the process of distributing the objects from X with repetition into the n slots.
A theorem in the Flajolet–Sedgewick theory of symbolic combinatorics treats the enumeration problem of labelled and unlabelled combinatorial classes by means of the creation of symbolic operators that make it possible to translate equations involving combinatorial structures directly (and automatically) into equations in the generating functions of these structures.
The power of this theorem lies in the fact that it makes it possible to construct operators on generating functions that represent combinatorial classes.
This is because in the labeled case there are no multisets (the labels distinguish the constituents of a compound combinatorial class) whereas in the unlabeled case there are multisets and sets, with the latter being given by Typically, one starts with the neutral class
Next, set-theoretic relations involving various simple operations, such as disjoint unions, products, sets, sequences, and multisets define more complex classes in terms of the already defined classes.
The relations corresponding to other operations depend on whether we are talking about labelled or unlabelled structures (and ordinary or exponential generating functions).
Instead, we make use of a construction that guarantees there is no intersection (be careful, however; this affects the semantics of the operation as well).
of size n is Using the definition of the OGF and some elementary algebra, we can show that The sequence construction, denoted by
subtracting z and solving for G(z) using the quadratic formula gives Another example (and a classic combinatorics problem) is integer partitions.
; however, the OGF can be used to derive a recurrence relation, or using more advanced methods of analytic combinatorics, calculate the asymptotic behavior of the counting sequence.
This specification allows us to use a set of recursive equations, with multiple combinatorial classes.
For example, the set of trees whose leaves' depth is even (respectively, odd) can be defined using the specification with two classes
We will restrict our attention to relabellings that are consistent with the order of the original labels.
The details of this construction are found on the page of the Labelled enumeration theorem.
is This binomial convolution relation for the terms is equivalent to multiplying the EGFs, The sequence construction
is defined similarly to the unlabelled case: and again, as above, In labelled structures, a set of
Stirling numbers of the second kind may be derived and analyzed using the structural decomposition The decomposition is used to study unsigned Stirling numbers of the first kind, and in the derivation of the statistics of random permutations.
A detailed examination of the exponential generating functions associated to Stirling numbers within symbolic combinatorics may be found on the page on Stirling numbers and exponential generating functions in symbolic combinatorics.