Combinatorial species

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

Combinatorial species is a simple, organized way to study discrete structures like graphs, trees, and permutations by focusing on their shape rather than their labels.

What a species is
- For every finite set A, a species F tells you the F-structures you can build on A, written F[A].
- If you relabel A with a bijection to another set B, you get a corresponding F-structure on B, written F[φ]: F[A] → F[B].
- In short, species are functors from finite sets with bijections to sets, so the same structure can be carried over to any equally sized set.

Generating functions
- From a species F, you get an exponential generating function F(x) = sum f_n x^n / n!, where f_n = |F[n]| and n-element sets behave the same for any A with n elements.
- Examples: the species of permutations, partitions, power sets, and graphs all have their own generating functions.

Basic operations and what they mean
- Addition (F + G): you get structures that are either F-type or G-type on the same base set. Generating function: F(x) + G(x).
- Multiplication (F · G): you split the base set into two disjoint parts, build an F-structure on one part and a G-structure on the other. Generating function: F(x) · G(x).
- Composition (F ∘ G): you split the base set into blocks, build a G-structure on each block, and then connect those blocks with an F-structure. Generating function: F(G(x)).
- Differentiation: adding a “hole” or a distinguished element. The pointed version F• satisfies F• = X · F′ and F•(x) = x F′(x). Pointing (F•[A] = A × F[A]) means choosing one element to mark.

Key examples
- Partitions P = E(E+): grouping A into nonempty blocks. P(x) = exp(exp(x) − 1) (the Bell numbers).
- Rooted trees Ar: Ar = X · E(Ar). A tree is a root plus a set of subtrees.
- Linear orders L: lists of elements. L′ = L · L and L(x) = 1/(1 − x).
- Cyclic permutations C: cycles on A. C′ = L, so C can be obtained by integrating L.
- Pointed structures F•: a distinguished element added to F[A], used as building blocks for more complex objects.
- Product to build bigger objects: F × G builds both an F-structure and a G-structure on the same base set. Generating function is (F × G)(x) = F(x) G(x). This helps describe objects like directed graphs built from simpler parts.

Why this matters
- These rules let us build and count complex structures from simpler ones, using familiar algebra on generating functions.
- The framework also supports advanced ideas like deeper differentiation, integration, and substitution, which reveal relationships between different kinds of structures.

Applications and tools
- SageMath and some Haskell packages support working with species.
- If you replace finite sets and bijections with finite vector spaces and linear maps, you get a related idea called polynomial functors.

In short, combinatorial species give a high-level, flexible way to describe, combine, and count discrete structures through elegant generating-function techniques.