Journal of Nonlinear Systems and Applications ()
Copyright c 2009 Watam Press

http://www.watam.org/JNSA/

STATISTICS ON GRAPHS, EXPONENTIAL FORMULA AND
COMBINATORIAL PHYSICS

arXiv:0910.0695v2 [cs.DM] 11 Feb 2010

Laurent Poinsot, Gérard H. E. Duchamp, Silvia Goodenough and Karol A. Penson

2

Abstract. The concern of this paper is a famous combinatorial
formula known under the name “exponential formula”. It occurs
quite naturally in many contexts (physics, mathematics, computer

Partial semigroups

Let us call partial semigroup a semigroup with a partially
defined associative law (see for instance [6] for usual semigroups and [1, 14, 18] for more details on structures with
a partially defined binary operation). More precisely, a
partial semigroup is a pair (S, ∗) where S is a set and ∗
is a (partially defined) function S × S → S such that the
two (again partially defined) functions S × S × S → S

science). Roughly speaking, it expresses that the exponential generating function of a whole structure is equal to the exponential
of those of connected substructures. Keeping this descriptive statement as a guideline, we develop a general framework to handle many
different situations in which the exponential formula can be applied.
Keywords. Combinatorial physics, Exponential generating function, Partial semigroup, Experimental mathematics.

1

†‡
∗

(x, y, z) 7→ (x ∗ y) ∗ z and (x, y, z) 7→ x ∗ (y ∗ z)

(1)

coincide (same domain and values). Using this requirement one can see that the values of the (partially defined)
functions S n → S

Introduction

(x1 , · · · , xn ) 7→ ET (x1 , · · · , xn )

Applying the exponential paradigm one can feel sometimes incomfortable wondering whether “one has the
right” to do so (as for coloured structures, for example). The following paper 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 [20, 17]. For an other
exposition, see for example [4, 7, 9, 19].
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 (labels of its) 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” and it is sufficiently
general to contain, as a particular case, the case of multivariate series.

(2)

obtained by evaluating the expression formed by labelling
by xi (from left to right) the ith leaf of a binary tree T
with n nodes and by ∗ its internal nodes, is independant
of T . We will denote x1 ∗ · · · ∗ xn their common value.
In this paper we restrict our attention to commutative
semigroups. By this we mean that the value x1 ∗ · · · ∗
xn does not depend on the relative order of the xi . A
nonempty partial semigroup (S, ∗) has a (two-sided and
total) unit ǫ ∈ S if, and only if, for every ω ∈ S, ω ∗ ǫ =
ω = ǫ∗ω. Using associativity of ∗, it can be easily checked
that if S has a unit, then it is unique.
Example 2.1. Let F be a set of sets (resp. which contains ∅ as an element) and which is closed under the disjoint sum ⊔, i.e., if A, B ∈ F such that A ∩ B = ∅, then
A ∪ B(= A ⊔ B) ∈ F . Then (F, ⊔) is a partial semigroup
(resp. partial semigroup with unit).

3
∗ L.

Poinsot, G. H. E. Duchamp and S. Goodenough are affiliated to Laboratoire d’Informatique Paris Nord, Université ParisNord 13, CNRS UMR 7030, 99 av. J.-B. Clément, F 93430 Villetaneuse, France (emails: {ghed,laurent.poinsot}@lipn-univ.paris13.fr,
goodenou@iutv.univ-paris13.fr).
† K. A. Penson is affiliated to Laboratoire de Physique Théorique
de la Matière Condensée, Université Pierre et Marie Curie, CNRS
UMR 7600, Tour 24 - 2e ét., 4 pl. Jussieu, F 75252 Paris cedex 05,
France (email: penson@lptl.jussieu.fr).
‡ Manuscript received October 05, 2009. This work was supported by the French Ministry of Science and Higher Education
under Grant ANR PhysComb.

Square-free decomposable partial semigroups
+

