Symbolic method (combinatorics)

This operator corresponds to the class

${\displaystyle 1+E_{1}+E_{2}+E_{3}+\cdots }$

and represents sequences, i.e. the slots are not being permuted and there is exactly one empty sequence. We have

${\displaystyle F(z)=1+\sum _{n\geq 1}Z(E_{n})(f(z),f(z^{2}),\ldots ,f(z^{n}))=1+\sum _{n\geq 1}f(z)^{n}={\frac {1}{1-f(z)}}}$

and

${\displaystyle G(z)=1+\sum _{n\geq 1}\left({\frac {1}{|E_{n}|}}\right)g(z)^{n}={\frac {1}{1-g(z)}}.}$

This operator corresponds to the class

${\displaystyle C_{1}+C_{2}+C_{3}+\cdots }$

i.e., cycles containing at least one object. We have

${\displaystyle F(z)=\sum _{n\geq 1}Z(C_{n})(f(z),f(z^{2}),\ldots ,f(z^{n}))=\sum _{n\geq 1}{\frac {1}{n}}\sum _{d\mid n}\varphi (d)f(z^{d})^{n/d}}$

or

${\displaystyle F(z)=\sum _{k\geq 1}\varphi (k)\sum _{m\geq 1}{\frac {1}{km}}f(z^{k})^{m}=\sum _{k\geq 1}{\frac {\varphi (k)}{k}}\log {\frac {1}{1-f(z^{k})}}}$

and

${\displaystyle G(z)=\sum _{n\geq 1}\left({\frac {1}{|C_{n}|}}\right)g(z)^{n}=\log {\frac {1}{1-g(z)}}.}$

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 CYC_even is

${\displaystyle C_{2}+C_{4}+C_{6}+\cdots }$

which yields

${\displaystyle G(z)=\sum _{n\geq 1}\left({\frac {1}{|C_{2n}|}}\right)g(z)^{2n}={\frac {1}{2}}\log {\frac {1}{1-g(z)^{2}}}.}$

This implies that the labelled odd cycle operator CYC_odd

${\displaystyle C_{1}+C_{3}+C_{5}+\cdots }$

is given by

${\displaystyle G(z)=\log {\frac {1}{1-g(z)}}-{\frac {1}{2}}\log {\frac {1}{1-g(z)^{2}}}={\frac {1}{2}}\log {\frac {1+g(z)}{1-g(z)}}.}$

The series is

${\displaystyle 1+S_{1}+S_{2}+S_{3}+\cdots }$

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

${\displaystyle M(f(z),y)=\sum _{n\geq 0}y^{n}Z(S_{n})(f(z),f(z^{2}),\ldots ,f(z^{n}))}$

so that

${\displaystyle {\mathfrak {M}}(f(z))=M(f(z),1).}$

Evaluating ${\displaystyle M(f(z),1)}$ we obtain

${\displaystyle F(z)=\exp \left(\sum _{\ell \geq 1}{\frac {f(z^{\ell })}{\ell }}\right).}$

For the labelled case we have

${\displaystyle G(z)=1+\sum _{n\geq 1}\left({\frac {1}{|S_{n}|}}\right)g(z)^{n}=\sum _{n\geq 0}{\frac {g(z)^{n}}{n!}}=\exp g(z).}$

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

${\displaystyle F(z)=\exp \left(\sum _{\ell \geq 1}(-1)^{\ell -1}{\frac {f(z^{\ell })}{\ell }}\right).}$

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).}$

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}})+\cdots .}$

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}+\cdots ={\frac {1}{1-B(z)}}.}$

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{aligned}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{aligned}}}$

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.

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{aligned}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{aligned}}}$

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 important elementary constructions are:

• the cycle construction (${\displaystyle {\mathfrak {C}}\{{\mathcal {B}}\}}$), like sequences except that cyclic rotations are not considered distinct
• pointing (${\displaystyle \Theta {\mathcal {B}}}$), in which each member of B is augmented by a neutral (zero size) pointer to one of its atoms
• substitution (${\displaystyle {\mathcal {B}}\circ {\mathcal {C}}}$), in which each atom in a member of B is replaced by a member of 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))}$

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

${\displaystyle {\mathcal {G}}={\mathcal {Z}}\times \operatorname {SEQ} \{{\mathcal {G}}\}.}$

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

${\displaystyle G(z)={\frac {z}{1-G(z)}}}$

we solve for G(z) by multiplying ${\displaystyle 1-G(z)}$ to get

${\displaystyle G(z)-G(z)^{2}=z}$

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

${\displaystyle G(z)={\frac {1-{\sqrt {1-4z}}}{2}}.}$

Another example (and a classic combinatorics problem) is integer partitions. First, define the class of positive integers ${\displaystyle {\mathcal {I}}}$, where the size of each integer is its value:

${\displaystyle {\mathcal {I}}={\mathcal {Z}}\times \operatorname {SEQ} \{{\mathcal {Z}}\}}$

The OGF of ${\displaystyle {\mathcal {I}}}$ is then

${\displaystyle I(z)={\frac {z}{1-z}}.}$

Now, define the set of partitions ${\displaystyle {\mathcal {P}}}$ as

${\displaystyle {\mathcal {P}}=\operatorname {MSET} \{{\mathcal {I}}\}.}$

The OGF of ${\displaystyle {\mathcal {P}}}$ is

${\displaystyle P(z)=\exp \left(I(z)+{\frac {1}{2}}I(z^{2})+{\frac {1}{3}}I(z^{3})+\cdots \right).}$

