Combinatorial Species of a Generating Function

155 Views Asked by At

A combinatorial species has an associated exponential generating function, which counts the number of occurrences of labelled objects of that species, of a given size.

Table 1 on p409 of "Combinatorial Species and Tree-Like Structures" by Bergeron, Labelle, and Leroux gives a 'dictionary' relating species and generating functions (GF). For example, the species of Sets has GF $e^x$, the species of linear orders has GF $1/1-x$.

Species can be recursively constructed by composing elementary species in a variety of ways (e.g. Cartesian product, substitution etc).

Q. Given a GF $F(x)$, is there a computationally-efficient means of determining a corresponding species?

My understanding is that such determination may not be unique (for example, the species of permutations and of linear orders have the same GF).

EDIT (in response to @user43208's comment): The inverse mapping should ideally capture some notion of 'parsimony' w.r.t. the species it yields. For example, if the species is actually $1/(1 - e^x)$ (i.e. a composition of elementary species), this would ideally be the result given. This can be achieved inefficiently by a process of 'inverse dictionary substitution', but the question is concerned with the existence of a computationally-superior method.