In
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...
, the symbolic method is a technique for
counting combinatorial objects. It uses the internal structure of the objects to derive formulas for their
generating function
In mathematics, a generating function is a representation of an infinite sequence of numbers as the coefficients of a formal power series. Generating functions are often expressed in closed form (rather than as a series), by some expression invo ...
s. The method is mostly associated with
Philippe Flajolet and is detailed in Part A of his book with
Robert Sedgewick, ''
Analytic Combinatorics
Analytic combinatorics uses techniques from complex analysis to solve problems in enumerative combinatorics, specifically to find asymptotic estimates for the coefficients of generating functions.
History
One of the earliest uses of analyti ...
'', 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
Leonhard Euler ( ; ; ; 15 April 170718 September 1783) was a Swiss polymath who was active as a mathematician, physicist, astronomer, logician, geographer, and engineer. He founded the studies of graph theory and topology and made influential ...
,
Arthur Cayley
Arthur Cayley (; 16 August 1821 – 26 January 1895) was a British mathematician who worked mostly on algebra. He helped found the modern British school of pure mathematics, and was a professor at Trinity College, Cambridge for 35 years.
He ...
,
Schröder
Schröder (Schroeder) is a German language, German surname often associated with the Schröder family. Notable people with the surname include:
* Arthur Schröder (1892–1986), German actor
* Atze Schröder, stage name of German comedian Hubertu ...
,
Ramanujan,
Riordan,
Knuth, , 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
In combinatorics, combinatorial mathematics, the theory of combinatorial species is an abstract, systematic method for deriving the generating functions of discrete structures, which allows one to not merely count these structures but give bijectiv ...
.
Note that this symbolic method in enumeration is unrelated to "Blissard's symbolic method", which is just another old name for
umbral calculus
The term umbral calculus has two related but distinct meanings.
In mathematics, before the 1970s, umbral calculus referred to the surprising similarity between seemingly unrelated polynomial equations and certain shadowy techniques used to prove ...
.
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
In computing, procedural generation is a method of creating data algorithmically as opposed to manually, typically through a combination of human-generated content and algorithms coupled with computer-generated randomness and processing power. I ...
, all of them being suitable to automatization via
computer algebra
In mathematics and computer science, computer algebra, also called symbolic computation or algebraic computation, is a scientific area that refers to the study and development of algorithms and software for manipulating expression (mathematics), ...
.
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
The Pólya enumeration theorem, also known as the Redfield–Pólya theorem and Pólya counting, is a theorem in combinatorics that both follows from and ultimately generalizes Burnside's lemma on the number of orbits of a group action on a set. T ...
solves this problem in the unlabelled case. Let ''f''(''z'') be the
ordinary generating function
In mathematics, a generating function is a representation of an infinite sequence of numbers as the coefficient
In mathematics, a coefficient is a Factor (arithmetic), multiplicative factor involved in some Summand, term of a polynomial, a se ...
(OGF) of the objects, then the OGF of the configurations is given by the substituted
cycle index In combinatorial mathematics a cycle index is a polynomial in several variables which is structured in such a way that information about how a group of permutations acts on a set can be simply read off from the coefficients and exponents. This com ...
:
In the labelled case we use an
exponential generating function
In mathematics, a generating function is a representation of an infinite sequence of numbers as the coefficients of a formal power series. Generating functions are often expressed in closed form (rather than as a series), by some expression invo ...
(EGF) ''g''(''z'') of the objects and apply the
Labelled enumeration theorem
In combinatorial mathematics, the labelled enumeration theorem is the counterpart of the Pólya enumeration theorem for the labelled case, where we have a set of labelled objects given by an exponential generating function (EGF) ''g''(''z'') which ...
, 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
The Pólya enumeration theorem, also known as the Redfield–Pólya theorem and Pólya counting, is a theorem in combinatorics that both follows from and ultimately generalizes Burnside's lemma on the number of orbits of a group action on a set. T ...
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 mathematics, a power series (in one variable) is an infinite series of the form
\sum_^\infty a_n \left(x - c\right)^n = a_0 + a_1 (x - c) + a_2 (x - c)^2 + \dots
where ''a_n'' represents the coefficient of the ''n''th term and ''c'' is a co ...
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 (orbits) 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. (The orbits with respect to two groups from the same conjugacy class are isomorphic.) This motivates the following definition.
A class