Paris, le 16 Févier 2005, 18h21

Please, don’t spread before discussion

1 A version of the exponential formula

Applying the exponential paradigm one can feel sometimes incomfortable wondering whether “one has the right” to do so (as for example for coloured structures). The following is aimed at giving a rather large framework where this formula holds. Exponential formula can be traced back to works by Touchard and Ridell & Uhlenbeck [5, 3]. For an other exposition see for example [2, 4]. We are interested to compute various examples of EGF for combinatorial objects having (a finite set of) nodes (i.e. their set-theoretical support) so we use as central concept the mapping σ which associates to every structure, its set of nodes. We need to draw what could be called “square-free decomposable objects” (SFD). This version is suited to our needs for the “exponential formula”. It is sufficiently general to contain, as a particular case, the case of multivariate series. Let FSt the category of finite sets and C be a class of (combinatorial) objects endowed with a mapping σ : C ↦ FSt. The setting (C, σ) will be called (SFD) if it fulfills the two following conditions.

(DS) Direct sum. — There is a (partial) binary law ⊕ on C, defined for couples of objects (ω_{1}, ω_{2}) such that σ(ω_{1}) ∩ σ(ω_{2}) = ∅, which is associative, commutative and such that

C_{F_{1}} × C_{F_{2}} →^{⊕} C_{F_{1}∪F_{2}}  (1)

is into. Moreover, C_{∅} consists in a single element {ϵ} which is neutral in the sense that, identically

ϵ ⊕ ω = ω ⊕ ϵ = ω  (2)

(LP) Levi’s property. — Let ω = ω_{1} ⊕ ω_{2} = ω^{1} ⊕ ω^{2} be two decompositions. Then it can be found a four terms decomposition ω = ⊕_{i,j=1,2}ω_{j}^{i} refining the original data in the sense that the maginal sums give the factors of the decompositions i.e.

ω_{j} = ω_{j}^{1} ⊕ ω_{j}^{2} and ω^{i} = ω_{1}^{i} ⊕ ω_{2}^{i}; i, j = 1, 2  (3)

Note 1.1 Condition (1) implies that σ(ω_{1} ⊕ ω_{2}) = σ(ω_{1}) ⊔ σ(ω_{2}).

Now, an atom is any object ω ≠ ϵ which cannot be split, formally

ω = ω_{1} ⊕ ω_{2} ⟹ ϵ ∈ {ω_{1}, ω_{2}}  (4)

Example 1.2 As example of this setting we have:

1. the positive square-free integers σ(n) being the set of primes which divide n, the atoms being the primes.

2. the positive integers σ(n) being the set of primes which divide n, the atoms being the primes.

3. graphs, hypergraphs, (finitely) coloured, weighted graphs, σ(G) being the set of nodes and ⊕ the juxtaposition, here the atoms are connected graphs.

4. the class of endofunctions f with σ(f) = dom(f)

5. the (multivariate) polynomials in N[X] with σ = Alph and ⊕ = +.

6. the square-free monic (for a given order on the variables) polynomials ; σ(P) being the set of irreducible monic divisors of P and ⊕ being the multiplication.

7. complex algebraic curves ; σ(V) being the set of monic irreducible bivariate polynomials vanishing on an infinite subset of V.

The prescriptions (DS,LP) imply that decomposition of objects into atoms always exists and is unique.

Proposition 1.3 Let ω ∈ C then ω = ω_{1} ⊕ ω_{2} ⊕ ⋯ ⊕ ω_{l} the ω_{i} being (dinstinct) atoms and the set {ω_{1}, ω_{2} ⋯ ω_{l}} depends only on ω.

In the class C, objects are conceived to be “measured” by different parameters (data in statistical language). So, to get a general purpose tool, we suppose that the statistics takes it’s values iin a ring K which contains ℚ (as, to write EGFs it is convenient to have no trouble with the fractions \frac{1}{n!}). Let then c : C → K be the given statistic. In order to write generating series, we need

1. that the sum c_{F} = ∑_{ω∈C_{F}} c(w) exists

2. that F → c_{F} should depend only of the cardinality of F.

3. c(ω_{1} ⊕ ω_{2}) = c(ω_{1}).c(ω_{2})

We formalize it in

(LF) Local finiteness. — For each finite set F, the subclass

C_{F} = {ω ∈ C|σ(ω) = F }  (5)

is a finite set. (Eq) Equivariance. —

|F_{1}| = |F_{2}| ⟹ c_{F_{1}} = c_{F_{2}}  (6)

(Mu) Multiplicativity. —

c(ω_{1} ⊕ ω_{2}) = c(ω_{1}).c(ω_{2})  (7)

Note 1.4 a) In fact, (LF) is a property of the class C, while (Eq) is a property of the statistics. In practice, we choose C which is locally finite and choose equivariant statistics for instance

c(ω) = x^{(number of cycles)}y^{(number of fixed points)}

for some variables x, y.

