Definitions

Symbolic combinatorics

Symbolic combinatorics

Symbolic combinatorics in mathematics is a technique of analytic combinatorics that uses symbolic representations of combinatorial classes to derive their generating functions. The underlying mathematics, including the Pólya enumeration theorem, are explained on the page of the fundamental theorem of combinatorial enumeration.

Procedure

Typically, one starts with the neutral class mathcal{E}, containing a single object of size 0 (the neutral object, often denoted by epsilon), and one or more atomic classes 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 mathcal{A} has generating function 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 mathcal{E} and mathcal{Z} are E(z) = 1 and Z(z) = z, respectively. The disjoint union is also simple — for disjoint sets mathcal{B} and mathcal{C}, mathcal{A} = mathcal{B} cup mathcal{C} implies 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 mathcal{A} and mathcal{B}, we mark members of each set with a distinct marker, for example circ for members of mathcal{A} and bullet for members of mathcal{B}. The combinatorial sum is then:

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

A(x)=sum_{n=0}^{infty}A_{n}x^{n}

Product

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

sum_{k=0}^{n}A_{k}B_{n-k}.

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

mathcal{A} = mathcal{B} times mathcal{C} implies A(z) = B(z) cdot C(z).

Sequence

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

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 mathcal{B}, or an ordered pair, ordered triple, etc. This leads to the relation

A(z) = 1 + B(z) + B(z)^{2} + B(z)^{3} + cdots = frac{1}{1 - B(z)}.

Set

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

mathfrak{P}{mathcal{B}} = prod_{beta in mathcal{B}}(mathcal{E} + {beta}),

which leads to the relation

begin{align}A(z) &{} = prod_{beta in mathcal{B}}(1 + z^
) >
&{} = 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{align}

where the expansion

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 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,

mathfrak{M}{mathcal{B}} = prod_{beta in mathcal{B}} mathfrak{G}{beta}.

This leads to the relation

begin{align} A(z) &{} = prod_{beta in mathcal{B}} (1 - z^
)^{-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{align}

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

Other elementary constructions

Other important elementary constructions are:

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

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

Construction Generating function
mathcal{A} = mathfrak{C}{mathcal{B}} A(z) = sum_{k=1}^{infty} frac{phi(k)}{k} ln frac{1}{1 - B(z^{k})} (where phi(k), is the Euler totient function)
mathcal{A} = Thetamathcal{B} A(z) = zfrac{d}{dz}B(z)
mathcal{A} = mathcal{B} circ mathcal{C} A(z) = B(C(z)),

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

mathcal{G} = mathcal{Z} times mathfrak{G}{mathcal{G}}.

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

G(z) = frac{z}{1 - G(z)}

or

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 mathcal{I}, where the size of each integer is its value:

mathcal{I} = mathcal{Z} times mathfrak{G}{mathcal{Z}}

The OGF of mathcal{I} is then

I(z) = frac{z}{1 - z}.

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

mathcal{P} = mathfrak{M}{mathcal{I}}.

The OGF of mathcal{P} is

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 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.

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 [1 ldots n]. 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 A_{n} is defined as

A(x)=sum_{n=0}^{infty}A_{n}frac{x^{n}}{n!}.

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

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

alpha star beta = {(alpha',beta'): (alpha',beta') mbox{ is well-labelled, } rho(alpha') = alpha, rho(beta') = beta }.

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

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 k and n-k, there are {n choose k} ways to do the relabelling. Therefore, the total number of objects of size n is

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,

A(z) cdot B(z).,

Sequence

The sequence construction mathcal{A} = mathfrak{G}{mathcal{B}} is defined similarly to the unlabelled case:
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,
A(z) = frac{1}{1 - B(z)}

Set

In labelled structures, a set of k elements corresponds to exactly k! sequences. This is different from the unlabelled case, where some of the permutations may coincide. Thus for mathcal{A} = mathfrak{P}{mathcal{B}}, we have
A(z) = sum_{k = 0}^{infty} frac{B(z)^k}{k!} = exp(B(z))

Cycle

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

A(z) = sum_{k = 0}^{infty} frac{B(z)^k}{k} = lnleft(frac{1}{1-B(z)}right).

Other elementary constructions

The operators

mathfrak{C}_operatorname{even}, mathfrak{C}_operatorname{odd}, mathfrak{P}_operatorname{even}, mbox{ and } mathfrak{P}_operatorname{odd}

represent cycles of even and odd length, and sets of even and odd cardinality.

Examples

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

mathfrak{P}(mathfrak{P}_{ge 1}(mathcal{Z})).

The decomposition

mathfrak{P}(mathfrak{C}(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 may be found on the page on Stirling numbers and exponential generating functions.

External links

Search another word or see Symbolic combinatoricson Dictionary | Thesaurus |Spanish
Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature
FAVORITES
RECENT

;