Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. The explicit molecul ...
Conference paper

The explicit molecular expansion of the combinatorial logarithm

Gilbert Labelle (1)
(1) Laboratoire de combinatoire et d'informatique mathématique [Montréal]
Download article
Open on HAL
Imported on
November 20, 2016
Published on
December 31, 2012
Last modified on
April 1, 2025
Volume
DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)
Proceedings
DOI
10.46298/dmtcs.12818
License
https://about.hal.science/hal-authorisation-v1
Indicators
380
Views
457
Downloads

The explicit molecular expansion of the combinatorial logarithm

Gilbert Labelle (1)
(1) Laboratoire de combinatoire et d'informatique mathématique [Montréal]
Abstract
English
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.
French
Tout comme la série de puissances de $\log (1+X)$ est l’inverse substitutionnel analytique de la série de $\exp (X)-1$ l’espèce de structures (virtuelle) $\mathrm{Lg} (1+X)$, est l’inverse substitutionnel combinatoire de l’espèce, $E(X)-1$, des ensembles finis non vides. Ce $\textit{logarithme combinatoire}$, $\mathrm{Lg} (1+X)$ , a été introduit par A. Joyal en 1986 en faisant appel à un schéma itératif. Étant donnée une espèce $F(X)$ (telle que $F(0)=1$), l’une de ses principales applications est d’exprimer l’espèce, $F^{\mathrm{c}}(X)$, des $F$-structures $\textit{connexes}$ par la formule $F{\mathrm{c}} = \mathrm{Lg} (F) = \mathrm{Lg} (1+F_+)$ où $F_+$ désigne l’espèce des $F$-structures non vides. Depuis sa création, des descriptions équivalentes du logarithme combinatoire ont été formulés par d’autres combinatoriciens (G. L., I, Gessel, J. Li), mais sa décomposition exacte en composantes irréductibles (développement moléculaire) est demeurée obscure. Le but principal du présent travail est de combler cette lacune en calculant explicitement le développement moléculaire du logarithme combinatoire et de $-\mathrm{Lg}(1-X)$ un “cousin” de l’espèce tensorielle, $\mathrm{Lie}(X)$, des algèbres de Lie libres.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • combinatorial species
  • combinatorial logarithm
  • molecular expansion
  • generating functions
Preview
Loading PDF preview...