b) More generally, it is typical to take integer-valued partial (additive) statistics c_{1}, ⋯ c_{i}, ⋯, c_{r} (for every ω ∈ C, c_{i}(ω) ∈ N) and set c(ω) = x_{1}^{c_{1}(ω)}x_{2}^{c_{2}(ω)} ⋯ x_{r}^{c_{r}(ω)}.

c) The class of examples 1.2.2 is not locally finite, but other examples satisfy (LF): 1.2.3 if one asks that the number of arrows and weight is finite, 1.2.1 and 1.2.5 to 1.2.7 in any case.

Now, we are in position to state the exponential formula as it will be used throughout the paper.

Proposition 1.5 Let C be a locally finite (SFD) and c : C → K an equivariant statistics on C. For every subclass F one sets the following exponential generating series

E(F; z) = ∑_{n=0}^{∞} c(F_{[1..n]})\frac{z^{n}}{n!}  (8)

Let C^{a} be the set of atoms of C. Then, one has

E(C; z) = e^{E(C^{a};z)}  (9)

Proof — (First Step). — We consider the subclasses of objects the atoms of which have a support of cardinality n i.e.

C[n] = {ω ∈ C|ω = ω_{1}⊕ω_{2}⊕⋯⊕ω_{s} = ω with ω_{i} ∈ C^{a} and |σ(ω)| = n for i = 1..s} (10)

These subclasses are closed under compositions (i.e. under ⊕) and decompositions and their atoms C^{a}[n] = {ω ∈ C[n] ∩ C^{a}}. Now, one has, thanks to the partitions of [1..n]

C_{[1..n]} = ⨆_{{k≥0, 0<n_{1}<n_{2}<···<n_{k} \atop n_{1}+n_{2}+···n_{k}=n}} ⨆_{{|P_{j} |=n_{j} \atop P_{1}⊔P_{2}⊔···P_{k}=[1..n]}} C_{P_{1}} ⊕ C_{P_{2}} ⊕ ⋯ ⊕ C_{P_{k}}  (11)

c(C_{[1..n]}) = ∑_{k≥0} ∑_{{0<n_{1}<n_{2}<···<n_{k} \atop n_{1}+n_{2}+···n_{k}=n}} ∑_{{|P_{j} |=n_{j} \atop P_{1}⊔P_{2}⊔···P_{k}=[1..n]}} c(C_{P_{1}})c(C_{P_{2}}) ⋯ c(C_{P_{k}})  (12)

as, for disjoint sets, it is easy to check that c(C_{X} ⊕ C_{Y}) = c(C_{X})c(C_{Y}). Now, due to the equivariance of c and to the fact that partitions (P_{1}, P_{2}, ⋯, P_{k}) such that P_{j} = n_{j} and P_{1} ⊔ P_{2} ⊔ ⋯ P_{k} = [1..n] are in number

\frac{n!}{n_{1}!n_{2}! ⋯ n_{k}!}

we get

c(C_{[1..n]}) = ∑_{k≥0} ∑_{{0<n_{1}<n_{2}<···<n_{k} \atop n_{1}+n_{2}+···n_{k}=n}} \frac{n!}{n_{1}!n_{2}! ⋯ n_{k}!}c(C_{[1..n_{1}]})c(C_{[1..n_{2}]}) ⋯ c(C_{[1..n_{k}]})  (13)

thus

E(C) = ∏_{n>0} E(C[n])  (14)

We then compute the factors.

E(C[n]) = ∑_{k≥0} c(C[n]_{[1..nk]})\frac{z^{nk}}{(nk)!}  (15)

but

E(C^{a}[n]) = c(C_{[1..n]}^{a})\frac{z^{n}}{n!}  (16)

(one monomial) and

e^{E(C^{a}[n])} = ∑_{k≥0} c(C_{[1..n]}^{a})^{k} \frac{z^{nk}}{(n!)^{k}k!} = ∑_{k≥0} c(C_{[1..n]}^{a})^{k} \frac{z^{nk}}{(nk!)} \frac{(nk)!}{(n!)^{k}k!} =

∑_{k≥0} c(C[n]_{[1..nk]})\frac{z^{nk}}{(nk)!} = E(C[n])

due to the fact that the number of (unordered) partitions of [1..nk] into k blocs of cardinality n is \frac{(nk)!}{(n!)^{k}k!}. To end the proof, it suffices to remark that C^{a} = ⊔_{n>0}C^{a}[n] and then

E(C) = ∏_{n>0} E(C[n]) = ∏_{n>0} e^{E(C^{a}[n])} = e^{∑_{n>0} E(C^{a}[n])} = e^{E(C^{a})}  (17)

Note 1.6 The proof suggests us that it is fruitful to factor a class C into (full) subclasses i.e. that are generated by a partition of the atoms.

References

[1] Comtet L., Analyse combinatoire, PUF (1970)

[2] Joyal A., Species ??, Advances in Math.

[3] Ridell R.J., Uhlenbeck G.E., On the theory of the virial development of the equation of state of monomatomic gases, J. Chem. Phys. 21 (1953), 2056-2064.

[4] Stanley R., Enumerative Combinatorics Vol I and II, Cambridge.

[5] Touchard J., Sur les cycles des permutations, Acta Math. 70 (1939), 243-297.