Combinatorial species

Remarks

The exponential generating function of $F$ is $F(x) = \sum_{n \ge 0} \abs{F[\set{1, \ldots, n}]}\, \frac{x^n}{n!}$.

Example: the species $L$ of linear orders assigns to $U$ the set of total orders on $U$. A bijection $\sigma$ transports an order $u_1 < \cdots < u_n$ to $\sigma(u_1) < \cdots < \sigma(u_n)$, and the functor rules hold. Since $\abs{L[\set{1, \ldots, n}]} = n!$, its generating function is $\frac{1}{1 - x}$. The species $E$ of sets, with $E[U] = \set{U}$, has generating function $e^x$.

Non-example: let $F[U] = \set{U}$ if $U \subseteq \N$ and $F[U] = \emptyset$ otherwise. For a bijection $\sigma$ from $\set{1}$ to $\set{a}$ with $a \notin \N$, clause 2 needs a bijection from a one-element set to the empty set, which does not exist. So $F$ is not a species.

Sum, product, composition and derivative of species correspond to the same operations on exponential generating functions. Some authors let $F$ take values in the category of finite sets and all functions; this gives the same notion, since a functor sends bijections to bijections.