Symbolic method (combinatorics): Difference between revisions

Revision as of 05:23, 15 September 2004

Revision as of 05:50, 15 September 2004

Line 1:

'''AnalyticSymbolic combinatorics''' is a technique of [[analytic combinatorics]] (a sub-branch of [[combinatorics]]) that describesuses symbolic representations of [[combinatorial class]]es usingto [[generating function]]s, which arederive oftentheir [[analyticgenerating function]]s, but sometimes [[formal power series]].

==Procedure==

Two types of generating functions are commonly used — [[Ordinary generating function|ordinary]] andsoxed ciorial clnerating function]]s,

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.

TwAn important tec )ge for deriving generating functions is [[symbolic combinatorics]].

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

Given a generating function, analytic combinatorics attempts to [[Oimt] toctiog funsis|imt] toctiobehaviorion

There are two types of generating functions commonly used in symbolic combinatorics &mdash; [[ordinary generating function]]s, used for combinatorial classes of unlabelled objects, and [[exponential generating function]]s, used for classes of labelled objects.

Taon,unven asepornceal class]ahoan,unven aseptopshbqh: This, whichinvolv].

funsis|

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 &mdash; 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).

Tao [[generati'funcSlasularity (mao [mao co)|sg [[f{{stub}}

==Combinatorial sum==

[[Category:unctions is [[s

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 <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}) + \ldots</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} + \ldots = \frac{1}{1 - B(z)}</math>

[[Category:unctions is [[scombinatorics]]