An Extension of the Exponential Formula in Enumerative Combinatorics

Gilbert Labelle and Pierre Leroux LACIM, Dép. de mathématiques, Université du Québec à Montréal C.P. 8888, Succ. Centre-Ville, Montréal (Québec), Canada H3C 3P8

Submitted: March 11, 1995; Accepted: July 15, 1995

En hommage à Dominique Foata, à l’occasion de son soixantième anniversaire.

Abstract

Let α 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_{w}^{c}), where E and F_{w}^{c} respectively denote the species of sets and of connected F_{w}-structures. Multiplying by α the weight of each F_{w}^{c}- structure yields the species F_{w^{(α)}} = E(F_{αw}^{c}). We introduce a “universal” virtual weighted species, Λ^{(α)}, such that F_{w^{(α)}} = Λ^{(α)} ∘ F_{w}^{+}, where F_{w}^{+} denotes the species of non-empty F_{w}-structures. Using general properties of Λ^{(α)} , we compute the various enumerative power series G(x), G̃(x), \overline{G}(x), G(x; q), G⟨x; q⟩, Z_{G}(x_{1}, x_{2}, x_{3}, …), Γ_{G}(x_{1}, x_{2}, x_{3}, …), for G = F_{w^{(α)}}, in terms of F_{w}. Special instances of our formulas include the exponential formula, F_{w^{(α)}}(x) = exp(αF_{w}(x)) = (F_{w}(x))^{α}, cyclotomic identities, and their q-analogues. The virtual weighted species, Λ^{(α)}, is, in fact, a new combinatorial lifting of the function (1 + x)^{α}.

Résumé

Soit α une variable formelle et F_{w} une espèce de structures pondérée (classe de structures fermée sous les isomorphismes préservant les poids) de la forme F_{w} = E(F_{w}^{c}), où E et F_{w}^{c} désignent respectivement l’espèce des ensembles et celle des F_{w}-structures connexes. En multipliant par α le poids de chaque F_{w}^{c}-structure, on obtient l’espèce F_{w^{(α)}} = E(F_{αw}^{c}). Nous introduisons une espèce virtuelle “universelle”, Λ^{(α)}, telle que F_{w^{(α)}} = Λ^{(α)} ∘ F_{w}^{+}, où F_{w}^{+} désigne l’espèce des F_{w}-structures non-vides. En faisant appel à des propriétés générales de Λ^{(α)}, nous calculons les diverses séries formelles énumératives G(x), G̃(x), \overline{G}(x), G(x; q), G⟨x; q⟩, Z_{G}(x_{1}, x_{2}, x_{3}, …), Γ_{G}(x_{1}, x_{2}, x_{3}, …), de G = F_{w^{(α)}}, en fonction de F_{w}. Comme cas spéciaux des formules que nous développons, on retrouve la formule exponentielle, F_{w^{(α)}}(x) = exp(αF_{w}(x)) = (F_{w}(x))^{α}, les identités cyclotomiques, ainsi que leurs q-analogues. L’espèce virtuelle pondérée, Λ^{(α)}, est, en fait, un nouveau relèvement combinatoire de la fonction (1 + x)^{α}.

1 Introduction

Let f(x) and g(x) be two functions or formal power series such that

f(x) = exp(g(x)).  (1)

The expression f(x)^{α} can then be given a meaning, for any variable α, by means of the “exponential formula”

f(x)^{α} = exp(α g(x)).  (2)

[figure: a; c; i; d; e; f; p; k; n; h; q; b; r; m; j]
Figure 1: A graph g with w(g) = y^{11} and w^{(α)}(g) = α^{5}y^{11}

D. Foata played a pioneer role in the interpretation and use of these formulas in enumerative combinatorics; see for example [3], [12], [16]. Essentially, if f(x) and g(x) are the exponential generating series for the structure classes F and G, then equation (1) expresses the fact that the F -structures can be identified with assemblies of G-structures, the latter being considered as “connected” F -structures. In that case, the “weight” α^{c(s)} can be assigned to any F -structure s, where c(s) denotes the number of “connected components” of s; one says that the variable α acts as a counter for (or marks) the connected components. Formula (2) then gives the exponential generating series of this new weighted class. For example, it is immediately seen that the function (1 − x)^{−α} is the generating series for permutations, where α acts as a cycle counter. This approach is fundamental in the development of combinatorial models for the classical orthogonal polynomials; see, for example, [13]–[15], [17].

In the following, we consider weighted structure classes (called species, see [2], [19], [24]) that are closed under isomorphisms induced by relabellings, that is, by bijections of the underlying sets. In that case, new generating series, symmetric functions (cycle index series), and q-analogues can be associated, in relation with the enumeration of unlabelled (i.e., up to isomorphism) or asymmetric (i.e., whose automorphism group is reduced to the identity) structures. When moreover the concept of connected components can be introduced, there arises the question of determining the relations analogous to (2) for these various series. As we will see, more complex exponential formulas appear, involving polynomials in α related to the classical “cyclotomic identity” and to a new “cocyclotomic identity” (see Corollary 2.3).

Let us illustrate our approach with the species Gr_{w} of (simple) graphs, weighted by an edge counter, y. For instance, the graph g of Figure 1 has weight w(g) = y^{11} since it has 11 edges. Note that this weighting is invariant under relabellings and multiplicative with respect to the natural concept of connected components, in the sense that the weight of a graph is equal to the product of the weights of its components. These facts are summarized by the equation Gr_{w} = E(Gr_{w}^{c}), where E denotes the species of sets and Gr^{c} denotes the connected graphs. Now the weight w can be refined to a new weight w^{(α)} by adjoining a counter α of connected components. Hence the previous graph g has a refined weight w^{(α)}(g) = α^{5}y^{11} (see Figure 1). This refinement w ↦ w^{(α)} transforms the species Gr_{w} of graphs weighted by the number of edges into the species Gr_{w^{(α)}} of graphs weighted by the numbers of edges and of connected components. Since any graph is an assembly of connected graphs, the transformation can be described as

Gr_{w} = E(Gr_{w}^{c}) ↦ Gr_{w^{(α)}} = E(Gr_{αw}^{c}),  (3)

where αw expresses that the weight w of any connected component is multiplied by α.

