Content deleted Content added
"Made {{stub}} into {{math-stub}}. This is an automatic update." |
Paul August (talk | contribs) m →Procedure: "set theoretic" -> "set-theoretic" |
||
Line 1:
'''
==Procedure==
Typically, one starts with the ''neutral class'' <math>\mathcal{E}</math>, containing a single object of size 0 (the ''neutral object'', often denoted by <math>\epsilon</math>), and one or more ''atomic classes'' <math>\mathcal{Z}</math>, each containing a single object of size 1. Next, [[Set theory|set-theoretic]] relations involving various simple operations, such as [[disjoint union]]s, [[Cartesian product|products]], [[Set (mathematics)|sets]], [[sequence]]s, and [[multiset]]s define more complex classes in terms of the already defined classes. These relations may be [[recursion|recursive]]. The elegance of symbolic combinatorics lies in that the set theoretic, or ''symbolic'', relations translate directly into ''[[algebra]]ic'' 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 <math>\mathcal{A}</math> has generating function <math>A(z)</math>).
There are two types of generating functions commonly used in symbolic combinatorics — [[ordinary generating function]]s, used for combinatorial classes of unlabelled objects, and [[exponential generating function]]s, used for classes of labelled objects.
It is trivial to show that the generating functions (either ordinary or exponential) for <math>\mathcal{E}</math> and <math>\mathcal{Z}</math> are <math>E(z) = 1</math> and <math>Z(z) = z</math>, respectively. The disjoint union is also simple — for disjoint sets <math>\mathcal{B}</math> and <math>\mathcal{C}</math>, <math>\mathcal{A} = \mathcal{B} \cup \mathcal{C}</math> implies <math>A(z) = B(z) + C(z)</math>. 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 [[Union (sets)|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 <math>\mathcal{A}</math> and <math>\mathcal{B}</math>, we mark members of each set with a distinct marker, for example <math>\circ</math> for members of <math>\mathcal{A}</math> and <math>\bullet</math> for members of <math>\mathcal{B}</math>. The combinatorial sum is then:
:<math>\mathcal{A} + \mathcal{B} = (\mathcal{A} \times \{\circ\}) \cup (\mathcal{B} \times \{\bullet\})</math>
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 <math>A_{n}</math> is defined as
:<math>A(x)=\sum_{n=0}^{\infty}A_{n}x^{n}</math>
===Product===
The [[Cartesian product|product]] of two combinatorial classes <math>\mathcal{A}</math> and <math>\mathcal{B}</math> 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 <math>a \in \mathcal{A}</math> and <math>b \in \mathcal{B}</math>, <math>|(a,b)| = |a| + |b|</math>. This should be a fairly intuitive definition. We now note that the number of elements in <math>\mathcal{A} \times \mathcal{B}</math> of size <var>n</var> is
:<math>\sum_{k=0}^{n}A_{k}B_{n-k}</math>
Using the definition of the OGF and some elementary algebra, we can show that
:<math>\mathcal{A} = \mathcal{B} \times \mathcal{C}</math> implies <math>A(z) = B(z) \cdot C(z)</math>
===Sequence===
The ''sequence construction'', denoted by <math>\mathcal{A} = \mathfrak{G}\{\mathcal{B}\}</math> is defined as
:<math>\mathfrak{G}\{\mathcal{B}\} = \mathcal{E} + \mathcal{B} + (\mathcal{B} \times \mathcal{B}) + (\mathcal{B} \times \mathcal{B} \times \mathcal{B}) + \cdots</math>
In other words, a sequence is the neutral element, or an element of <math>\mathcal{B}</math>, or an ordered pair, ordered triple, etc. This leads to the relation
:<math>A(z) = 1 + B(z) + B(z)^{2} + B(z)^{3} + \cdots = \frac{1}{1 - B(z)}</math>
===Set===
The ''set'' (or ''powerset'') ''construction'', denoted by <math>\mathcal{A} = \mathfrak{P}\{\mathcal{B}\}</math> is defined as
:<math>\mathfrak{P}\{\mathcal{B}\} = \prod_{\beta \in \mathcal{B}}(\mathcal{E} + \{\beta\})</math>
which leads to the relation
:<math>\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}</math>
where the expansion
:<math>\ln(1 + u) = \sum_{k = 1}^{\infty} \frac{(-1)^{k-1}u^{k}}{k} </math> was used to go from line 4 to line 5.
===Multiset===
The ''multiset construction'', denoted <math>\mathcal{A} = \mathfrak{M}\{\mathcal{B}\}</math> 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,
:<math>\mathfrak{M}\{\mathcal{B}\} = \prod_{\beta \in \mathcal{B}} \mathfrak{G}\{\beta\}</math>
This leads to the relation
:<math>\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}
</math>
where, similar to the above set construction, we expand <math>\ln (1 - z^{n})</math>, swap the sums, and substitute for the OGF of <math>\mathcal{B}</math>.
===Other elementary constructions===
Other important elementary constructions are:
*the ''cycle construction'' (<math>\mathfrak{C}\{\mathcal{B}\}</math>), like sequences except that cyclic rotations are not considered distinct
*''pointing'' (<math>\Theta\mathcal{B}</math>), in which each member of <math>\mathcal{B}</math> is augmented by a neutral (zero size) pointer to one of its atoms
*''substitution'' (<math>\mathcal{B} \circ \mathcal{C}</math>), in which each atom in a member of <math>\mathcal{B}</math> is replaced by a member of <math>\mathcal{C}</math>.
The derivations for these constructions are too complicated to show here. Here are the results:
{|
|-
! Construction
! Generating function
|-
|<math>\mathcal{A} = \mathfrak{C}\{\mathcal{B}\}</math>
|<math>A(z) = \sum_{k=1}^{\infty} \frac{\phi(k)}{k} \ln \frac{1}{1 - B(z^{k})}</math> (where <math>\phi(k)\,</math> is the [[Euler totient function]])
|-
|<math>\mathcal{A} = \Theta\mathcal{B}</math>
|<math>A(z) = z\frac{d}{dz}B(z)</math>
|-
|<math>\mathcal{A} = \mathcal{B} \circ \mathcal{C}</math>
|<math>A(z) = B(C(z))\,</math>
|}
===Examples===
Many combinatorial classes can be built using these elementary constructions. For example, the class of [[plane tree]]s (the order of the subtrees matters) is specified by the [[Recursion|recursive]] relation
:<math>\mathcal{G} = \mathcal{Z} \times \mathfrak{G}\{\mathcal{G}\}</math>
In other words, a tree is a root node of size 1 and a sequence of subtrees. This gives
:<math>G(z) = \frac{z}{1 - G(z)}</math>
or
:<math>G(z) = \frac{1 - \sqrt{1 - 4z}}{2}</math>
Another example (and a classic combinatorics problem) is [[integer partition]]s. First, define the class of positive integers <math>\mathcal{I}</math>, where the size of each integer is its value:
:<math>\mathcal{I} = \mathcal{Z} \times \mathfrak{G}\{\mathcal{Z}\}</math>
The OGF of <math>\mathcal{I}</math> is then
:<math>I(z) = \frac{z}{1 - z}</math>
Now, define the set of partitions <math>\mathcal{P}</math> as
:<math>\mathcal{P} = \mathfrak{M}\{\mathcal{I}\}</math>
The OGF of <math>\mathcal{P}</math> is
:<math>P(z) = \exp \left ( I(z) + \frac{1}{2} I(z^{2}) + \frac{1}{3} I(z^{3}) + \cdots \right ) </math>
Unfortunately, there is no closed form for <math>P(z)</math>; however, the OGF can be used to derive a [[recurrence relation]], or, using more advanced methods of analytic combinatorics, calculate the [[asymptotic analysis|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 <math>[1 \ldots n]</math>. ''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 [[Graph (mathematics)|labelled graph]]s.
With labelled structures, an [[exponential generating function]] (EGF) is used. The EGF of a sequence <math>A_{n}</math> is defined as
:<math>A(x)=\sum_{n=0}^{\infty}A_{n}\frac{x^{n}}{n!}</math>
===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 <math>\mathcal{A} \star \mathcal{B}</math>.
For a pair <math>\beta \in \mathcal{B}</math> and <math>\gamma \in \mathcal{C}</math>, 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 <math>\beta</math> and <math>\gamma</math>. 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.
To aid this development, let us define a function, <math>\rho</math>, that takes as its argument a (possibly weakly) labelled object <math>\alpha</math> and relabels its atoms in an order-consistent way so that <math>\rho(\alpha)</math> is well labelled. We then define the labelled product for two objects <math>\alpha</math> and <math>\beta</math> as
:<math>\alpha \star \beta = \{(\alpha',\beta'): (\alpha',\beta') \mbox{is well-labelled}, \rho(\alpha') = \alpha, \rho(\beta') = \beta \}</math>
Finally, the labelled product of two classes <math>\mathcal{A}</math> and <math>\mathcal{B}</math> is
:<math>\mathcal{A} \star \mathcal{B} = \bigcup_{\alpha \in \mathcal{A}, \beta \in \mathcal{B}} (\alpha \star \beta)</math>
The EGF can be derived by noting that for objects of size <math>k</math> and <math>n-k</math>, there are <math>{n \choose k}</math> ways to do the relabelling. Therefore, the total number of objects of size <math>n</math> is
:<math>\sum_{k=0}^{n}{n \choose k}A_{k}B_{n-k}</math>
This ''binomial convolution'' relation for the terms is equivalent to multiplying the EGFs,
:<math>A(z) \cdot B(z)</math>
===Sequence===
The ''sequence construction'' <math>\mathcal{A} = \mathfrak{G}\{\mathcal{B}\}</math> is defined similarly to the unlabelled case:
:<math>\mathfrak{G}\{\mathcal{B}\} = \mathcal{E} + \mathcal{B} + (\mathcal{B} \star \mathcal{B}) + (\mathcal{B} \star \mathcal{B} \star \mathcal{B}) + \cdots</math>
and again, as above,
:<math>A(z) = \frac{1}{1 - B(z)}</math>
===Set===
In labelled structures, a set of <math>k</math> elements corresponds to exactly <math>k!</math> sequences. This is different than the unlabelled case, where some of the permutations may coincide. Thus for <math>\mathcal{A} = \mathfrak{P}\{\mathcal{B}\}</math>, we have
:<math>A(z) = \sum_{k = 0}^{\infty} \frac{B(z)^k}{k!} = \exp(B(z))</math>
===Cycle===
Cycles are also easier than in the unlabelled case. A cycle of length <math>k</math> corresponds to <math>k</math> distinct sequences. Thus for <math>\mathcal{A} = \mathfrak{C}\{\mathcal{B}\}</math>, we have
:<math>A(z) = \sum_{k = 0}^{\infty} \frac{B(z)^k}{k} = \ln(\frac{1}{1-B(z)})</math>
===Other elementary constructions===
===Examples===
[[Category:combinatorics]]
[[de:Symbolisch Kombinatorik]]
| |||