Symbolic method (combinatorics)

Symbolic combinatorics is a technique of analytic combinatorics (a sub-branch of combinatorics) that uses symbolic representations of combinatorial classes to derive their generating functions.

Procedure

Typically, one starts with the neutral class ${\displaystyle {\mathcal {E}}}$ , containing a single object of size 0 (the neutral object, often denoted by ${\displaystyle \epsilon }$ ), and one or more atomic classes ${\displaystyle {\mathcal {Z}}}$ , 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 ${\displaystyle {\mathcal {A}}}$  has generating function ${\displaystyle A(z)}$ ).

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 ${\displaystyle {\mathcal {E}}}$  and ${\displaystyle {\mathcal {Z}}}$  are ${\displaystyle E(z)=1}$  and ${\displaystyle Z(z)=z}$ , respectively. The disjoint union is also simple — for disjoint sets ${\displaystyle {\mathcal {B}}}$  and ${\displaystyle {\mathcal {C}}}$ , ${\displaystyle {\mathcal {A}}={\mathcal {B}}\cup {\mathcal {C}}}$  implies ${\displaystyle A(z)=B(z)+C(z)}$ . 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 ${\displaystyle {\mathcal {A}}}$  and ${\displaystyle {\mathcal {B}}}$ , we mark members of each set with a distinct marker, for example ${\displaystyle \circ }$  for members of ${\displaystyle {\mathcal {A}}}$  and ${\displaystyle \bullet }$  for members of ${\displaystyle {\mathcal {B}}}$ . The combinatorial sum is then:

${\displaystyle {\mathcal {A}}+{\mathcal {B}}=({\mathcal {A}}\times \{\circ \})\cup ({\mathcal {B}}\times \{\bullet \})}$ 

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 ${\displaystyle A_{n}}$  is defined as

${\displaystyle A(x)=\sum _{n=0}^{\infty }A_{n}x^{n}}$ 

Product

The product of two combinatorial classes ${\displaystyle {\mathcal {A}}}$  and ${\displaystyle {\mathcal {B}}}$  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 ${\displaystyle a\in {\mathcal {A}}}$  and ${\displaystyle b\in {\mathcal {B}}}$ , ${\displaystyle |(a,b)|=|a|+|b|}$ . This should be a fairly intuitive definition. We now note that the number of elements in ${\displaystyle {\mathcal {A}}\times {\mathcal {B}}}$  of size n is

${\displaystyle \sum _{k=0}^{n}A_{k}B_{n-k}}$ 

Using the definition of the OGF and some elementary algebra, we can show that

${\displaystyle {\mathcal {A}}={\mathcal {B}}\times {\mathcal {C}}}$  implies ${\displaystyle A(z)=B(z)\cdot C(z)}$ 

Sequence

The sequence construction, denoted by ${\displaystyle {\mathcal {A}}={\mathfrak {G}}\{{\mathcal {B}}\}}$  is defined as

${\displaystyle {\mathfrak {G}}\{{\mathcal {B}}\}={\mathcal {E}}+{\mathcal {B}}+({\mathcal {B}}\times {\mathcal {B}})+({\mathcal {B}}\times {\mathcal {B}}\times {\mathcal {B}})+\ldots }$ 

In other words, a sequence is the neutral element, or an element of ${\displaystyle {\mathcal {B}}}$ , or an ordered pair, ordered triple, etc. This leads to the relation

${\displaystyle A(z)=1+B(z)+B(z)^{2}+B(z)^{3}+\ldots ={\frac {1}{1-B(z)}}}$ 

Set

The set (or powerset) construction, denoted by ${\displaystyle {\mathcal {A}}={\mathfrak {P}}\{{\mathcal {B}}\}}$  is defined as

${\displaystyle {\mathfrak {P}}\{{\mathcal {B}}\}=\prod _{\beta \in {\mathcal {B}}}({\mathcal {E}}+\{\beta \})}$ 