Let 2(N ) be the set of all finite subsets of the positive
integers N+ and (S, ⊕) be a partial semigroup with unit
+
(here denoted ǫ) equipped with a mapping σ : S → 2(N ) ,
called the (set-theoretic) support mapping. Let D be the
domain of ⊕. The triple (S, ⊕, σ) is called square-free
decomposable (SFD) if, and only if, it fulfills the two following conditions.
1

2

L. Poinsot, G. H. E. Duchamp, S. Goodenough and K.A. Penson
• Direct sum (DS):
1. σ(ω) = ∅ iff ω = ǫ;
2. D = {(ω1 , ω2 ) ∈ S 2 : σ(ω1 ) ∩ σ(ω2 ) = ∅};
3. For all ω1 , ω2 ∈ S, if (ω1 , ω2 ) ∈ D then σ(ω1 ⊕
ω2 ) = σ(ω1 ) ∪ σ(ω2 ).
• Levi’s property (LP): For every ω1 , ω2 , ω 1 , ω 2 ∈ S
such that (ω1 , ω2 ), (ω 1 , ω 2 ) ∈ D and ω1 ⊕ ω2 = ω 1 ⊕
ω 2 , there are ωij ∈ S for i = 1, 2, j = 1, 2 such that
(ωi1 , ωi2 ), (ω1j , ω2j ) ∈ D, ωi = ωi1 ⊕ωi2 and ω j = ω1j ⊕ω2j
for i = 1, 2 and j = 1, 2.

Remark 3.1. The second and third conditions of (DS)
imply that σ(ω1 ⊕ω2 ) = σ(ω1 )⊔σ(ω2 ) whenever (ω1 , ω2 ) ∈
D (which means that σ(ω1 )∩σ(ω2 ) = ∅), where ⊔ denotes
the disjoint sum.
Example 3.1. As example of this setting we have:

is equal to ǫ, then ωi 6= ωj for every i, j ∈ {1, . . . , n} such
n
G
σ(ωi ).
that i 6= j. Moreover σ(⊕ni=1 ωi ) =
i=1

(ωi )ni=1

Lemma 3.2. Let
be a finite family of elements
of S with pairwise disjoint supports. Suppose that for
i
i
i = 1, · · · , n, ωi = ⊕nk=1
ωik , where (ωik )nk=1
is a finite

n
n
i
ωik .
family of elements of S. Then ⊕i=1 ωi = ⊕i=1 ⊕nk=1

These lemmas are useful to define the sum of two or
more elements of S using respective sum decompositions.
Now, an atom in a partial semigroup with unit S is any
object ω 6= ǫ which cannot be split, formally
ω = ω1 ⊕ ω2 =⇒ ǫ ∈ {ω1 , ω2 } .

(3)

The set of all atoms is denoted by atoms(S). Whenever
the square-free decomposable semigroup S is not trivial,
i.e., reduced to {ǫ}, atoms(S) is not empty.

