Combinatorial species

So what is a species?

Formally, a species is a functor from the category $N$ of finite sets to itself, where the morphisms in $N$ are bijections of sets.

Less formally, a species $S$ is an assignment, for each $n\ge 0$, of the set $[n]=\{1,2,\ldots,n\}$ to a finite set $S([n])$, along with a rule for “relabeling.” The relabeling rule then determines a unique finite set $S(A)$ for any given finite set $A$.

For instance, we can define the “species of cyclic permutations” $C$ by $$C([n])=\{\text{cyclic permutations of }1,2,\ldots,n\}.$$ Then for any $A=\{a_1,\ldots,a_n\}$ and any bijection $\phi:[n]\to A$, we have $$C(A)=\{\text{cyclic permutations of }a_1,a_2,\ldots,a_n\},$$ and there is a natural bijection $C([n])\to C(A)$ given by re-labeling the permutations according to $\phi$.

Species serve as an excellent organizational tool for manipulating generating functions. The exponential generating function of a species $S$ is the function $$\widetilde{S}(x)=\sum_{n=0}^\infty \frac{|S([n])|}{n!}x^n.$$ Recall that we can add, multiply, and sometimes compose exponential generating functions, and it is useful to define corresponding operations on species:

Addition of species: Given two species $S,T$, we define the species $S+T$ by $$(S+T)([n])=S([n])\sqcup T([n]),$$ with the relabeling rule naturally inherited from $S$ and $T$. It is easy to see that this corresponds to addition of exponential generating functions: $\widetilde{S+T}=\widetilde{S}+\widetilde{T}$.

Example: Let $E$ be the species of even permutations and $O$ the species of odd permutations. Let $P$ be the species of all permutations. Then $E+O=P$.

Multiplication of species: Given species $S$ and $T$, we define the species $S\cdot T$ as follows:
$(S\cdot T)([n])$ is the set of tuples $(A_1,A_2,\alpha,\beta)$ where $A_1$ and $A_2$ form a partition of $[n]$, and $\alpha\in S(A_1)$ and $\beta\in S(A_2)$. We also have $\widetilde{S\cdot T}=\widetilde{S}\cdot \widetilde{T}$.

Example: Every permutation can be decomposed into a product of even cycles and odd cycles, so if $A$
is the species of permutations having only even cycles and $B$ is the species of permutations having only odd cycles, then $A\cdot B=P$.

Composition of species: Given species $S$ and $T$ with $T(\emptyset)=\emptyset$, we define
$(S\odot T)([n])$ to be the set of tuples $(A_1,\ldots,A_k,\alpha_1,\ldots \alpha_k,\beta)$ where $A_1,\ldots,A_k$ form a partition of $[n]$, each $\alpha_i\in T(A_i)$, and $\beta\in S(\{A_1,\ldots, A_k\})$. This corresponds to composition of exponential generating functions: $\widetilde{S\odot T}=\widetilde{S}\circ \widetilde{T}$, which is only well-defined when $\widetilde{T}(0)=0$.

Example: Permutations can be uniquely written as a union of disjoint cycles. Each of the cycles has a $C$-structure and the cycles themselves have the trivial structure, so if $E$ is the “trivial species” sending each $[n]$ to $\{1\}$, then $E\odot C=P$.

3 thoughts on “Combinatorial species

  1. Excellent post, brings back great memories! I had the extraordinary privilege of meeting and interacting with some of the founders and early proponents of the theory – Andre Joyal (a truly fascinating character), Pierre Leroux (who unfortunately passed away in 2008), the Labelle brothers (one of whom also happens to be a brilliant chess player) and Francois Bergeron (a polymath in the best sense of the word). They definitely played a major role in my decision to go into mathematics research. I’m sure the rest of your quals went well after such an inspiring start 🙂

    • Oh wow! I’ve never met the people you mentioned myself – I learned about species from Mark Haiman last year.

      The exam did go pretty well after that. The algebraic geometry section gave me some trouble, but overall it was a fun exam. 🙂

  2. Hi,
    While searching for a proof, I fell on the disimmetry theorem – which is another mind blowing argument – and here is my comment.

    Take for example, a necklace o-o-o-o-o-o. It has a “canonical” middle edge and two canonical ends that could be depicted by: x-o-o—o-o-x. These particular specifications are critical for the proof. Meanwhile, the associated species is E2(X.X.X).

    This species has no middles, no ends and no edges. The only thing that the above combinatorial species has is the permutation group of order two and degree six, generated by (1 2) (3 4) (5 6).

    Similarly, once written the species relation R = X.C(T), the trees as we knew them are not anymore there…

    Lovely article,
    Best regards

Leave a Reply

Your email address will not be published. Required fields are marked *