which leads to the relation

${\displaystyle {\begin{matrix}A(z)&=&\prod _{\beta \in {\mathcal {B}}}(1+z^{|\beta |})\\&=&\prod _{n=1}^{\infty }(1+z^{n})^{B_{n}}\\&=&\exp \left(\ln \prod _{n=1}^{\infty }(1+z^{n})^{B_{n}}\right)\\&=&\exp \left(\sum _{n=1}^{\infty }B_{n}\ln(1+z^{n})\right)\\&=&\exp \left(\sum _{n=1}^{\infty }B_{n}\cdot \sum _{k=1}^{\infty }{\frac {(-1)^{k-1}z^{nk}}{k}}\right)\\&=&\exp \left(\sum _{k=1}^{\infty }{\frac {(-1)^{k-1}}{k}}\cdot \sum _{n=1}^{\infty }B_{n}z^{nk}\right)\\&=&\exp \left(\sum _{k=1}^{\infty }{\frac {(-1)^{k-1}B(z^{k})}{k}}\right)\end{matrix}}}$ 

where the expansion

${\displaystyle \ln(1+u)=\sum _{k=1}^{\infty }{\frac {(-1)^{k-1}u^{k}}{k}}}$  was used to go from line 4 to line 5.

Multiset

The multiset construction, denoted ${\displaystyle {\mathcal {A}}={\mathfrak {M}}\{{\mathcal {B}}\}}$  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,

${\displaystyle {\mathfrak {M}}\{{\mathcal {B}}\}=\prod _{\beta \in {\mathcal {B}}}{\mathfrak {G}}\{\beta \}}$ 

This leads to the relation

${\displaystyle {\begin{matrix}A(z)&=&\prod _{\beta \in {\mathcal {B}}}(1-z^{|\beta |})^{-1}\\&=&\prod _{n=1}^{\infty }(1-z^{n})^{-B_{n}}\\&=&\exp \left(\ln \prod _{n=1}^{\infty }(1-z^{n})^{-B_{n}}\right)\\&=&\exp \left(\sum _{n=1}^{\infty }-B_{n}\ln(1-z^{n})\right)\\&=&\exp \left(\sum _{k=1}^{\infty }{\frac {B(z^{k})}{k}}\right)\end{matrix}}}$ 

where, similar to the above set construction, we expand ${\displaystyle \ln(1-z^{n})}$ , swap the sums, and substitute for the OGF of ${\displaystyle {\mathcal {B}}}$ .

Other elementary constructions

Other important elementary constructions are the cycle construction (${\displaystyle {\mathfrak {C}}\{{\mathcal {B}}\}}$ ), which are like sequences except that cyclic rotations are not considered distinct, pointing (${\displaystyle \Theta {\mathcal {B}}}$ ), in which each member of ${\displaystyle {\mathcal {B}}}$  is augmented by a neutral (zero size) pointer to one of its atoms, and substitution (${\displaystyle {\mathcal {B}}\circ {\mathcal {C}}}$ ), in which each atom in a member of ${\displaystyle {\mathcal {B}}}$  is replaced by a member of ${\displaystyle {\mathcal {C}}}$ .

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

Construction	Generating function
${\displaystyle {\mathcal {A}}={\mathfrak {C}}\{{\mathcal {B}}\}}$	${\displaystyle A(z)=\sum _{k=1}^{\infty }{\frac {\phi (k)}{k}}\ln {\frac {1}{1-B(z^{k})}}}$  (where ${\displaystyle \phi (k)}$  is the Euler totient function)
${\displaystyle {\mathcal {A}}=\Theta {\mathcal {B}}}$	${\displaystyle A(z)=z{\frac {d}{dz}}B(z)}$
${\displaystyle {\mathcal {A}}={\mathcal {B}}\circ {\mathcal {C}}}$	${\displaystyle A(z)=B(C(z))}$