It is clear that the transformation (3) can be extended to any weighted species F_{w}, of the form F_{w} = E(F_{w}^{c}), where F_{w}^{c} denotes the species of connected F_{w}-structures:

F_{w} = E(F_{w}^{c}) ↦ F_{w^{(α)}} = E(F_{αw}^{c}),  (4)

Our goal is to analyse the general transformation F_{w} ↦ F_{w^{(α)}} and to deduce a number of enumerative results. We show, in section 2, that there exists a “universal” virtual (i.e., formal difference of species, see [2], [20], [36]) weighted species, Λ^{(α)}, such that

F_{w^{(α)}} = Λ^{(α)} ∘ F_{w}^{+},  (5)

where F_{w}^{+} = F_{w} − 1 denotes the species of non-empty F_{w}-structures, and we compute the main enumerative series associated with Λ^{(α)}. From this follows an explicit general form for the series G(x), G̃(x), \overline{G}(x), G(x; q), G⟨x; q⟩, Z_{G}(x_{1}, x_{2}, x_{3}, …), Γ_{G}(x_{1}, x_{2}, x_{3}, …), associated with the species G = F_{w^{(α)}}, in terms of the series associated with the species F_{w}. In section 3, we give a number of identities (and q-identities) which follow for some particular choices of species F_{w}. We conclude, in section 4, with an analysis of the species Λ^{(α)}. In particular, we give the first terms of the molecular decomposition of Λ^{(α)} which constitutes a new combinatorial lifting of the binomial formula for a formal exponent α:

(1 + x)^{α} = 1 + α x + α(α − 1) \frac{x^{2}}{2!} + α(α − 1)(α − 2) \frac{x^{3}}{3!} + α(α − 1)(α − 2)(α − 3) \frac{x^{4}}{4!} + · · · . (6)

2 The transformation F_{w} ↦ F_{w^{(α)}}

Many formal power series can be assigned to a weighted species F = F_{w}. The two main ones, Z_{F} and Γ_{F} are called respectively the cycle index series of F (see [19]) and the asymmetry index series of F (see [23]–[25]). They are power series in an infinity of variables x_{1}, x_{2}, x_{3}, …:

Z_{F} (x_{1}, x_{2}, x_{3}, …) = ∑_{n=0}^{∞} \frac{1}{n!} ∑_{σ∈S_{n}} f_{σ} x_{1}^{σ_{1}}x_{2}^{σ_{2}}x_{3}^{σ_{3}} ⋯,  (7)

Γ_{F} (x_{1}, x_{2}, x_{3}, …) = ∑_{n=0}^{∞} \frac{1}{n!} ∑_{σ∈S_{n}} f_{σ}^{∗} x_{1}^{σ_{1}}x_{2}^{σ_{2}}x_{3}^{σ_{3}} · · · .  (8)

In these formulas, the coeficients f_{σ} (resp. f_{σ}^{∗}) are ℕ-linear (resp. ℤ-linear) combinations of the weights given to the F -structures on [n] = {1, 2, …, n}, S_{n} is the symmetric group of degree n and σ_{k} denotes the number of cycles of length k in the cyclic decomposition of any permutation σ ∈ S_{n}. In fact, Z_{F} and Γ_{F} can be seen as symmetric functions of auxiliary variables ξ_{1}, ξ_{2}, ξ_{3}, …, by making the substitutions

x_{i} := p_{i}(ξ_{1}, ξ_{2}, ξ_{3}, …) = ξ_{1}^{i} + ξ_{2}^{i} + ξ_{3}^{i} + ⋯, i ≥ 1 (power sums).  (9)

Other specializations of the variables x_{1}, x_{2}, x_{3}, …, in the series (7)–(8) give (see [19], [23])

Z_{F} (x, 0, 0, …) = Γ_{F} (x, 0, 0, …) = F (x) = ∑_{n≥0} f_{n} \frac{x^{n}}{n!} ,  (10)

Z_{F} (x, x^{2}, x^{3}, …) = F̃(x) = ∑_{n≥0} f̃_{n}x^{n},  (11)

Γ_{F} (x, x^{2}, x^{3}, …) = \overline{F} (x) = ∑_{n≥0} \overline{f}_{n}x^{n},  (12)

where

f_{n} = total weight of the F_{w}-structures on [n] = {1, 2, …, n},  (13)
f̃_{n} = total weight of the unlabelled F_{w}-structures on n points,  (14)
\overline{f}_{n} = total weight of the unlabelled asymmetric F_{w}-structures on n points.  (15)

Of course, when the weighting w is trivial (i.e., w = 1 for any structure), then the total weights (13)

– (15) give the numbers of corresponding structures.

Finally, two q-series F (x; q) and F ⟨x; q⟩ can be canonically associated to the species F (see [7]–[9]) by setting

F (x; q) = ∑_{n=0}^{∞} f_{n}(q)\frac{x^{n}}{n!_{q}} = Z_{F} (\frac{(1 − q)}{(1 − q)}x, \frac{(1 − q)^{2}}{(1 − q^{2})}x^{2}, \frac{(1 − q)^{3}}{(1 − q^{3})}x^{3}, …) ,  (16)

F ⟨x; q⟩ = ∑_{n=0}^{∞} f_{n} ⟨q⟩ \frac{x^{n}}{n!_{q}} = Γ_{F} (\frac{(1 − q)}{(1 − q)}x, \frac{(1 − q)^{2}}{(1 − q^{2})}x^{2}, \frac{(1 − q)^{3}}{(1 − q^{3})}x^{3}, …) ,  (17)

where

n!_{q} = \frac{(1 − q)}{(1 − q)} · \frac{(1 − q^{2})}{(1 − q)} · \frac{(1 − q^{3})}{(1 − q)} ⋯ \frac{(1 − q^{n})}{(1 − q)}  (18)

denotes the q-analogue of n! (n! = lim_{q→1} n!_{q}). These q-series satisfy the following properties:

lim_{q→1} F (x; q) = F (x),  lim_{q→0} F (x; q) = F̃(x).  (19)
lim_{q→1} F ⟨x; q⟩ = F (x),  lim_{q→0} F ⟨x; q⟩ = \overline{F} (x).  (20)

Moreover their coefficients, f_{n}(q) and f_{n} ⟨q⟩, are polynomials in q of degree ≤ n(n − 1)/2. For F = E, the species of sets, the q-series (16) and (17) take the form of the two classical q-analogues of the exponential function:

