Symbolic method (combinatorics)

Last updated

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.

Contents

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. [3]

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

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. 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 , and on the second slot, . 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 (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 of combinatorial structures is a formal series

where (the "A" is for "atoms") 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 FlajoletSedgewick fundamental theorem

A theorem in the FlajoletSedgewick 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.

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 (the most common example is the case of unlabelled sets) and To prove the theorem simply apply PET (Pólya enumeration theorem) 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 SEQ

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 CYC

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 SET, 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 CYCeven is

which yields

This implies that the labelled odd cycle operator CYCodd

is given by

The multiset/set operator MSET/SET

The series is

i.e., the symmetric group is applied to the slots. This creates multisets in the unlabelled case and sets in the labelled case (there are no multisets in the labelled case because the labels distinguish multiple instances of the same object from the set being put into different slots). 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 SET, and in the unlabelled case, by MSET. 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

Procedure

Typically, one starts with the neutral class, containing a single object of size 0 (the neutral object, often denoted by ), 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 (so the class has generating function ).

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 (either ordinary or exponential) 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 (and ordinary or exponential generating functions).

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 (be careful, however; this affects the semantics of the operation as well). 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 (OGF) 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

implies

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

Set

The set (or powerset) construction, denoted by is defined as

which leads to the relation

where the expansion

was used to go from line 4 to line 5.

Multiset

The multiset construction, denoted is a generalization of the set construction. In the set construction, each element can occur zero or one times. In a multiset, each element can appear an arbitrary number of times. Therefore,

This leads to the relation

where, similar to the above set construction, we expand , swap the sums, and substitute for the OGF of .

Other elementary constructions

Other important elementary constructions are:

The derivations for these constructions are too complicated to show here. Here are the results:

ConstructionGenerating function
(where is the Euler totient function)

Examples

Many combinatorial classes can be built using these elementary constructions. For example, the class of plane trees (that is, trees embedded in the plane, so that the order of the subtrees matters) is specified by the recursive relation

In other words, a tree is a root node of size 1 and a sequence of subtrees. This gives

we solve for G(z) by multiplying to get

subtracting z and solving for G(z) using the quadratic formula gives

Another example (and a classic combinatorics problem) is integer partitions. First, define the class of positive integers , where the size of each integer is its value:

The OGF of is then

Now, define the set of partitions as

The OGF of is

Unfortunately, there is no closed form for ; 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.

Specification and specifiable classes

The elementary constructions mentioned above allow us to define the notion of specification. This specification allows us to use a set of recursive equations, with multiple combinatorial classes.

Formally, a specification for a set of combinatorial classes is a set of equations , where is an expression, whose atoms are and the 's, and whose operators are the elementary constructions listed above.

A class of combinatorial structures is said to be constructible or specifiable when it admits a specification.

For example, the set of trees whose leaves' depth is even (respectively, odd) can be defined using the specification with two classes and . Those classes should satisfy the equation and .

Labelled structures

An object is weakly labelled if each of its atoms has a nonnegative integer label, and each of these labels is distinct. An object is (strongly or well) labelled, if furthermore, these labels comprise the consecutive integers . Note: some combinatorial classes are best specified as labelled structures or unlabelled structures, but some readily admit both specifications. A good example of labelled structures is the class of labelled graphs.

With labelled structures, an exponential generating function (EGF) is used. The EGF of a sequence is defined as

Product

For labelled structures, we must use a different definition for product than for unlabelled structures. In fact, if we simply used the cartesian product, the resulting structures would not even be well labelled. Instead, we use the so-called labelled product, denoted

For a pair and , we wish to combine the two structures into a single structure. In order for the result to be well labelled, this requires some relabelling of the atoms in and . We will restrict our attention to relabellings that are consistent with the order of the original labels. Note that there are still multiple ways to do the relabelling; thus, each pair of members determines not a single member in the product, but a set of new members. The details of this construction are found on the page of the Labelled enumeration theorem.

To aid this development, let us define a function, , that takes as its argument a (possibly weakly) labelled object and relabels its atoms in an order-consistent way so that is well labelled. We then define the labelled product for two objects and as

Finally, the labelled product of two classes and is

The EGF can be derived by noting that for objects of size and , there are ways to do the relabelling. Therefore, the total number of objects of size is

This binomial convolution relation for the terms is equivalent to multiplying the EGFs,

Sequence

The sequence construction is defined similarly to the unlabelled case:

and again, as above,

Set

In labelled structures, a set of elements corresponds to exactly sequences. This is different from the unlabelled case, where some of the permutations may coincide. Thus for , we have

Cycle

Cycles are also easier than in the unlabelled case. A cycle of length corresponds to distinct sequences. Thus for , we have

Boxed product

In labelled structures, the min-boxed product is a variation of the original product which requires the element of in the product with the minimal label. Similarly, we can also define a max-boxed product, denoted by , by the same manner. Then we have,

or equivalently,

Example

An increasing Cayley tree is a labelled non-plane and rooted tree whose labels along any branch stemming from the root form an increasing sequence. Then, let be the class of such trees. The recursive specification is now

Other elementary constructions

The operators CYCeven, CYCodd, SETeven, and SETodd represent cycles of even and odd length, and sets of even and odd cardinality.

Example

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.

See also

Related Research Articles

In complex analysis, an entire function, also called an integral function, is a complex-valued function that is holomorphic on the whole complex plane. Typical examples of entire functions are polynomials and the exponential function, and any finite sums, products and compositions of these, such as the trigonometric functions sine and cosine and their hyperbolic counterparts sinh and cosh, as well as derivatives and integrals of entire functions such as the error function. If an entire function has a root at , then , taking the limit value at , is an entire function. On the other hand, the natural logarithm, the reciprocal function, and the square root are all not entire functions, nor can they be continued analytically to an entire function.

In complex analysis, a branch of mathematics, analytic continuation is a technique to extend the domain of definition of a given analytic function. Analytic continuation often succeeds in defining further values of a function, for example in a new region where the infinite series representation which initially defined the function becomes divergent.

In mathematical analysis, the Lagrange inversion theorem, also known as the Lagrange–Bürmann formula, gives the Taylor series expansion of the inverse function of an analytic function.

In mathematics, a generating function is a way of encoding an infinite sequence of numbers by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary series, the formal power series is not required to converge: in fact, the generating function is not actually regarded as a function, and the "variable" remains an indeterminate. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general linear recurrence problem. One can generalize to formal power series in more than one indeterminate, to encode information about infinite multi-dimensional arrays of numbers.

In mathematics, a Dirichlet series is any series of the form

<span class="mw-page-title-main">Mertens function</span> Summatory function of the Möbius function

In number theory, the Mertens function is defined for all positive integers n as

In probability theory, the Azuma–Hoeffding inequality gives a concentration result for the values of martingales that have bounded differences.

<span class="mw-page-title-main">Dyadic transformation</span> Doubling map on the unit interval

The dyadic transformation is the mapping

Enumerative combinatorics is an area of combinatorics that deals with the number of ways that certain patterns can be formed. Two examples of this type of problem are counting combinations and counting permutations. More generally, given an infinite collection of finite sets Si indexed by the natural numbers, enumerative combinatorics seeks to describe a counting function which counts the number of objects in Sn for each n. Although counting the number of elements in a set is a rather broad mathematical problem, many of the problems that arise in applications have a relatively simple combinatorial description. The twelvefold way provides a unified framework for counting permutations, combinations and partitions.

In conformal field theory and representation theory, a W-algebra is an associative algebra that generalizes the Virasoro algebra. W-algebras were introduced by Alexander Zamolodchikov, and the name "W-algebra" comes from the fact that Zamolodchikov used the letter W for one of the elements of one of his examples.

The statistics of random permutations, such as the cycle structure of a random permutation are of fundamental importance in the analysis of algorithms, especially of sorting algorithms, which operate on random permutations. Suppose, for example, that we are using quickselect to select a random element of a random permutation. Quickselect will perform a partial sort on the array, as it partitions the array according to the pivot. Hence a permutation will be less disordered after quickselect has been performed. The amount of disorder that remains may be analysed with generating functions. These generating functions depend in a fundamental way on the generating functions of random permutation statistics. Hence it is of vital importance to compute these generating functions.

<span class="mw-page-title-main">Bessel–Clifford function</span>

In mathematical analysis, the Bessel–Clifford function, named after Friedrich Bessel and William Kingdon Clifford, is an entire function of two complex variables that can be used to provide an alternative development of the theory of Bessel functions. If

The use of exponential generating functions (EGFs) to study the properties of Stirling numbers is a classical exercise in combinatorial mathematics and possibly the canonical example of how symbolic combinatorics is used. It also illustrates the parallels in the construction of these two types of numbers, lending support to the binomial-style notation that is used for them.

Coherent states have been introduced in a physical context, first as quasi-classical states in quantum mechanics, then as the backbone of quantum optics and they are described in that spirit in the article Coherent states. However, they have generated a huge variety of generalizations, which have led to a tremendous amount of literature in mathematical physics. In this article, we sketch the main directions of research on this line. For further details, we refer to several existing surveys.

In mathematics, the oscillator representation is a projective unitary representation of the symplectic group, first investigated by Irving Segal, David Shale, and André Weil. A natural extension of the representation leads to a semigroup of contraction operators, introduced as the oscillator semigroup by Roger Howe in 1988. The semigroup had previously been studied by other mathematicians and physicists, most notably Felix Berezin in the 1960s. The simplest example in one dimension is given by SU(1,1). It acts as Möbius transformations on the extended complex plane, leaving the unit circle invariant. In that case the oscillator representation is a unitary representation of a double cover of SU(1,1) and the oscillator semigroup corresponds to a representation by contraction operators of the semigroup in SL(2,C) corresponding to Möbius transformations that take the unit disk into itself.

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 are being distributed into n slots and a permutation group G which permutes the slots, thus creating equivalence classes of configurations. There is a special re-labelling operation that re-labels the objects in the slots, assigning labels from 1 to k, where k is the total number of nodes, i.e. the sum of the number of nodes of the individual objects. The EGF of the number of different configurations under this re-labelling process is given by

In mathematics, a transformation of a sequence's generating function provides a method of converting the generating function for one sequence into a generating function enumerating another. These transformations typically involve integral formulas applied to a sequence generating function or weighted sums over the higher-order derivatives of these functions.

In mathematics, the field of logarithmic-exponential transseries is a non-Archimedean ordered differential field which extends comparability of asymptotic growth rates of elementary nontrigonometric functions to a much broader class of objects. Each log-exp transseries represents a formal asymptotic behavior, and it can be manipulated formally, and when it converges, corresponds to actual behavior. Transseries can also be convenient for representing functions. Through their inclusion of exponentiation and logarithms, transseries are a strong generalization of the power series at infinity and other similar asymptotic expansions.

In analytic number theory, a Dirichlet series, or Dirichlet generating function (DGF), of a sequence is a common way of understanding and summing arithmetic functions in a meaningful way. A little known, or at least often forgotten about, way of expressing formulas for arithmetic functions and their summatory functions is to perform an integral transform that inverts the operation of forming the DGF of a sequence. This inversion is analogous to performing an inverse Z-transform to the generating function of a sequence to express formulas for the series coefficients of a given ordinary generating function.

A Boltzmann sampler is an algorithm intended for random sampling of combinatorial structures. If the object size is viewed as its energy, and the argument of the corresponding generating function is interpreted in terms of the temperature of the physical system, then a Boltzmann sampler returns an object from a classical Boltzmann distribution.

References

  1. Foata, Dominique; Schützenberger, Marcel-P. (1970). "Théorie géométrique des polynômes Eulériens". Lectures Notes in Mathematics. Lecture Notes in Mathematics. 138. doi: 10.1007/BFb0060799 . ISBN   978-3-540-04927-2.
  2. Bender, Edward A.; Goldman, Jay R. (1971). "Enumerative uses of generating functions". Indiana University Mathematics Journal. 20 (8): 753–764. doi: 10.1512/iumj.1971.20.20060 .
  3. Joyal, André (1981). "Une théorie combinatoire des séries formelles". Advances in Mathematics . 42: 1–82. doi: 10.1016/0001-8708(81)90052-9 .