1. The positive square-free integers, σ(n) being the set Example 3.2. The atoms obtained from examples 3.1:
of primes which divide n, the atoms being the prime
1. The atoms of 3.1.2 are the primes.
numbers.
2. The atoms of 3.1.3 are connected graphs.
2. All the positive integeres (S = N+ ), under the usual
integer multiplication, σ(n) being the set of primes
3. The atoms of 3.1.4 are the endofunctions for which
which divide n.
the domain is a singleton.
3. Graphs, hypergraphs, (finitely) coloured, weighted
4. The atoms of 3.1.5 are the monomials.
graphs, with nodes in N+ , σ(G) being the set of nodes
The prescriptions (DS,LP) imply that decomposition
and ⊕ the juxtaposition (direct sum) when the set
of
objects into atoms always exists and is unique.
of nodes are mutually disjoint.
Proposition 3.1. Let (S, ⊕, σ) be SFD. For each ω ∈
4. The set of endofunctions f : F → F where F is a
S
there is one and only one finite set of atoms A =
finite subset of N+ .
{ω1 , · · · , ωn } such that ω = ⊕ni=1 ωi . One has A = ∅
5. The (multivariate) polynomials in N[X], X = {xi : iff ω = ǫ.
i ∈ I}, with I ⊆ N+ , being a nonempty set of (commuting or not) variables, with σ(P ) = Alph(P ) the
Exponential formula
set of indices of variables that occur in a polynomial 4
P , and ⊕ = +.
In this section we consider (S, ⊕, σ) as a square-free
6. For a given finite or denumerable field, the set of irre- decomposable partial semigroup with unit.
ducible monic polynomials is denumerable. Arrange
In the set S, objects are conceived to be “measured” by
them in a sequence (Pn )n∈N+ , then the square-free
monic (for a given order on the variables) polynomi- different parameters (data in statistical language). So, to
als is SFD, σ(P ) := {n ∈ N+ : Pn divides P } and ⊕ get a general purpose tool, we suppose that the statistics
takes its values in a (unitary) ring R of characteristic zero
being the multiplication.
that is to say which contains Q (as, to write exponential
7. Rational complex algebraic curves; σ(V ) being the generating series it is convenient to have at hand the fracset of monic irreducible bivariate polynomials van- tions 1 ). Let then c : S → R be the given statistics. For
n!
ishing on V .
F a finite set and each X ⊆ S, we define
In what follows we write ⊕ni=1 ωi instead of ω1 ⊕· · ·⊕ωn
(if n = 0, then ⊕ni=1 ωi = ǫ) and we suppose that (S, ⊕, σ)
is SFD for the two following lemmas.
Lemma 3.1. Let ω1 , . . . , ωn ∈ S such that ⊕ni=1 ωi is
defined. Then for every i, j ∈ {1, . . . , n} such that i 6= j,
it holds that σ(ωi ) ∩ σ(ωj ) = ∅. In particular, if none ωk

XF := {ω ∈ X : σ(ω) = F } .

(4)

In order to write generating series, we need
X
1. that the sums c(XF ) :=
c(ω) exist for every
ω∈XF

finite set F of N+ and every X ⊆ S;

Statistics on Graphs, Exponential Formula and Combinatorial Physics
2. that F → c(XF ) would depend only of the cardinal- where
ity of the finite set F of N+ , for each fixed X ⊆ S;

an =

X Y

fcard(p)

3

(8)

π∈Πn p∈π

3. that c(ω1 ⊕ ω2 ) = c(ω1 ).c(ω2 ).
We formalize it in
(LF) Local finiteness. — For each finite set F of N+ , the
subset SF of S is a finite set.
(Eq) Equivariance. —

with Πn being the set of all partitions of [1..n] (in particX zn
ular for n = 0, a0 = 1) and ez =
∈ R[[z]].
n!
n≥0

