Symbolic method (combinatorics): Difference between revisions

Revision as of 08:58, 23 February 2025

Revision as of 18:30, 22 March 2025

Line 26:

:<math>\frac{g(z)^n}{|G|}.</math>

We are able to enumerate filled slot configurations using either PET[[Pólya enumeration theorem]] in the unlabelled case or the labelled enumeration theorem in the labelled case. We now ask about the generating function of configurations obtained when there is more than one set of slots, with a permutation group acting on each. Clearly the orbits do not intersect and we may add the respective generating functions. Suppose, for example, that we want to enumerate unlabelled sequences of length two or three of some objects contained in a set ''X''. There are two sets of slots, the first one containing two slots, and the second one, three slots. The group acting on the first set is the full symmetric group <math>E_2S_2</math>, andwhich in symbolic combinatorics is traditionally denoted <math>E_2</math>. The group acting on the second slotset is, analogously, <math>S_3 = E_3</math>. We represent this by the following formal [[power series]] in ''X'':

:<math> X^2/E_2 \; + \; X^3/E_3 </math>

Line 36:

Clearly we can assign meaning to any such power series of quotients (orbits) with respect to permutation groups, where we restrict the groups of degree ''n'' to the conjugacy classes <math>\operatorname{Cl}(S_n)</math> of the symmetric group <math>S_n</math>, which form a unique factorization ___domain. (The orbits with respect to two groups from the same conjugacy class are isomorphic.) This motivates the following definition.

A class <math>\mathcal{C}\in \mathbb{N}[\mathfrak{AM}]</math> of combinatorial structures is a formal series

:<math>\mathcal{C} = \sum_{n \ge 1} \sum_{G\in \operatorname{Cl}(S_n)} c_G (X^n/G)</math>

where <math>\mathfrak{AM}</math> (the "AM" is for "atomsmolecules") is the set of primes of the UFD <math>\{\operatorname{Cl}(S_n)\}_{n\ge 1}</math> and <math>c_G \in \mathbb{N}.</math>

In the following we will simplify our notation a bit and write e.g.

Line 66:

This operator corresponds to the class

:<math>L = \frac{1}{1 - X} = 1 + E_1X + E_2X^2 + E_3X^3 + \cdots</math>

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

:<math> F(z) = 1 + \sum_{n\ge 1} Z(E_n1)(f(z), f(z^2), \ldots, f(z^n)) =

1 + \sum_{n\ge 1} f(z)^n = \frac{1}{1-f(z)}</math>

and

:<math> G(z) = 1 + \sum_{n\ge 1} \left(\frac{1}{|E_n|}\right) g(z)^n =

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

Line 82:

This operator corresponds to the class

:<math>C = C_1 + C_2 + C_3 + \cdots</math>

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

Line 125:

The series is

:<math>E = 1 + S_1E_1 + S_2E_2 + S_3E_3 + \cdots</math>

i.e., the symmetric group <math>S_n = E_n</math> is applied to the slots''n''th slot. 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.

The unlabelled case is done using the function

:<math>M(f(z), y) = \sum_{n\ge 0} y^n Z(S_nE_n)(f(z), f(z^2), \ldots, f(z^n))</math>

so that