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.