Discrete Mathematics & Theoretical Computer Science |
Just as the power series of $\log (1+X)$ is the analytical substitutional inverse of the series of $\exp (X)-1$, the (virtual) combinatorial species, $\mathrm{Lg} (1+X)$, is the combinatorial substitutional inverse of the combinatorial species, $E(X)-1$, of non-empty finite sets. This $\textit{combinatorial logarithm}$, $\mathrm{Lg} (1+X)$, has been introduced by A. Joyal in 1986 by making use of an iterative scheme. Given a species $F(X)$ (with $F(0)=1$), one of its main applications is to express the species, $F^{\mathrm{c}}(X)$, of $\textit{connected}$ $F$-structures through the formula $F{\mathrm{c}} = \mathrm{Lg} (F) = \mathrm{Lg} (1+F_+)$ where $F_+$ denotes the species of non-empty $F$-structures. Since its creation, equivalent descriptions of the combinatorial logarithm have been given by other combinatorialists (G. L., I. Gessel, J. Li), but its exact decomposition into irreducible components (molecular expansion) remained unclear. The main goal of the present work is to fill this gap by computing explicitly the molecular expansion of the combinatorial logarithm and of $-\mathrm{Lg}(1-X)$, a "cousin'' of the tensorial species, $\mathrm{Lie}(X)$, of free Lie algebras.