Combinatorial Addition Formulas and Applications

AbstractWe derive addition formulas at the combinatorial level, that is, equations of the form F(X1+X2+⋯+Xk)=ΦF(X1,X2,…,Xk), where F=F(X) is a given combinatorial species and ΦF is a species on k sorts of singletons X1,X2,…,Xk, depending on F. General results are given in the case of a molecular species M=Xn/H. Specific formulas are also presented in the cases of the species Ln of n-lists, Chan of n-chains, En of n-sets, En± of oriented n-sets, Cn of (oriented) n-cycles, and Pn of n-gons (unoriented cycles). These formulas are useful for the computation of molecular expansions of species defined by functional equations. Applications to the computation of cycle index series and asymmetry index series, to the extension of substitution to virtual species (and K-species), and to the analysis of generalized binomial coefficients k for molecular species are also given.Nous obtenons des formules d'addition combinatoires, c'est-à-dire des équations de la forme F(X1+X2+⋯+Xk)=ΦF(X1,X2,…,Xk) où F=F(X) est une espèce de structures donnée et ΦF est une espèce, dépendant de F, sur k sortes de singletons X1,X2,…,Xk. Nous donnons des formules générales pour les espèces moléculaires M=Xn/H et des résultats plus spécifiques dans le cas des espèces Ln, des n-listes (listes de longueur n), Chan, des n-chaı̂nes, En, des n-ensembles, En±, des n-ensembles orientés, Cn, des n-cycles (orientés), et Pn, des n-gones (cycles non orientés). Ces formules sont utiles pour calculer le développement moléculaire d'espèces définies par des équations fonctionnelles. Nous présentons également des applications au calcul des séries indicatrices des cycles ou d'asymétrie, à l'extension de la substitution aux espèces virtuelles (et aux K-espèces), et à l'analyse des coefficients binomiaux généralisés k pour les espèces moléculaires