An extension of the exponential formula in enumerative combinatorics

Gilbert Labelle ; Pierre Leroux

The electronic journal of combinatorics, The Foata Festschrift volume, Tome 3 (1996) no. 2

Résumé

Let $\alpha$ be a formal variable and $F_w$ be a weighted species of structures (class of structures closed under weight-preserving isomorphisms) of the form ${F}_{w} = E({F}_{w}^{c})$, where $E$ and $F_w^c$ respectively denote the species of sets and of connected $F_w$-structures. Multiplying by $\alpha$ the weight of each $F_w^c$-structure yields the species ${F}_{{w}^{( \alpha )}} = E({F}_{ \alpha w}^{c})$. We introduce a "universal" virtual weighted species, $\Lambda ^{(\alpha)}$, such that $F_{w^{(\alpha)}} = \Lambda^{( \alpha)}\, \circ \, F_w^+$, where $F_w^+$ denotes the species of non-empty $F_w$-structures. Using general properties of $\Lambda^{( \alpha)}$ , we compute the various enumerative power series $G(x)$, $\widetilde{G}(x)$, $\overline{G}(x)$, $G(x;q)$, $G\langle{x;q}\rangle$, ${Z}_{G}(x_1,x_2,x_3,\ldots)$, ${\Gamma }_{G}(x_1,x_2,x_3,\ldots)$, for $G = F_{w^{(\alpha)}}$, in terms of $F_w$. Special instances of our formulas include the exponential formula, ${F}_{{w}^{(\alpha )}}(x)=\exp(\alpha F_{w}(x))=({F}_{w}(x){)}^{\alpha }$, cyclotomic identities, and their $q$-analogues. The virtual weighted species, $\Lambda ^{(\alpha)}$, is, in fact, a new combinatorial lifting of the function ${(1+x)}^{\alpha }$.

Détail

DOI : 10.37236/1270

Classification : 05A15
Mots-clés : weighted species, structures, enumerative power series, exponential formula, cyclotomic identities