×

An extension of the exponential formula in enumerative combinatorics. (English) Zbl 0856.05003

Electron. J. Comb. 3, No. 2, Research paper R12, 14 p. (1996); printed version J. Comb. 3, No. 2, 269-282 (1996).
From the authors’ abstract: 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^c_w)\), where \(E\) and \(F^c_w\) respectively denote the species of sets and of connected \(F_w\)-structures. Multiplying by \(\alpha\) the weight of each \(F^c_w\)-structure yields the species \(F_{w^{(\alpha)}} = E (F^c_{\alpha w})\). We introduce a ‘universal’ virtual weighted species, \(\bigwedge^{(\alpha)}\), such that \(F_{w^{(\alpha)}} = \bigwedge^{(\alpha)} \circ F^+_w\), where \(F^+_w\) denotes the species of non-empty \(F_w\)-structures. Using general properties of \(\bigwedge^{(\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, \dots)\), \(\Gamma_G (x_1, x_2, x_3, \dots)\), 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\)-analogous. The virtual weighted species, \(\bigwedge^{(\alpha)}\), is, in fact, a new combinatorial lifting of the function \((1 + x)^\alpha\).

MSC:

05A15 Exact enumeration problems, generating functions
Full Text: EuDML EMIS