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, 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 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(z) be the ordinary generating function (OGF) of the objects, then the OGF of the configurations is given by the substituted cycle index
Z ( G ) ( f ( z ) , f ( z 2 ) , … , f ( z n ) ) . {\displaystyle Z(G)(f(z),f(z^{2}),\ldots ,f(z^{n})).}
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
g ( z ) n | G | . {\displaystyle {\frac {g(z)^{n}}{|G|}}.}
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 S 2 {\displaystyle S_{2}} , which in symbolic combinatorics is traditionally denoted E 2 {\displaystyle E_{2}} . The group acting on the second set is, analogously, S 3 = E 3 {\displaystyle S_{3}=E_{3}} . We represent this by the following formal power series in X:
X 2 / E 2 + X 3 / E 3 {\displaystyle X^{2}/E_{2}\;+\;X^{3}/E_{3}}
where the term X n / G {\displaystyle X^{n}/G} is used to denote the set of orbits under G and X n = X × ⋯ × X {\displaystyle X^{n}=X\times \cdots \times X} , 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:
… excerpt ends here. Continue reading the full article.