Unfortunately, there is no closed form for ${\displaystyle P(z)}$; 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.

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 ${\displaystyle ({\mathcal {A}}_{1},\dots ,{\mathcal {A}}_{r})}$ is a set of ${\displaystyle r}$ equations ${\displaystyle {\mathcal {A}}_{i}=\Phi _{i}({\mathcal {A}}_{1},\dots ,{\mathcal {A}}_{r})}$, where ${\displaystyle \Phi _{i}}$ is an expression, whose atoms are ${\displaystyle {\mathcal {E}},{\mathcal {Z}}}$ and the ${\displaystyle {\mathcal {A}}_{i}}$'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 ${\displaystyle {\mathcal {A}}_{\text{even}}}$ and ${\displaystyle {\mathcal {A}}_{\text{odd}}}$. Those classes should satisfy the equation ${\displaystyle {\mathcal {A}}_{\text{odd}}={\mathcal {Z}}\times \operatorname {Seq} _{\geq 1}{\mathcal {A}}_{\text{even}}}$ and ${\displaystyle {\mathcal {A}}_{\text{even}}={\mathcal {Z}}\times \operatorname {Seq} {\mathcal {A}}_{\text{odd}}}$.

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 ${\displaystyle {\mathcal {A}}\star {\mathcal {B}}.}$

For a pair ${\displaystyle \beta \in {\mathcal {B}}}$ and ${\displaystyle \gamma \in {\mathcal {C}}}$, 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 ${\displaystyle \beta }$ and ${\displaystyle \gamma }$. 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, ${\displaystyle \rho }$, that takes as its argument a (possibly weakly) labelled object ${\displaystyle \alpha }$ and relabels its atoms in an order-consistent way so that ${\displaystyle \rho (\alpha )}$ is well labelled. We then define the labelled product for two objects ${\displaystyle \alpha }$ and ${\displaystyle \beta }$ as

${\displaystyle \alpha \star \beta =\{(\alpha ',\beta '):(\alpha ',\beta '){\text{ is well-labelled, }}\rho (\alpha ')=\alpha ,\rho (\beta ')=\beta \}.}$

Finally, the labelled product of two classes ${\displaystyle {\mathcal {A}}}$ and ${\displaystyle {\mathcal {B}}}$ is

${\displaystyle {\mathcal {A}}\star {\mathcal {B}}=\bigcup _{\alpha \in {\mathcal {A}},\beta \in {\mathcal {B}}}(\alpha \star \beta ).}$

The EGF can be derived by noting that for objects of size ${\displaystyle k}$ and ${\displaystyle n-k}$, there are ${\displaystyle {n \choose k}}$ ways to do the relabelling. Therefore, the total number of objects of size ${\displaystyle n}$ is

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

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

${\displaystyle A(z)\cdot B(z).}$

The sequence construction ${\displaystyle {\mathcal {A}}={\mathfrak {G}}\{{\mathcal {B}}\}}$ is defined similarly to the unlabelled case:

${\displaystyle {\mathfrak {G}}\{{\mathcal {B}}\}={\mathcal {E}}+{\mathcal {B}}+({\mathcal {B}}\star {\mathcal {B}})+({\mathcal {B}}\star {\mathcal {B}}\star {\mathcal {B}})+\cdots }$

and again, as above,

${\displaystyle A(z)={\frac {1}{1-B(z)}}}$

In labelled structures, a set of ${\displaystyle k}$ elements corresponds to exactly ${\displaystyle k!}$ sequences. This is different from the unlabelled case, where some of the permutations may coincide. Thus for ${\displaystyle {\mathcal {A}}={\mathfrak {P}}\{{\mathcal {B}}\}}$, we have

${\displaystyle A(z)=\sum _{k=0}^{\infty }{\frac {B(z)^{k}}{k!}}=\exp(B(z))}$

Cycles are also easier than in the unlabelled case. A cycle of length ${\displaystyle k}$ corresponds to ${\displaystyle k}$ distinct sequences. Thus for ${\displaystyle {\mathcal {A}}={\mathfrak {C}}\{{\mathcal {B}}\}}$, we have

${\displaystyle A(z)=\sum _{k=0}^{\infty }{\frac {B(z)^{k}}{k}}=\ln \left({\frac {1}{1-B(z)}}\right).}$

In labelled structures, the min-boxed product ${\displaystyle {\mathcal {A}}_{\min }={\mathcal {B}}^{\square }\star {\mathcal {C}}}$ is a variation of the original product which requires the element of ${\displaystyle {\mathcal {B}}}$ in the product with the minimal label. Similarly, we can also define a max-boxed product, denoted by ${\displaystyle {\mathcal {A}}_{\max }={\mathcal {B}}^{\blacksquare }\star {\mathcal {C}}}$, by the same manner. Then we have,

${\displaystyle A_{\min }(z)=A_{\max }(z)=\int _{0}^{z}B'(t)C(t)\,dt.}$

or equivalently,

${\displaystyle A_{\min }'(t)=A_{\max }'(t)=B'(t)C(t).}$

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 ${\displaystyle {\mathcal {L}}}$ be the class of such trees. The recursive specification is now ${\displaystyle {\mathcal {L}}={\mathcal {Z}}^{\square }\star \operatorname {SET} ({\mathcal {L}}).}$

The operators CYC_even, CYC_odd, SET_even, and SET_odd represent cycles of even and odd length, and sets of even and odd cardinality.

Stirling numbers of the second kind may be derived and analyzed using the structural decomposition

${\displaystyle \operatorname {SET} (\operatorname {SET} _{\geq 1}({\mathcal {Z}})).}$

The decomposition

${\displaystyle \operatorname {SET} (\operatorname {CYC} ({\mathcal {Z}}))}$

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.