E(x; q) = ∑_{n=0}^{∞} \frac{x^{n}}{n!_{q}} = \frac{1}{(1 − (1 − q)x)(1 − (1 − q)qx)(1 − (1 − q)q^{2}x) ⋯} ,  (21)

E⟨x; q⟩ = ∑_{n=0}^{∞} q^{n(n−1)/2} \frac{x^{n}}{n!_{q}} = (1 + (1 − q)x)(1 + (1 − q)qx)(1 + (1 − q)q^{2}x) · · · .  (22)

The definition of the series Z_{F}, Γ_{F}, F (x), F̃(x), \overline{F} (x), F (x; q), F ⟨x; q⟩, can be extended to any virtual weighted species F = F_{w} = A_{u} − B_{v}, where A_{u} and B_{v} are two weighted species, by setting Z_{F} = Z_{A_{u}} − Z_{B_{v}}, Γ_{F} = Γ_{A_{u}} − Γ_{B_{v}}, and so on.

The transformations F ↦ Z_{F} and F ↦ Γ_{F}, from species to index series, have the remarkable property of preserving the main combinatorial operations ([19], [23]): for any (virtual weighted) species F and G, one has

Z_{F +G} = Z_{F} + Z_{G} ,  Γ_{F +G} = Γ_{F} + Γ_{G} ,  (23)

Z_{F ·G} = Z_{F} · Z_{G} ,  Γ_{F ·G} = Γ_{F} · Γ_{G} ,  (24)
Z_{F ∘G} = Z_{F} ∘ Z_{G} ,  Γ_{F ∘G} = Γ_{F} ∘ Γ_{G} ,  (25)
Z_{F′} = \frac{∂Z_{F}}{∂x_{1}} ,  Γ_{F′} = \frac{∂Γ_{F}}{∂x_{1}} ,  (26)

In the right hand sides of (25), the operation used is the plethystic substitution of index series. It is defined, for two arbitrary index series f_{w}(x_{1}, x_{2}, x_{3}, …) and g_{v}(x_{1}, x_{2}, x_{3}, …), with g_{v}(0, 0, 0, …) = 0, arising from weighted virtual species F_{w} and G_{v}, by

(f_{w} ∘ g_{v})(x_{1}, x_{2}, x_{3}, …) = f_{w}((g_{v})_{1}, (g_{v})_{2}, (g_{v})_{3}, …) ,  (27)

where (g_{v})_{k} := g_{v^{k}}(x_{k}, x_{2k}, x_{3k}, …) denotes the index series obtained by raising to the power k any weight appearing in g_{v}(x_{1}, x_{2}, x_{3}, …) and by multiplying the index of any variable by k. The following general principle follows immediately from the equations (23)–(26):

Principle 2.1 Any combinatorial equation (that is, a natural isomorphism, see [2]) between species F, G, H, … gives rise—automatically—to seven corresponding equations between the series

F (x), G(x), H(x), …,
Z_{F} , Z_{G}, Z_{H}, …, F̃(x), G̃(x), H̃(x), …, F (x; q), G(x; q), H(x; q), …,  (28)
Γ_{F} , Γ_{G}, Γ_{H}, …, \overline{F} (x), \overline{G}(x), \overline{H}(x), …, F ⟨x; q⟩, G⟨x; q⟩, H⟨x; q⟩, ….

Here is the main result of this article.

Theorem 2.2 There exists a “universal” virtual weighted species, Λ^{(α)}, such that for any species of the form F_{w} = E(F_{w}^{c}), we have

F_{w^{(α)}} = Λ^{(α)} ∘ F_{w}^{+},  (29)

where F_{w}^{+} = F_{w} − 1 denotes the species of non-empty F_{w}-structures and F_{w^{(α)}} = E(F_{αw}^{c}) denotes the species of F_{w}-structures with the adjunction to the weight of a counter α of connected components. The main series associated to Λ^{(α)} are given by the formulas

Λ^{(α)}(x) = (1 + x)^{α},
Z_{Λ^{(α)}} = ∏_{n≥1}(1 + x_{n})^{λ_{n}(α)}, Λ̃^{(α)}(x) = ∏_{n≥1}(1 + x^{n})^{λ_{n}(α)}, Λ^{(α)}(x; q) = ∏_{n≥1} (1 + \frac{(1 − q)^{n}}{(1 − q^{n})} x^{n})^{λ_{n}(α)} (30)

Γ_{Λ^{(α)}} = ∏_{n≥1}(1 + x_{n})^{γ_{n}(α)}, \overline{Λ^{(α)}}(x) = ∏_{n≥1}(1 + x^{n})^{γ_{n}(α)}, Λ^{(α)}⟨x; q⟩ = ∏_{n≥1} (1 + \frac{(1 − q)^{n}}{(1 − q^{n})} x^{n})^{γ_{n}(α)},

where the exponents λ_{n}(α) and γ_{n}(α) are polynomials of degree n in α defined by

λ_{n}(α) = \frac{1}{n} ∑_{d|n} μ(n/d)α^{d},  (31)
γ_{n}(α) = −λ_{n}(−α) − λ_{n/2}(−α) − λ_{n/4}(−α) − ⋯ − λ_{n/2^{k}}(−α) − · · · .  (32)

In (31), μ denotes the classical Möbius function and in (32), the sum ranges over all integers k ≥ 0 for which n/2^{k} is an integer.

Before proving Theorem 2.2, observe that when α is a positive integer, λ_{n}(α) , given by (31), is equal to the number of primitive circular words (Lyndon words) of length n over an alphabet of α letters (c.f. [29]). It also represents the number of irreducible unitary polynomials of degree n over the finite field F_{q} of cardinality q, when α = q (c.f. [11], [31]). The polynomials (31) are known as Lyndon polynomials (see [34]) and also as (primitive) necklace polynomials (see [30]). Finally, note that formula (29) permits the extension of the transformation F_{w} ↦ F_{w^{(α)}} to all the weighted species F_{w} for which F_{w}(0) = 1. Indeed, it suffices to substitute F_{w}^{+} = F_{w} − 1 into Λ^{(α)}. The species F_{w} can even be virtual. In fact, as long as F_{w}(0) = 1, a concept of connected components can be defined (see (34) below) and the associated series can be computed (see [2], [20], [22], [25]).

