Symbolic method (combinatorics): Difference between revisions

Revision as of 19:54, 31 January 2016

Revision as of 05:53, 15 July 2017

Line 8:

The [[Pólya enumeration theorem]] solves this problem in the unlabelled case. Let ''f''(''z'') be the [[ordinary generating function]] (OGF) of the objects, then the OGF of the configurations is given by the substituted [[cycle index]]

:<math>Z(G)(f(z), f(z^2), \ldots, f(z^n)).\,</math>

In the labelled case we use an [[exponential generating function]] (EGF) ''g''(''z'') of the objects and apply the [[Labelled enumeration theorem]], which says that the EGF of the configurations is given by

Line 54:

This operator corresponds to the class

:<math>1 + E_1 + E_2 + E_3 + \cdots\,</math>

and represents sequences, i.e. the slots are not being permuted and there is exactly one empty sequence. We have

Line 70:

This operator corresponds to the class

:<math>C_1 + C_2 + C_3 + \cdots\,</math>

i.e., cycles containing at least one object. We have

Line 93:

The labelled even cycle operator <math>\mathfrak{C}_{\operatorname{even}}</math> is

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

which yields

Line 113:

The series is

:<math>1 + S_1 + S_2 + S_3 + \cdots\,</math>

i.e., the symmetric group is applied to the slots. This creates multisets in the unlabelled case and sets in the labelled case (there are no multisets in the labelled case because the labels distinguish multiple instances of the same object from the set being put into different slots). We include the empty set in both the labelled and the unlabelled case.

Line 123:

so that

:<math>\mathfrak{M}(f(z)) = M(f(z), 1).\,</math>

Evaluating <math>M(f(z), 1)</math> we obtain

Line 227:

|-

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

Line 233:

|-

|<math>\mathcal{A} = \mathcal{B} \circ \mathcal{C}</math>

|<math>A(z) = B(C(z))\,</math>

|}

Line 297:

This ''binomial convolution'' relation for the terms is equivalent to multiplying the EGFs,

:<math>A(z) \cdot B(z).\,</math>

===Sequence===