Symbolic method (combinatorics)

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.
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 on permutations,
Bender and Goldman on prefabs, and Joyal on combinatorial species.
Note that this symbolic method in enumeration is unrelated to "Blissard's symbolic method", which is just another old name for umbral calculus.
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.

Classes of combinatorial structures

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 be the ordinary generating function 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 g 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 Pólya enumeration theorem 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. Clearly the orbits do not intersect and we may add the respective generating functions. Suppose, for example, that we want to enumerate unlabelled sequences of length two or three of some objects contained in a set X. There are two sets of slots, the first one containing two slots, and the second one, three slots. The group acting on the first set is the full symmetric group, which in symbolic combinatorics is traditionally denoted. The group acting on the second set is, analogously,. We represent this by the following formal power series in X:
where the term is used to denote the set of orbits under G and, which denotes in the obvious way the process of distributing the objects from X with repetition into the n slots. Similarly, consider the labelled problem of creating cycles of arbitrary length from a set of labelled objects X. This yields the following series of actions of cyclic groups:
Clearly we can assign meaning to any such power series of quotients with respect to permutation groups, where we restrict the groups of degree n to the conjugacy classes of the symmetric group, which form a unique factorization domain. This motivates the following definition.
A class of combinatorial structures is a formal series
where is the set of primes of the UFD and
In the following we will simplify our notation a bit and write e.g.
for the classes mentioned above.

The Flajolet–Sedgewick fundamental theorem

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 into equations in the generating functions of these structures.
Let be a class of combinatorial structures. The OGF of where X has OGF and the EGF of where X is labelled with EGF are given by
and
In the labelled case we have the additional requirement that X not contain elements of size zero. It will sometimes prove convenient to add one to to indicate the presence of one copy of the empty set. It is possible to assign meaning to both and To prove the theorem simply apply PET and the labelled enumeration theorem.
The power of this theorem lies in the fact that it makes it possible to construct operators on generating functions that represent combinatorial classes. A structural equation between combinatorial classes thus translates directly into an equation in the corresponding generating functions. Moreover, in the labelled case it is evident from the formula that we may replace by the atom z and compute the resulting operator, which may then be applied to EGFs. We now proceed to construct the most important operators. The reader may wish to compare with the data on the cycle index page.

The sequence operator

This operator corresponds to the class
and represents sequences, i.e. the slots are not being permuted and there is exactly one empty sequence. We have
and

The cycle operator

This operator corresponds to the class
i.e., cycles containing at least one object. We have
or
and
This operator, together with the set operator, and their restrictions to specific degrees are used to compute random permutation statistics. There are two useful restrictions of this operator, namely to even and odd cycles.
The labelled even cycle operator is
which yields
This implies that the labelled odd cycle operator
is given by

The multiset/set operator

The series is
i.e., the symmetric group is applied to the nth slot. This creates multisets in the unlabelled case and sets in the labelled case. We include the empty set in both the labelled and the unlabelled case.
The unlabelled case is done using the function
so that
Evaluating we obtain
For the labelled case we have
In the labelled case we denote the operator by, and in the unlabelled case, by. This is because in the labeled case there are no multisets whereas in the unlabeled case there are multisets and sets, with the latter being given by

Procedure

Typically, one starts with the neutral class, containing a single object of size 0, and one or more atomic classes, each containing a single object of size 1. 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. These relations may be recursive. The elegance of symbolic combinatorics lies in that the set theoretic, or symbolic, relations translate directly into algebraic relations involving the generating functions.
In this article, we will follow the convention of using script uppercase letters to denote combinatorial classes and the corresponding plain letters for the generating functions.
There are two types of generating functions commonly used in symbolic combinatorics—ordinary generating functions, used for combinatorial classes of unlabelled objects, and exponential generating functions, used for classes of labelled objects.
It is trivial to show that the generating functions for and are and, respectively. The disjoint union is also simple — for disjoint sets and, implies. The relations corresponding to other operations depend on whether we are talking about labelled or unlabelled structures.

Combinatorial sum

The restriction of unions to disjoint unions is an important one; however, in the formal specification of symbolic combinatorics, it is too much trouble to keep track of which sets are disjoint. Instead, we make use of a construction that guarantees there is no intersection. In defining the combinatorial sum of two sets and, we mark members of each set with a distinct marker, for example for members of and for members of. The combinatorial sum is then:
This is the operation that formally corresponds to addition.

Unlabelled structures

With unlabelled structures, an ordinary generating function is used. The OGF of a sequence is defined as

Product

The product of two combinatorial classes and is specified by defining the size of an ordered pair as the sum of the sizes of the elements in the pair. Thus we have for and,. This should be a fairly intuitive definition. We now note that the number of elements in of size n is
Using the definition of the OGF and some elementary algebra, we can show that

Sequence

The sequence construction, denoted by is defined as
In other words, a sequence is the neutral element, or an element of, or an ordered pair, ordered triple, etc. This leads to the relation