Proof of Theorem 2.2. Consider the species X_{α} of singletons of weight α and E^{+} = E − 1, of non-empty sets. A. Joyal [20] has shown that the species E^{+} possesses an inverse (E^{+})^{<−1>} under substitution, given by the formula

(E^{+})^{<−1>} = X − ΔX + Δ^{2}X − Δ^{3}X + ⋯,  (33)

where X is the species of singletons (of weight 1) and Δ is the combinatorial difference operator defined by ΔG = G ∘ E^{+} − G, for any (virtual) species G. Since F_{w} = E(F_{w}^{c}) = 1 + E^{+}(F_{w}^{c}), we get F_{w}^{+} = F_{w} − 1 = E^{+}(F_{w}^{c}), whence

F_{w}^{c} = (E^{+})^{<−1>} ∘ F_{w}^{+}.  (34)

Let us define Λ^{(α)} by the formula

Λ^{(α)} := E ∘ X_{α} ∘ (E^{+})^{<−1>}.  (35)

A short computation, based on (33), gives the first few terms of the molecular expansion of Λ^{(α)} (see also Section 4):

Λ^{(α)} = 1 + X_{α} + (E_{2})_{α^{2}} − (E_{2})_{α} + ⋯,  (36)

where (E_{2})_{α} and (E_{2})_{α^{2}} denote the species of sets of cardinality 2 weighted by α and by α^{2}, respectively. This shows that Λ^{(α)} is a virtual weighted species. We then have successively

F_{w^{(α)}} = E(F_{α w}^{c}) = E ∘ X_{α} ∘ F_{w}^{c} = E ∘ X_{α} ∘ (E^{+})^{<−1>} ∘ F_{w}^{+} = Λ^{(α)} ∘ F_{w}^{+}  (37)

which gives (29). By taking the generating series of both sides of (35), we get

Λ^{(α)}(x) = e^{α log(1+x)} = (1 + x)^{α}.  (38)

The explicit formula for the cycle index series Z_{Λ^{(α)}} is obtained by substituting the known expressions (see [19], [20], [22])

Z_{E} = exp(∑_{n≥1} x_{n}/n) ,  Z_{(E^{+})^{<−1>}} = ∑_{n=1}^{∞} \frac{μ(n)}{n} log(1 + x_{n})  (39)

in the formula Z_{Λ^{(α)}} = Z_{E∘X_{α}∘(E^{+})^{<−1>}} = (Z_{E}) ∘ (αx_{1}) ∘ (Z_{(E^{+})^{<−1>}}). The explicit computation of the asymmetry index series Γ_{Λ^{(α)}} = Γ_{E∘X_{α}∘(E^{+})^{<−1>}} = (Γ_{E}) ∘ (αx_{1}) ∘ (Γ_{(E^{+})^{<−1>}}) is more delicate. It is known [23] that

Γ_{E} = exp(∑_{n≥1}(−1)^{n−1}x_{n}/n)  (40)

and we must determine Θ := Γ_{(E^{+})^{<−1>}}. Since E ∘ (E^{+})^{<−1>} = 1 + E^{+} ∘ (E^{+})^{<−1>} = 1 + X, we have Γ_{E} ∘ Θ = 1 + x_{1} . Substituting Θ in both sides of (40) and taking logarithms, we find

Θ_{1} − \frac{1}{2}Θ_{2} + \frac{1}{3}Θ_{3} − ⋯ + \frac{(−1)^{i−1}}{i} Θ_{i} + ⋯ = log(1 + x_{1}),  (41)

where Θ_{i} = Θ(x_{i}, x_{2i}, x_{3i}, ⋯), i ≥ 1. By summation, we obtain the remarkable relation

Θ_{1} − Θ_{2} = Ω , where Ω := Z_{(E^{+})^{<−1>}} = ∑_{k=1}^{∞} \frac{μ(k)}{k} log(1 + x_{k})  (42)

since the Möbius function satisfies the property

