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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.