In what follows [1..n] denotes the interval {j ∈ N+ : 1 ≤
j ≤ n}, reduced to ∅ when n = 0. Let (S, ⊕, σ) be a
locally finite SFD and c be a multiplicative equivariant
statistics.
For every subset X of S one sets the following
card(F1 ) = card(F2 ) =⇒ c(atoms(S)F1 ) = c(atoms(S)F2 ) .
exponential
generating series
(5)
∞
(Mu) Multiplicativity. —
X
zn
.
(9)
EGF(X; z) =
c(X[1..n] )
n!
c(ω1 ⊕ ω2 ) = c(ω1 ).c(ω2 ) .
(6)
n=0
Remark 4.1. a) In fact, (LF) is a property of the set thm 4.1 (exponential formula). Let S be a locally finite
S, while (Eq) is a property of the statistics. In practice, SFD and c be a multiplicative equivariant statistics. We
we choose S which is locally finite and choose equivariant have
statistics for instance
EGF(S; z) = c(ǫ) − 1 + eEGF(atoms(S);z) ..
(10)
(number of cycles) (number of fixed points)
c(ω) = x
y
In particular if c(ǫ) = 1 (for instance if c is proper and
R is an integral domain),
for some variables x, y.
EGF(S; z) = eEGF(atoms(S);z) .
(11)
b) More generally, it is typical to take integer-valued
partial (additive) statistics c1 , · · · ci , · · · , cr (for every
Proof — Let n = 0. Then the unique element of S∅
c (ω) c (ω)
c (ω)
ω ∈ S, ci (ω) ∈ N) and set c(ω) = x11 x22 · · · xrr .
is ǫ. Therefore c(S∅ ) = c(ǫ). Now suppose that n > 0
and let ω ∈ S[1..n] . According to proposition 3.1, there
c) The set of example 3.1.2 is not locally finite, but
is a unique finite set {α1 , . . . , αk } ⊆ atoms(S) such that
other examples satisfy (LF): for instance 3.1.3 if one asks
ω = ⊕ki=1 αi . By lemma 3.1, {σ(αi ) : 1 ≤ i ≤ k} is a parthat the number of arrows and weight is finite, 3.1.1.
tition of [1..n] into k blocks. Therefore ω ∈ atoms(S)P1 ⊕
A multiplicative statistics is called proper if c(ǫ) 6= 0. · · · ⊕ atoms(S)Pk where Pi = σ(αi ) for i = 1, . . . , k. We
It is called improper if c(ǫ) = 0. In this case, for every can remark that α1 ⊕ · · · ⊕ αk is well-defined for each
(α1 , . . . , αk ) ∈ atoms(S)P1 × · · · × atoms(S)Pk since the
ω ∈ S, c(ω) = 0 as c(ω) = c(ω ⊕ ǫ) = c(ω)c(ǫ) = 0.
If R is a integral domain and if c is proper, supports are disjoint. Now, one has, thanks to the partithen c(ǫ) = 1 because c(ǫ) = c(ǫ ⊕ ǫ) = c(ǫ)2 , tions of [1..n]
therefore 1 = c(ǫ). Note that for each X ⊆ S,
G M
X
S[1..n] =
atoms(S)p
(12)
c(ǫ) if ǫ ∈ X
c(X∅ ) =
c(ω) =
. For every
p∈π
π∈Π
n
0
if ǫ 6∈ X
X Y
ω∈X∅
X
c(S[1..n] ) =
c(atoms(S)p )
(13)
finite subset X of S, we also define c(X) :=
c(ω),
ω∈X

then we have in particular c(∅) = 0 (which is not the
same as c(S∅ ) = c({ǫ}) if c is proper). The requirement
(LF) implies that for every X ⊆ S and every finite set
F of N+ , c(XF ) is defined as a sum of a finite number of terms because XF ⊆ SF , and therefore XF is finite.

π∈Πn p∈π

as, for disjoint (finite) sets F and G of N+ , it is easy to
check that c(XF ⊕ XG ) = c(XF )c(XG ) for every X ⊆ S
and because the disjoint union as only a finite number of
factors. Therefore due to equivariance of c on sets of the
form atoms(S)F , one has
X Y
Now, we are in position to state the exponential formula
c(S[1..n] ) =
c(atoms(S)[1..card(p)] ) .
(14)
as it will be used throughout the paper. Let us recall the
π∈Πn p∈π
usual exponential formula for formal power series in R[[z]]
(see [13,X
19] for more details on formal power series). Let But c(atoms(S)[1..card(p)] ) is the card(p)th coefficient of
the series EGF(atoms(S); z). Therefore due to the
f (z) =
fn z n . Then we have
usual exponential formula, EGF(S; z) = c(ǫ) − 1 +
n≥1
eEGF(atoms(S);z) . Now if c(ǫ) = 1, then we obtain
X zn
EGF(atoms(S);z)
.
(7) EGF(S; z) = e
ef =
an
n!
n≥0

4

5

L. Poinsot, G. H. E. Duchamp, S. Goodenough and K.A. Penson

Two examples

(one-parameter) groups eλΩ where Ω =

X

α(ω)ω is

ω∈HWC

an element of HWC , with all - but a finite number of
them - the complex numbers α(ω) equal to 0, and ω a
word on the alphabet {a, a† } leads to the necessity of
solving the Normal Ordering Problem, i.e., the reduction
of the powers of Ω to the form
X
Ωn =
βi,j (a† )i aj .
(18)
(15)

The examples provided here pertain to the class of labelled graphs where the “classic” exponential formula applies, namely Burnside’s Classes1 Burn a,b , defined, for
0 ≤ a < b two integers, as the class of graphs of numeric
endofunctions f such that
fa = fb

where f n denotes the nth power with respect to functional composition. Despite of its simplicity, there are
still (enumerative combinatorial) open problems for this
class and only B1,ℓ+1 gives rise to an elegant formula
[8, 19] (see also [11], for the idempotent case: ℓ = 1 and
compare to exact but non-easily tractable formulas in [4]
for the general case in the symmetric semigroup, and in
[12] for their generalization to the wreath product of the
symmetric semigroup and a finite group).

In the sequel, Normal (Ωn ) denotes such a sum. This
problem can be performed with three indices in general
and two in the case of homogeneous operators that is
operators for which the “excess” e = i − j is constant
along the monomials (a† )i aj of the support (for which
βi,j 6= 0). Thus, for
X
βi,j (a† )i aj
(19)
Ω=
i−j=e

one has, for all n ∈ N,
The second example: the class of finite parti∞
tions which can be (and should here) identified as
X
n
† ne
Normal
(Ω
)
=
(a
)
SΩ (n, k)(a† )k ak
(20)
graphs of equivalence relations on finite subsets F ⊆
+
k=0
N .
Call this class “Stirling class” as the number of such graphs with support [1..n] and k conwhen e ≥ 0, and
nected components is exactly the Stirling number of
!
∞
the second kind S2 (n, k) and, using the statistics
X
n
†
k
k
(21)
Normal (Ω ) =
SΩ (n, k)(a ) a an|e|
x(number of points) y (number of connected components) , one obk=0
tains
X
x
xn
(16) otherwise. It turns out that, when there is only one anS2 (n, k) y k = ey(e −1) .
n!
n,k≥0
nihilation, one gets a formula of the type (x, y are formal
Examples of this kind bring us to the conclusion that commutative variables)
bivariate statistics like Burna,b (n, k), S2 (n, k) or S1 (n, k)
P
X
xn
xn
SΩ (n, k) y k = g(x)ey n≥1 SΩ (n,1) n!
(22)
(Stirling numbers of the second and first kind) are better
n!
n,k≥0
understood through the notion of one-parameter group,
conversely such groups naturally arinsing in Combinatowhich is a generalization of formula (16). A complete
rial Physics lead to such statistics and new ones some of
study of such a procedure and the details to perform the
which can be interpreted combinatorially.
solution of the normal ordering problem may be found in
[5].

6

Generalized Stirling numbers in
7
Combinatorial Physics

Conclusion

In this paper, we have broadened 2, 3 the domain of application of the exponential formula, a tool originated from
statistical physics. This broadening reveals us, together
with the essence of “why this formula works”, a possibility
of extension to denominators other than the factorial and,
on the other hand, provides a link with one-parameter
groups whose infinitesimal generators are (formal) vector
The complex algebra generated by these two symbols and fields on the line. The general combinatorial theory of
this unique relation, the Heisenberg-Weyl algebra, will be the correspondence (vector fields ↔ bivariate statistics)
here denoted by HWC . The consideration of evolution is still to be done despite the fact that we have already a
wealth of results in this direction.
1
In Quantum Mechanics, many tools boil down to the consideration of creation and annihilation operators which
will be here denoted respectively a† and a. These two
symbols do not commute and are subject to the unique
relation
[a, a† ] = 1 .
(17)

The name is related to the notion of free Burnside semigroups,
namely the quotient of the free semigroup A+ , where A is a finite
alphabet, by the the smallest congruence that contains the relators
ω n+m = ω n , ω ∈ A+ . For more details see [15].

2 A part of our setting can be reformulated in the categorical
context [2, 3]
3 Another direction is the q-exponential formula [10, 16].

Statistics on Graphs, Exponential Formula and Combinatorial Physics

Acknowledgements
We would like to thank Christian Krattenthaler (from
Wien) for fruitful discussions.
The research of this work was supported, in part, by the
Agence Nationale de la Recherche (Paris, France) under
Program No. ANR-08-BLAN-0243-2. We would like also
to acknowledge support from “Projet interne au LIPN
2009” “Polyzêta functions”.

References
[1] R. H. Bruck, A survey of binary systems, Ergebnisse der Mathematik und ihrer Grenzgebiete, new series, vol. 20, BerlinGttingen-Heidelberg, Springer, 1958.
[2] F. Bergeron, G. Labelle, and P. Leroux, Combinatorial Species
and Tree-Like Structures, Cambridge University Press, 1999.
[3] P. J. Cameron, C. Krattenthaler, and T. W. Müller, Decomposable functors and the exponential principle II, to appear.
[4] A. Dress and T. W. Müller, Decomposable functors and the exponential principle, Advances in Mathematics, vol. 129, pp. 188221, 1997.
[5] G. H. E. Duchamp, K. A. Penson, A. I. Solomon, A. Horzela and
P. Blasiak, One-parameter groups and combinatorial physics, in
Proc. of the Third International Workshop on Contemporary
Problems in Mathematic Physics (COPROMAPH3), PortoNovo (Benin), 2003. arXiv:quant-ph/0401126
[6] S. Eilenberg, Automata, Languages and Machines - volume A,
Academic Press, 1974.
[7] P. Flajolet, R. Sedgewick, Analytic Combinatorics, Cambridge
University Press, 2008.
[8] I. P. Goulden and D. M. Jackson, Combinatorial enumeration,
John Wiley & Sons, Inc., 1983.
[9] A. Joyal, Une théorie combinatoire des séries formelles, Advances in Mathematics, vol. 42, pp. 1-82, 1981.
[10] I. M. Gessel, A q-analog of the exponential formula, Discrete
Mathematics 306 (2006).
[11] B. Harris and L. Schoenfeld, The number of idempotent elements in symmetric semigroups, Journal of Combinatorial Theory, Series A, vol. 3, pp. 122-135, 1967.
[12] C. Krattenthaler and T. W. Müller, Equations in finite semigroups: explicit enumeration and asymptotics of solution numbers, Journal of Combinatorial Theory, Series A, vol. 105,
pp. 291-334, 2004.
[13] S. Lang, Complex analysis, Springer, 1999.
[14] E. S. Ljapin and A. E. Evseev, The Theory of Partial Algebraic
Operations, Kluwer Academic, 1997.
[15] A. Pereira do Lago and I. Simon, Free Burnside Semigroups,
Theoretical Informatics and Applications, vol. 35, pp. 579-595,
2001.
[16] C. Quesne, Disentangling q-Exponentials: A General Approach, International Journal of Theoretical Physics, Vol. 43,
No. 2, February 2004
[17] R. J. Ridell and G. E. Uhlenbeck, On the theory of the virial
development of the equation of state of monomatomic gases, J.
Chem. Phys., vol. 21, pp. 2056-2064, 1953.
[18] G. Segal, Configuration-spaces and iterated loop-spaces, Inventiones Mathematicae, vol. 21 (3), pp. 213-221, 1973.
[19] R. Stanley, Enumerative Combinatorics - Volume I, in Studies
in Advanced Mathematics, vol. 49, Cambridge University Press,
1997.
[20] J. Touchard, Sur les cycles des substitutions, Acta Mathematica, vol. 70, pp. 243-297, 1939.

5

