Symbolic method (combinatorics): Difference between revisions

Revision as of 22:34, 13 August 2018

Revision as of 09:27, 11 October 2018

Line 54:

The power of this theorem lies in the fact that it makes it possible to construct operators on generating functions that represent combinatorial classes. A structural equation between combinatorial classes thus translates directly into an equation in the corresponding generating functions. Moreover in the labelled case it is evident from the formula that we may replace <math>g(z)</math> by the atom ''z'' and compute the resulting operator, which may then be applied to EGFs. We now proceed to construct the most important operators. The reader may wish to compare with the data on the [[cycle index]] page.

=== The sequence operator <math>\operatorname{{nobold|{{math|SEQ}</math>}}} ===

This operator corresponds to the class

Line 70:

\frac{1}{1-g(z)}.</math>

=== The cycle operator <math>\operatorname{{nobold|{{math|CYC}</math>}}} ===

This operator corresponds to the class

Line 93:

\log \frac{1}{1-g(z)}.</math>

This operator, together with the set operator <math>\operatorname{{math|SET}</math>}, 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 <math>\operatorname{{math|CYC}_{\operatorname{sub|even}}</math>}} is

:<math>C_2 + C_4 + C_6 + \cdots</math>

Line 104:

\frac{1}{2} \log \frac{1}{1-g(z)^2}.</math>

This implies that the labelled odd cycle operator <math>\operatorname{{math|CYC}_{\operatorname{sub|odd}}</math>}}

:<math>C_1 + C_3 + C_5 + \cdots</math>

Line 113:

\frac{1}{2} \log \frac{1+g(z)}{1-g(z)}.</math>

=== The multiset/set operator <math>\operatorname{{nobold|{{math|MSET}}/\operatorname{{math|SET}</math>}}} ===

The series is

Line 138:

\sum_{n\ge 0} \frac{g(z)^n}{n!} = \exp g(z).</math>

In the labelled case we denote the operator by <math>\operatorname{{math|SET}</math>}, and in the unlabelled case, by <math>\operatorname{{math|MSET}</math>}. 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

:<math> F(z) = \exp \left( \sum_{l\ge 1} (-1)^{l-1} \frac{f(z^l)}{l} \right).</math>