Combinatorial Species - Types and Unlabelled Structures

Types and Unlabelled Structures

Instead of counting all the possible structures that can be built on some set, we often want to count only the number of different "shapes" of structure. Consider the set of rooted trees on the set A = {a, b, c}. There are nine of these, which can be grouped into two classes by tree shape. There are:

• Six trees with three levels:
  1. a → b → c
  2. a → c → b
  3. b → a → c
  4. b → c → a
  5. c → a → b
  6. c → b → a
• Three trees with two levels: (not six, because subtrees are not in any order)
  1. b ← a → c
  2. a ← b → c
  3. a ← c → b

There is an exact correspondence between trees in the first class and permutations of A. Any of these trees can be constructed from any of the others, by permuting the labels on its nodes. For any two trees s and t in this class, there is some permutation σ in the symmetric group S_A which acts on s to give t: Ar(s) = t. The same holds for the second class of trees. This property can be used to define an equivalence relation on Ar, dividing it into the two parts listed above. These equivalence classes are the isomorphism types of Ar-structures of order 3.

Formally, when F is a species, we define T(F_n) to be the quotient set F/~ of types of F-structures of order n, where "~" is the relation "s ~ t if and only if there is some σ in S_n such that F(s) = t". As with the exponential generating functions, the size of T(F_n) depends only on the value of n and the definition of F. It is the set of unlabelled F-structures on any set of size n.

The isomorphism type generating series of F is:

Manipulations of these functions are done in essentially the same way as for the exponential generating functions. There are a few differences in how some of the operations translate into operations on type generating series. Addition and multiplication work as expected, but the more complicated operations need some more sophisticated mathematical tools for their proper definitions.

There is a much more general series, called the cycle index series, for each species, which contains all the information in the previously-defined series, and more. Any permutation σ of a finite set A with n elements can be decomposed, uniquely, into a product of disjoint cycles. Letting σ_i be the number of cycles of length i in the decomposition of σ ∈ S_n, the cycle type of σ is defined to be the sequence (σ₁, σ₂, ..., σ_n). Now let Fix(σ) be the set of elements fixed by σ — that is, the elements x of A where σ(x) = x. Then the cycle index series of F is:

|Fix(F)| is the number of F-structures on A = {1, ..., n} for which σ is an automorphism.

It follows immediately that

and

for any species F. The cycle index series follows these rules for combinatorial operations on species F and G:

Then the rules for type generating series can be given in terms of these: