Symbolic method (combinatorics): Difference between revisions

Revision as of 08:18, 15 September 2004

Revision as of 08:49, 15 September 2004

Line 29:

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

===Set===

Line 83:

|}

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

[[Category:combinatorics]]