\frac{1}{n} ∑_{d|n} μ(n/d)(−1)^{d−1} = \{ \begin{matrix}1, & if & n = 1, \\ −1, & if & n = 2, \\ 0, & if & n ≥ 3. \end{matrix}  (43)

Another summation, based on (42), gives

Θ = Ω_{1} + Ω_{2} + Ω_{4} + ⋯ + Ω_{2^{i}} + · · · .  (44)

We then get, by collecting terms properly,

Γ_{Λ^{(α)}} = (Γ_{E}) ∘ (αx_{1}) ∘ (Γ_{(E^{+})^{<−1>}}) = Γ_{E} ∘ (αΩ_{1} + αΩ_{2} + αΩ_{4} + ⋯) = ∏_{n≥1}(1 + x_{n})^{γ_{n}(α)}  (45)

where

γ_{n}(α) = ∑_{2^{i}·j·k=n} \frac{(−1)^{j−1}μ(k)}{kj}α^{j}  (46)

and equation (32) is satisfied. The other series associated to Λ_{(α)} follow directly from the formulas for Z_{Λ_{(α)}} and Γ_{Λ_{(α)}}. □

The following corollary gives the general explicit form of the series associated to the species F_{w^{(α)}} in terms of the series for F_{w}. The proof is straightforward and left to the reader.

Corollary 2.3 Let F_{w} be a weighted virtual species such that F_{w}(0) = 1 and set F_{w^{(α)}} = Λ^{(α)} ∘ F_{w}^{+}. Then we have

F_{w^{(α)}}(x) = F_{w}(x)^{α},  (47)
Z_{F_{w^{(α)}}} (x_{1}, x_{2}, x_{3}, …) = ∏_{n≥1} Z_{F_{w^{n}}} (x_{n}, x_{2n}, x_{3n}, …)^{λ_{n}(α)},  (48)
F̃_{w^{(α)}}(x) = ∏_{n≥1} F̃_{w^{n}}(x^{n})^{λ_{n}(α)},  (49)

F_{w^{(α)}}(x; q) = ∏_{n≥1} F_{w^{n}}(\frac{(1 − q)^{n}}{(1 − q^{n})}x^{n}; q^{n})^{λ_{n}(α)},  (50)
Γ_{F_{w^{(α)}}} (x_{1}, x_{2}, x_{3}, …) = ∏_{n≥1} Γ_{F_{w^{n}}} (x_{n}, x_{2n}, x_{3n}, …)^{γ_{n}(α)},  (51)
\overline{F_{w^{(α)}}}(x) = ∏_{n≥1} \overline{F_{w^{n}}}(x^{n})^{γ_{n}(α)},  (52)

F_{w^{(α)}}⟨x; q⟩ = ∏_{n≥1} F_{w^{n}}⟨\frac{(1 − q)^{n}}{(1 − q^{n})}x^{n}; q^{n}⟩^{γ_{n}(α)}.  (53)

□

The special case α = −1 is particularly interesting. In the simplest case of the series (47), it corresponds to the computation of the excess weight of the F_{w}-structures having an even number of connected components over those having an odd number:

F_{w^{(−1)}}(x) = ∑_{n≥0}(f_{n}^{+} − f_{n}^{−})\frac{x^{n}}{n!} ,  (54)

where

f_{n}^{+} = total weight of F_{w}-structures on [n] with an even number of connected components, (55)
f_{n}^{−} = total weight of F_{w}-structures on [n] with an odd number of connected components. (56)

The behavior of the seven main series with respect to the transformation F_{w} ↦ F_{w^{(−1)}} is described in the following corollary.

Corollary 2.4 Let F_{w} be a weighted virtual species such that F_{w}(0) = 1 and set F_{w^{(−1)}} = Λ^{(−1)} ∘F_{w}^{+}. Then we have

F_{w^{(−1)}}(x) = 1/F_{w}(x),  (57)
Z_{F_{w^{(−1)}}} (x_{1}, x_{2}, x_{3}, …) = \frac{Z_{F_{w^{2}}} (x_{2}, x_{4}, x_{6}, …)}{Z_{F_{w}}(x_{1}, x_{2}, x_{3}, …)},  (58)
F̃_{w^{(−1)}}(x) = \frac{F̃_{w^{2}}(x^{2})}{F̃_{w}(x)},  (59)

F_{w^{(−1)}}(x; q) = \frac{F_{w^{2}}(\frac{(1−q)}{(1+q)}x^{2}; q^{2})}{F_{w}(x; q)},  (60)
Γ_{F_{w^{(−1)}}} (x_{1}, x_{2}, x_{3}, …) = 1/ ∏_{k≥0} Γ_{F_{w^{2^{k}}}} (x_{2^{k}}, x_{2·2^{k}}, x_{3·2^{k}}, …),  (61)
\overline{F_{w^{(−1)}}}(x) = 1/ ∏_{k≥0} \overline{F_{w^{2^{k}}}} (x^{2^{k}}),  (62)

F_{w^{(−1)}}⟨x; q⟩ = 1/ ∏_{k≥0} F_{w^{2^{k}}} ⟨\frac{(1 − q)^{2^{k}}}{(1 − q^{2^{k}})}x^{2^{k}}; q^{2^{k}}⟩.  (63)

Proof. It suffices to use the relations

λ_{n}(−1) = \{ \begin{matrix}−1, & if & n = 1 \\ 1, & if & n = 2 \\ 0, & if & n ≥ 3 \end{matrix} and γ_{n}(−1) = \{ \begin{matrix}−1, & if n = 2^{k}, k ≥ 0 \\ 0, & otherwise . \end{matrix}  (64)

□

Observe that the transformations described by (57)–(63) are involutive since w^{(−1)(−1)} = w. It is easily verified that the series associated to the universal virtual species Λ^{(−1)} are given by

Λ^{(−1)}(x) = (1 + x)^{−1},

Z_{Λ^{(−1)}} = \frac{1 + x_{2}}{1 + x_{1}} , Λ̃^{(−1)}(x) = \frac{1 + x^{2}}{1 + x} , Λ^{(−1)}(x; q) = \frac{1 + \frac{1−q}{1+q} x^{2}}{1 + x} ,  (65)
Γ_{Λ^{(−1)}} = ∏_{k≥0}(1 + x_{2^{k}})^{−1},  \overline{Λ^{(−1)}}(x) = 1 − x,  Λ^{(−1)}⟨x; q⟩ = ∏_{k≥0}(1 + \frac{(1 − q)^{2^{k}}}{1 − q^{2^{k}}} x^{2^{k}})^{−1}.

3 Examples arising from particular choices of F_{w}

The corollaries 2.3 and 2.4 give rise to a multitude of identities and of interesting expressions, by choosing particular species F_{w}. For example, in the case of the species F_{w} = E, of sets (trivially weighted by w = 1), we have Z_{E} = exp(∑_{n≥1} x_{n}/n) and Γ_{E} = exp(∑_{n≥1}(−1)^{n−1}x_{n}/n). The formulas (47)–(53) of Corollary 2.3 produce respectively the identities

e^{αx} = (e^{x})^{α},  (66)
exp(∑_{k≥1} α^{k}x_{k}/k) = ∏_{n≥1} exp(λ_{n}(α) ∑_{k≥1} x_{kn}/k),  (67)
(1 − αx)^{−1} = ∏_{n≥1}(1 − x^{n})^{−λ_{n}(α)},  (68)
E(αx; q) = E(x; q)^{α} E(\frac{(1−q)^{2}}{(1−q^{2})}x^{2}; q^{2})^{λ_{2}(α)} E(\frac{(1−q)^{3}}{(1−q^{3})}x^{3}; q^{3})^{λ_{3}(α)} ⋯,  (69)
exp(∑_{k≥1}(−1)^{k−1}α^{k}x_{k}/k) = ∏_{n≥1} exp(λ_{n}(α) ∑_{k≥1}(−1)^{k−1}x_{kn}/k),  (70)
1 + αx = ∏_{n≥1}(1 + x^{n})^{γ_{n}(α)},  (71)
E⟨αx; q⟩ = E⟨x; q⟩^{α} E⟨\frac{(1−q)^{2}}{(1−q^{2})}x^{2}; q^{2}⟩^{γ_{2}(α)} E⟨\frac{(1−q)^{3}}{(1−q^{3})}x^{3}; q^{3}⟩^{γ_{3}(α)} · · · .  (72)

The reader will recognize, in (68), the classical cyclotomic identity of Gauss (see [10], [30]). The identity (71) constitutes a kind of dual of (68) and could be called the cocyclotomic identity. The identities (67) (due to F. Bergeron, see [1], p. 300) and (70) are extensions of (68) and (71) which also yield (69) and (72) by specialization. Expressed in terms of the q-exponentials, the latter can be seen as q-analogues of the cyclotomic and cocyclotomic identities.

In the case of the species F_{w} = S, of permutations, we have Z_{S} = ∏_{n≥1}(1 − x_{n})^{−1} and Γ_{S} = (1 − x_{2})/(1 − x_{1}). Let us then denote by S_{(α)}, the transformed species of permutations, weighted by the cycle counter α. Applications of Corollary 2.3 give for example, after a proper term collection,

Z_{S_{(α)}} = ∏_{n≥1}(1 − x_{n})^{−ν_{n}(α)},  (73)

where ν_{n}(α) denotes the polynomial defined by

ν_{n}(α) = \frac{1}{n} ∑_{d|n} ϕ(n/d)α^{d},  (74)

where ϕ(n) is the Euler totient function. When α is a positive integer, ν_{n}(α) is the number of circular words of length n over an alphabet with α letters or, equivalently, the number of (not necessarily primitive) necklaces of length n with α colors. Formula (73), due to H. Décoste, is the basis for the computation of the cycle index series of combinatorial models of the classical orthogonal polynomials of Laguerre, Charlier, Meixner, Meixner-Pollaczek, and Jacobi, (see [7], [8], and also [6], [34] and [35]) and their canonical q-analogues. We also obtain

Γ_{S_{(α)}} = ∏_{n odd}(1 − x_{n})^{−γ_{n}(α)} ∏_{n even}(1 − x_{n})^{λ_{n}(−α)}.  (75)

Taking the particular value α = −1, Corollary 2.4 gives the following formulas:

S_{(−1)}(x) = 1 − x,  (76)
Z_{S_{(−1)}}(x_{1}, x_{2}, x_{3}, …) = (1 − x_{1})(1 − x_{3})(1 − x_{5}) ⋯,  (77)
S̃_{(−1)}(x) = (1 − x)(1 − x^{3})(1 − x^{5}) ⋯,  (78)
S_{(−1)}(x; q) = (1 − x)(1 − \frac{(1−q)^{3}}{(1−q^{3})}x^{3})(1 − \frac{(1−q)^{5}}{(1−q^{5})}x^{5}) ⋯,  (79)
Γ_{S_{(−1)}}(x_{1}, x_{2}, x_{3}, …) = 1 − x_{1},  (80)
\overline{S_{(−1)}}(x) = 1 − x,  (81)
S_{(−1)}⟨x; q⟩ = 1 − x.  (82)

The reader is invited to give direct combinatorial proofs of these formulas.

In the case of the species F_{w} = Gr_{w} of graphs, weighted by an edge counter y, already seen in the introduction, the series Gr_{w^{(α)}}(x), Z_{Gr_{w^{(α)}}} , G̃r_{w^{(α)}}(x), Gr_{w^{(α)}}(x; q), of the associated species Gr_{w^{(α)}} can be computed with the help of (47)–(50), by using the known formula (see [2], [18])

Z_{Gr}(x_{1}, x_{2}, x_{3}, …) = ∑_{n=0}^{∞} \frac{1}{n!} ∑_{σ∈S_{n}}(1 + y)^{c_{1}}(1 + y^{2})^{c_{2}}(1 + y^{3})^{c_{3}} ⋯ x_{1}^{σ_{1}}x_{2}^{σ_{2}}x_{3}^{σ_{3}} ⋯,  (83)

where

c_{k} = \frac{1}{2} ∑_{[i,j]=k}(i, j)σ_{i}σ_{j} + σ_{2k} − σ_{k} + \frac{1}{2}(k mod 2)σ_{k},  (84)

and where [i, j] denotes the smallest common multiple of the integers i and j. However, the explicit computation of the other series Γ_{Gr_{w^{(α)}}} , \overline{Gr_{w^{(α)}}}(x), Gr_{w^{(α)}}⟨x; q⟩ is an open problem since no closed formulas for the series Γ_{Gr_{w}}, \overline{Gr_{w}}(x), Gr_{w}⟨x; q⟩ are known up to now.

Other applications are possible, in addition to the various combinatorial models of orthogonal polynomials already mentioned. An example is given by the species F_{w} = E(A) = A/X, of forests of rooted trees (where A is the species of rooted trees). The transformation F_{w} ↦ F_{w^{(α)}} is then equivalent to the introduction of a counter for trees in the forests. Taking the coefficients of the seven associated series yields families of polynomials in α: a_{n}(α), a_{σ}(α), ã_{n}(α), a_{n}(α; q), a_{σ}^{∗}(α), \overline{a}_{n}(α) and a_{n}⟨α; q⟩. The first is the family of classical Abel polynomials a_{n}(α) = α(α + n)^{n−1} while the others constitute generalized versions of it. Note that these generalized Abel polynomials are distinct from those introduced in [26], since the species F_{w^{(α)}} is different from the simple exponentiation (F_{w})^{α}, even when α is an integer.

4 Some properties of the species Λ^{(α)}

Recall that the universal virtual weighted species Λ^{(α)} is defined by Λ^{(α)} = E ∘X_{α}∘(E^{+})^{<−1>} and that we have F_{w^{(α)}} = Λ^{(α)} ∘ F_{w}^{+}, for any weighted species F_{w} such that F_{w}(0) = 1. Since the exponential generating series of Λ^{(α)} given by Λ^{(α)}(x) = (1+x)^{α}, it is natural to ask which properties of the function (1 + x)^{α} carry over to the species Λ^{(α)}. For example, the algebraic identity ((1 + x)^{β})^{α} = (1 + x)^{αβ} can be lifted to the combinatorial equality

Λ^{(α)} ∘ (Λ^{(β)})^{+} = Λ^{(αβ)},  (85)

where (Λ^{(β)})^{+} = Λ^{(β)} − 1 = E^{+} ∘ X_{β} ∘ (E^{+})^{<−1>} is the conjugate (for composition) of the species of singletons of weight β by that of non-empty sets. Indeed, since X_{α} ∘ X_{β} = X_{αβ}, we have immediately

E ∘ X_{α} ∘ (E^{+})^{<−1>} ∘ E^{+} ∘ X_{β} ∘ (E^{+})^{<−1>} = E ∘ X_{αβ} ∘ (E^{+})^{<−1>}.  (86)

By taking the cycle and asymmetry index series of both sides of (85) the following identities are easily obtained:

λ_{n}(αβ) = ∑_{i·j=n} λ_{i}(α^{j})λ_{j}(β), γ_{n}(αβ) = ∑_{i·j=n} γ_{i}(α^{j})γ_{j}(β), n ≥ 0.  (87)

The identity on the left hand side of (87) is a variant of the well known relation (see [30])

λ_{n}(αβ) = ∑_{[i,j]=n}(i, j)λ_{i}(α)λ_{j}(β).  (88)

Of course, the algebraic identity Λ^{(α)}(x) · Λ^{(β)}(x) = (1 + x)^{α}(1 + x)^{β} = (1 + x)^{α+β} = Λ^{(α+β)}(x), between generating series, is satisfied. However, we have, at the species level,

Λ^{(α)} · Λ^{(β)} ≠ Λ^{(α+β)}  (89)

This behavior follows from the fact that X_{α} +X_{β} ≠ X_{α+β}. It is also reflected by the fact that although λ_{1}(α + β) = α + β = λ_{1}(α) + λ_{1}(β), we have

λ_{n}(α + β) ≠ λ_{n}(α) + λ_{n}(β), if n ≥ 2 .  (90)

The difference operator Δ, defined by ΔG = G ∘ E^{+} − G, permits the expression of Λ^{(α)} in the form

Λ^{(α)} = E(X_{α}) − ΔE(X_{α}) + Δ^{2}E(X_{α}) − Δ^{3} E(X_{α}) + ⋯  (91)

By using the computer algebra software Maple [4], Y. Chiricota (personal communication, see also [5]) has computed the molecular decomposition of Λ^{(α)}, i.e., its expression as a ℤ-linear combination of molecular (i.e., indecomposable under addition) species, up to degree 7 . Here are the first terms, up to degree 5:

Λ^{(α)} = E ∘ X_{α} ∘ (E^{+})^{<−1>}
= 1 + X_{α} − (E_{2})_{α} + (E_{2})_{α^{2}} − (E_{3})_{α} + (XE_{2})_{α} − (XE_{2})_{α^{2}} + (E_{3})_{α^{3}}
+ (E_{2} ∘ E_{2})_{α} − (E_{4})_{α} + (XE_{3})_{α} − (X^{2}E_{2})_{α}
+ (E_{2}^{2})_{α^{2}} − (XE_{3})_{α^{2}} + (X^{2}E_{2})_{α^{2}} − (E_{2} ∘ E_{2})_{α^{2}} − (E_{2}^{2})_{α^{3}} + (E_{4})_{α^{4}}  (92)
+ (E_{2}E_{3})_{α} + (XE_{4})_{α} + (X^{3}E_{2})_{α} − (X^{2}E_{3})_{α} − (XE_{2}^{2})_{α} − (E_{5})_{α}
+ (E_{2}E_{3})_{α^{2}} + (X^{2}E_{3})_{α^{2}} − (XE_{4})_{α^{2}} − (X^{3}E_{2})_{α^{2}} + (X E_{2} ∘ E_{2})_{α^{2}} − (XE_{2}^{2})_{α^{2}}
+ 2 (XE_{2}^{2})_{α^{3}} − (E_{2}E_{3})_{α^{3}} − (X E_{2} ∘ E_{2})_{α^{3}} − (E_{2}E_{3})_{α^{4}} + (E_{5})_{α^{5}}
+ ⋯,

where E_{k} denotes the species of sets of cardinality k. The molecular decomposition (92) can be seen as a combinatorial lifting of the binomial formula

Λ^{(α)}(x) = (1 + x)^{α}
= 1 + α x + α(α − 1)\frac{x^{2}}{2!} + α(α − 1)(α − 2)\frac{x^{3}}{3!} + α(α − 1)(α − 2)(α − 3)\frac{x^{4}}{4!} + · · · . (93)

The formulas (91) and (92) show that Λ^{(α)} is a species of set-like type: all its molecular components are obtained by products and compositions of species of the form E_{k} . For all n ≥ 0, set

m_{n} = number of set-like molecular species of degree n,  (94)
a_{n} = number of set-like atomic species of degree n.  (95)

A species is atomic if it is molecular and indecomposable under the product. It can be shown that the sequences (m_{n})_{n≥0} and (a_{n})_{n≥0} satisfy the double recursive scheme

\begin{matrix}m_{0} = 1, & m_{1} = 1, \\ a_{0} = 0, & a_{1} = 1, \end{matrix}  \{ \begin{matrix}m_{n} & = & \frac{1}{n} ∑_{k=1}^{n}(∑_{d|k} d a_{d})m_{n−k} \\ a_{n} & = & ∑_{{k | n \atop k<n}} m_{k} \end{matrix}  n ≥ 2,  (96)

which is equivalent to the following relations:

∑_{n≥0} m_{n} x^{n} = ∏_{k≥1} \frac{1}{(1 − x^{k})^{a_{k}}} ,  ∑_{n≥1} \frac{a_{n}}{n^{s}} = 1 + (ζ(s) − 1) · ∑_{n≥1} \frac{m_{n}}{n^{s}} ,  (97)

where ζ(s) denotes the Riemann zeta function. In the case of all atomic and molecular species, the first of these relations has an analogue (see [27], [28]) but not the second one. Here are the values of m_{n} and a_{n}, for 0 ≤ n ≤ 40:

m_{n} = 1, 1, 2, 3, 7, 9, 20, 26, 54, 74, 137, 184, 356, 473, 841, 1154, 2034, 2742, 4740, 6405, 10874,
14794, 24515, 33246, 54955, 74380, 120501, 163828, 263144, 356621, 567330, 768854, 1212354, (98)

1644335, 2567636, 3478873, 5403223, 7314662, 11265825, 15258443, 23363143,

a_{n} = 0, 1, 1, 1, 3, 1, 6, 1, 10, 4, 12, 1, 33, 1, 29, 13, 64, 1, 100, 1, 156, 30, 187, 1, 443, 10, 476, 78,
877, 1, 1326, 1, 2098, 188, 2745, 36, 5203, 1, 6408, 477, 11084.  (99)

These sequences do not appear in the 1973 edition of Sloane’s book [32] but they do in the new edition [33]. The analytical properties of the functions (97) should prove useful for the asymptotic analysis of the numbers m_{n}, for n → ∞.

References

[1] F. Bergeron, Une combinatoire du pléthysme. Journal of Combinatorial Theory, Series A, 46 (1987), 291–305.

[2] F. Bergeron, G. Labelle et P. Leroux, Théorie des espèces et combinatoire des structures arborescentes. Publications du LACIM, Vol. 19, Université du Québec à Montréal, 1994.

[3] P. Cartier et D. Foata, Problèmes combinatoires de commutation et de réarrangements. Lecture Notes in Mathematics, 85, Springer-Verlag, 1969.

[4] B. W. Char, K. O. Geddes, G. H. Gonnet, B. L. Leong, M. B. Monagan and S. M. Watt, MAPLE V Language Reference Manual. Springer-Verlag, 1991.

[5] Y. Chiricota, Structures combinatoires et calcul symbolique. Publications du LACIM, Vol. 12, Université du Québec à Montréal, 1993.

[6] I. Constantineau, Auto-similarité dans la combinatoire des polynômes orthogonaux. Theoretical Computer Science, Elsevier, 117 (1993), 153-167.

[7] H. Décoste, Séries indicatrices d’espèces pondérées et q-analogues. Publications du LACIM, Vol. 2, Université du Québec à Montréal, 1990 (Ph.D. Thesis, Un. de Montréal, 1989).

[8] H. Décoste, Séries indicatrices et q-séries. Theoretical Computer Science, Elsevier, 117 (1993), 169–186.

[9] H. Décoste et G. Labelle, Le q-dénombrement générique d’une espèce de structures. Discrete Mathematics , à paraître.

[10] A. Dress and C. Siebeneicher, The Burnside ring of the infinite cyclic group and its relations to the necklace algebra, lambda-rings, and the universal ring of Witt vectors, Adv. in Mathematics, 78 (1989) 1–41.

[11] A. Dress and C. Siebeneicher On the number of solutions of certain linear Diophantine equations. Hokkaido Mathematical Journal, 19 (1990), 385–401.

[12] D. Foata, La série exponentielle dans les problèmes d’énumération. Presses de l’Université de Montréal, 1974.

[13] D. Foata, A combinatorial proof of the Mehler formula. Journal of Combinatorial Theory, Series A, 24 (1978), 367–376.

[14] D. Foata et J. Labelle, Modèles combinatoires pour les polynômes de Meixner. European Journal of Combinatorics, 4 (1983), 305–311.

[15] D. Foata et P. Leroux, Polynômes de Jacobi, interprétation combinatoire et fonction génératrice. Proceedings of the American Mathematical Society, 87 (1983), 47–53.

[16] D. Foata et M. P. Schutzenberger, Théorie géométrique des polynômes eulériens. Lecture Notes in Mathematics, Vol. 138, Springer-Verlag, 1970.

[17] D. Foata and V. Strehl, Combinatorics of Laguerre polynomials. In: D. M. Jackson and S. A. Vanstone, eds., Enumeration and Design, Academic Press, 1984, 123–140.

[18] F. Harary and E. Palmer, Graphical enumeration. Academic Press, 1973.

[19] A. Joyal, Une théorie combinatoire des séries formelles. Advances in Mathematics, 42 (1981), 1–82.

[20] A. Joyal, Foncteurs analytiques et espèces de structures. In: G. Labelle and P. Leroux, eds, Combinatoire énumérative, Proceedings, Montréal, Québec, 1985. Lecture Notes in Mathematics, Vol. 1234, Springer-Verlag, 1986, 126–159.

[21] G. Labelle, Une nouvelle démonstration combinatoire des formules d’inversion de Lagrange. Advances in Mathematics, 42 (1981), 217–247.

[22] G. Labelle, Some new computational methods in the theory of species, In: G. Labelle and P. Leroux, eds, Combinatoire énumérative, Proceedings, Montréal, Québec 1985. Lecture Notes in Mathematics, Vol. 1234, Springer-Verlag, 1986, 192–209.

[23] G. Labelle, On asymmetric structures. Discrete Mathematics, 99 (1992), 141–164.

[24] G. Labelle, Counting asymmetric enriched trees. Journal of Symbolic Computation, 14 (1992), 211–242.

[25] G. Labelle, Sur la symétrie et l’asymétrie des structures combinatoires. Theoretical Computer Science, Elsevier, 117 (1993), 3–22.

[26] G. Labelle, Enriched q-Abel identities arising from symmetric functions. Rapport de Recherche, Département de Mathématiques, UQAM , no 244, mars 1995.

[27] J. Labelle, Quelques espèces sur les ensembles de petites cardinalités. Annales des sciences mathématiques du Québec, 9 (1985), 31–58.

[28] J. Labelle and Y.-N. Yeh, The Relation between Burnside Rings and Combinatorial Species, Jour. Combin. Th., A, 50 (1989), 269–284.

[29] M. Lothaire, Combinatorics on Words. Encyclopedia of Mathematics, Vol. 17, Addison-Wesley 1983, Cambridge University Press 1984.

[30] N. Metropolis and G.-C. Rota, Witt Vectors and the Algebra of Necklaces. Advances in Mathematics, 50 (1983), 95–125.

[31] C. Reutenauer, Mots circulaires et polynômes irréductibles. Annales des sciences mathématiques du Québec, 12 (1988), 275–285.

[32] N. J. A. Sloane, A Handbook of Integer Sequences. Academic Press, 1973.

[33] N. J. A. Sloane and S. Plouffe, The Encyclopedia of Integer Sequences. Academic Press, 1995.

[34] V. Strehl, Cycle counting for isomorphism types of endofunctions. Bayreuther Mathematische Schriften, 40 (1992), 153–167.

[35] V. Strehl, Zykel-Enumeration bei lokal-strukturierten Funktionen. Habilitationsschrift, Institut für Mathematische Maschinen und Datenverarbeitung, Universität Erlangen-Nürnberg, 1990

[36] Y.-N. Yeh, The calculus of virtual species and 𝕂-species. In: G. Labelle and P. Leroux, eds, Combinatoire énumérative, Proceedings, Montréal, Québec, 1985. Lecture Notes in Mathematics, Vol. 1234, Springer-Verlag, Berlin, 1986, 351–369.