An Extension of the Exponential Formula in Enumerative Combinatorics.pdf

An Extension of the Exponential Formulain Enumerative CombinatoricsGilbert Labelle and Pierre LerouxLACIM, Dep. de mathematiques, Universite du Quebec a MontrealC.P. 8888, Succ. Centre-Ville, Montreal (Quebec), Canada H3C 3P8Submitted: March 11, 1995; Accepted: July 15, 1995En hommage a Dominique Foata, a loccasion de son soixantieme anniversaire.AbstractLet  be a formal variable and Fw be a weighted species of structures (class of structures closedunder weight-preserving isomorphisms) of the form Fw = E(F cw), where E and F cw respectivelydenote the species of sets and of connected Fw-structures. Multiplying by  the weight of each F cw-structure yields the species Fw() = E(F cw). We introduce a \universal virtual weighted species,(), such that Fw() = ()  F+w , where F+w denotes the species of non-empty Fw-structures.Using general properties of () , we compute the various enumerative power series G(x), eG(x),G(x), G(x; q), Ghx; qi, ZG(x1; x2; x3; : : :), G(x1; x2; x3; : : :), for G = Fw() , in terms of Fw. Specialinstances of our formulas include the exponential formula, Fw()(x) = exp(Fw(x)) = (Fw(x)),cyclotomic identities, and their q-analogues. The virtual weighted species, (), is, in fact, a newcombinatorial lifting of the function (1 + x).ResumeSoit  une variable formelle et Fw une espece de structures ponderee (classe de structuresfermee sous les isomorphismes preservant les poids) de la forme Fw = E(F cw), ou E et F cw designentrespectivement lespece des ensembles et celle des Fw-structures connexes. En multipliant par  lepoids de chaque F cw-structure, on obtient lespece Fw() = E(F cw). Nous introduisons une especevirtuelle \universelle, (), telle que Fw() = ()  F+w , ou F+w designe lespece des Fw-structuresnon-vides. En faisant appel a des proprietes generales de (), nous calculons les diverses seriesformelles enumeratives G(x), eG(x), G(x), G(x; q), Ghx; qi, ZG(x1; x2; x3; : : :), G(x1; x2;