A linear species is a functor

$$F : \mathrm{Lin} \to \mathrm{FinSet},$$

where $\mathrm{Lin}$ is the category of totally ordered sets and bijections and $\mathrm{FinSet}$ is the category of finite sets and functions.

The size of the values of $F$ on sets of a given size are recorded by a formal power series, eg. an ordinary generating function $f(z)=\sum_{n\geq 0}\left|{F[n]}\right|z^n$, or an exponential generating function $F(z)=\sum_{n\geq 0}\left|{F[n]}\right|\frac{z^n}{n!}$.

Given linear species $F$ and $G$ with $G[\emptyset]=\emptyset$, the substitution $F \circ G$ is the linear species which, for any totally ordered set $l$, produces a set $$(F\circ G)[l] = \coprod\limits_{\pi \in \mathrm{Par}[l]}{F[\pi] \times \prod\limits_{p \in \pi}{G[p]}},$$ where $\mathrm{Par}$ is the linear species of set partitions.

Moreover, if $F(z)$ and $G(z)$ are the e.g.f.s of $F$ and $G$, then $F(G(z))$ is the e.g.f. of $F\circ G$.

In analogy to the above, let's define the non-crossing substitution of $F$ and $G$ (when $G[\emptyset]=\emptyset$) as the linear species $F \diamond G$ which, for any totally ordered set $l$, $$(F\diamond G)[l] = \coprod\limits_{\pi \in \mathrm{NC}[l]}{F[\pi] \times \prod\limits_{p \in \pi}{G[p]}},$$ where $\mathrm{NC}$ is the linear species of non-crossing partitions.

A formula of Kreweras (1972) for the number of non-crossing partitions of a given type (an integer partition which records the sizes of the parts) implies

$$\left|{(F \diamond G)[n]}\right| = \sum\limits_{\mathrm{i} \in \mathcal{C}_n} \frac{1}{k}\binom{n}{k-1}f_k g_{i_1} \cdots g_{i_k},$$ where $\mathcal{C}_{n} = \{ (i_1, \ldots, i_k) : 1 \leq k \leq n, i_1 + \cdots + i_k = n \}$ is the set of compositions of $n$ into $k$ parts, $f_m = \left|{F[m]}\right|$ and $g_m = \left|{G[m]}\right|$.


Given generating functions (of some kind) for $F$ and $G$, is there a nice formula for the generating function of $F \diamond G$?

For the special case $F = \mathrm{Set}$ (the uniform species, which given $l$ produces $\{l\}$), David Callan (2008) showed that if $g(z)$ is the o.g.f. of $G$ and $h(z)$ the o.g.f. of $\mathrm{Set} \diamond G$,

$$h(z) = \frac{1}{z} \left( \frac{z}{1+g(z)} \right)^{\langle{-1}\rangle},$$

where $\langle -1 \rangle$ denotes the reversion of series.

For the general case, if $F(z)$ and $H(z)$ are the e.g.f.s of $F$ and $F \diamond G$, we could write

$$H(z) = \mathcal{L}^{-1} \left\{ \frac{ F \left( s g(z/s) \right) }{s^2} \right\}(1),$$ where $\mathcal{L}^{-1}$ is the inverse Laplace transform (evaluated at $t=1$).

(This follows from the formula of Kreweras since $\mathcal{L}^{-1}\left\{ \frac{s^{k-n}}{s^2}\right\}(1)=\frac{1}{(n-k+1)!}.)$

The last formula is not very nice, however, as although it allows the evaluation of $H$ for some limited choices of $F$ and $G$, the expression is intractable in basic examples we would hope to be easy, such as for $F = \mathrm{Set}$ and $G= \mathrm{Set_+}$ (so $F\diamond G = \mathrm{NC}$) (in this case the o.g.f. of $F \diamond G$ is the simpler one: it's the well known o.g.f. for the Catalan numbers, $\frac{1-\sqrt{1-4z}}{2z}$ (the corresponding e.g.f. is a combination of Bessel functions); this makes me suspect a better formula would give $h$ instead of $H$).


  • Kreweras, Germain. "Sur les partitions non croisées d'un cycle." Discrete Mathematics 1.4 (1972): 333-350.
  • Bergeron, François, Gilbert Labelle, and Pierre Leroux. Combinatorial species and tree-like structures. Vol. 67. Cambridge University Press, 1998.
  • Callan, David. "Sets, lists and noncrossing partitions." Journal of Integer Sequences 11.2 (2008): 3.
  • 3
    $\begingroup$ Exercise 5.35 of Enumerative Combinatorics, vol. 2, is relevant. $\endgroup$ – Richard Stanley Jun 27 '15 at 9:41

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.