Journal of Nonlinear Systems and Applications () Copyright \begin{matrix}c \\ ◯ \end{matrix} 2009 Watam Press http://www.watam.org/JNSA/

STATISTICS ON GRAPHS, EXPONENTIAL FORMULA AND COMBINATORIAL PHYSICS

Laurent Poinsot, Gérard H. E. Duchamp, Silvia Goodenough and Karol A. Penson ^{∗}^{†}^{‡}

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 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 Introduction

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 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

(x, y, z) ↦ (x ∗ y) ∗ z and (x, y, z) ↦ 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

(x_{1}, ⋯, x_{n}) ↦ E_{T} (x_{1}, ⋯, x_{n})  (2)

obtained by evaluating the expression formed by labelling by x_{i} (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 x_{1} ∗ ⋯ ∗ x_{n} their common value. In this paper we restrict our attention to commutative semigroups. By this we mean that the value x_{1} ∗ ⋯ ∗ x_{n} does not depend on the relative order of the x_{i}. 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 Square-free decomposable partial semigroups

Let 2^{(ℕ^{+})} be the set of all finite subsets of the positive integers ℕ^{+} and (S, ⊕) be a partial semigroup with unit (here denoted ϵ) equipped with a mapping σ : S → 2^{(ℕ^{+})}, 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.

∗L. Poinsot, G. H. E. Duchamp and S. Goodenough are affiliated to Laboratoire d’Informatique Paris Nord, Université Paris-Nord 13, CNRS UMR 7030, 99 av. J.-B. Clé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 Théorique de la Matière Condensée, Université Pierre et Marie Curie, CNRS UMR 7600, Tour 24 - 2e é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.

• 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 ω_{i}^{j} ∈ S for i = 1, 2, j = 1, 2 such that (ω_{i}^{1}, ω_{i}^{2}), (ω_{1}^{j}, ω_{2}^{j}) ∈ D, ω_{i} = ω_{i}^{1}⊕ω_{i}^{2} and ω^{j} = ω_{1}^{j}⊕ω_{2}^{j} 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:

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

2. All the positive integeres (S = ℕ^{+}), under the usual integer multiplication, σ(n) being the set of primes which divide n.

3. Graphs, hypergraphs, (finitely) coloured, weighted graphs, with nodes in ℕ^{+}, σ(G) being the set of nodes and ⊕ the juxtaposition (direct sum) when the set of nodes are mutually disjoint.

4. The set of endofunctions f : F → F where F is a finite subset of ℕ^{+}.

5. The (multivariate) polynomials in ℕ[X], X = {x_{i} : i ∈ I}, with I ⊆ ℕ^{+}, being a nonempty set of (commuting or not) variables, with σ(P) = Alph(P) the set of indices of variables that occur in a polynomial P, and ⊕ = +.

6. For a given finite or denumerable field, the set of irreducible monic polynomials is denumerable. Arrange them in a sequence (P_{n})_{n∈ℕ^{+}}, then the square-free monic (for a given order on the variables) polynomials is SFD, σ(P) := {n ∈ ℕ^{+} : P_{n} divides P } and ⊕ being the multiplication.

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

In what follows we write ⊕_{i=1}^{n}ω_{i} instead of ω_{1} ⊕⋯⊕ω_{n} (if n = 0, then ⊕_{i=1}^{n}ω_{i} = ϵ) and we suppose that (S, ⊕, σ) is SFD for the two following lemmas.

Lemma 3.1. Let ω_{1}, …, ω_{n} ∈ S such that ⊕_{i=1}^{n}ω_{i} is defined. Then for every i, j ∈ {1, …, n} such that i ≠ j, it holds that σ(ω_{i}) ∩ σ(ω_{j}) = ∅. In particular, if none ω_{k} is equal to ϵ, then ω_{i} ≠ ω_{j} for every i, j ∈ {1, …, n} such

that i ≠ j. Moreover σ(⊕_{i=1}^{n}ω_{i}) = ⨆_{i=1}^{n} σ(ω_{i}).

Lemma 3.2. Let (ω_{i})_{i=1}^{n} be a finite family of elements of S with pairwise disjoint supports. Suppose that for i = 1, ⋯, n, ω_{i} = ⊕_{k=1}^{n_{i}}ω_{i}^{k}, where (ω_{i}^{k})_{k=1}^{n_{i}} is a finite family of elements of S. Then ⊕_{i=1}^{n}ω_{i} = ⊕_{i=1}^{n} (⊕_{k=1}^{n_{i}}ω_{i}^{k}).

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 ω ≠ ϵ 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.

Example 3.2. The atoms obtained from examples 3.1:

1. The atoms of 3.1.2 are the primes.

2. The atoms of 3.1.3 are connected graphs.

3. The atoms of 3.1.4 are the endofunctions for which the domain is a singleton.

4. The atoms of 3.1.5 are the monomials.

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

Proposition 3.1. Let (S, ⊕, σ) be SFD. For each ω ∈ S there is one and only one finite set of atoms A = {ω_{1}, ⋯, ω_{n}} such that ω = ⊕_{i=1}^{n}ω_{i}. One has A = ∅ iff ω = ϵ.

4 Exponential formula

In this section we consider (S, ⊕, σ) as a square-free decomposable partial semigroup with unit.

In the set S, 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 its values in a (unitary) ring R of characteristic zero that is to say which contains ℚ (as, to write exponential generating series it is convenient to have at hand the fractions \frac{1}{n!}). Let then c : S → R be the given statistics. For F a finite set and each X ⊆ S, we define

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

In order to write generating series, we need

1. that the sums c(X_{F}) := ∑_{ω∈X_{F}} c(ω) exist for every

finite set F of ℕ^{+} and every X ⊆ S; 2. that F → c(X_{F}) would depend only of the cardinal-

ity of the finite set F of ℕ^{+}, for each fixed X ⊆ S;

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

We formalize it in

(LF) Local finiteness. — For each finite set F of ℕ^{+}, the subset S_{F} of S is a finite set. (Eq) Equivariance. —

card(F_{1}) = card(F_{2}) ⟹ c(atoms(S)_{F_{1}}) = c(atoms(S)_{F_{2}}) .

(5)

(Mu) Multiplicativity. —

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

Remark 4.1. a) In fact, (LF) is a property of the set S, while (Eq) is a property of the statistics. In practice, we choose S 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 ω ∈ S, c_{i}(ω) ∈ ℕ) and set c(ω) = x_{1}^{c_{1}(ω)}x_{2}^{c_{2}(ω)} ⋯ x_{r}^{c_{r}(ω)}.

c) The set of example 3.1.2 is not locally finite, but other examples satisfy (LF): for instance 3.1.3 if one asks that the number of arrows and weight is finite, 3.1.1.

A multiplicative statistics is called proper if c(ϵ) ≠ 0. It is called improper if c(ϵ) = 0. In this case, for every ω ∈ S, c(ω) = 0 as c(ω) = c(ω ⊕ ϵ) = c(ω)c(ϵ) = 0.

If R is a integral domain and if c is proper, then c(ϵ) = 1 because c(ϵ) = c(ϵ ⊕ ϵ) = c(ϵ)^{2}, therefore 1 = c(ϵ). Note that for each X ⊆ S,

c(X_{∅}) = ∑_{ω∈X_{∅}} c(ω) = \{ \begin{matrix}c(ϵ) & if & ϵ ∈ X \\ 0 & if & ϵ ∉ X \end{matrix} . For every

finite subset X of S, we also define c(X) := ∑_{ω∈X} c(ω),

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 ℕ^{+}, c(X_{F}) is defined as a sum of a finite number of terms because X_{F} ⊆ S_{F}, and therefore X_{F} is finite.

Now, we are in position to state the exponential formula as it will be used throughout the paper. Let us recall the usual exponential formula for formal power series in R[[z]] (see [13, 19] for more details on formal power series). Let f(z) = ∑_{n≥1} f_{n}z^{n}. Then we have

e^{f} = ∑_{n≥0} a_{n} \frac{z^{n}}{n!}  (7)

where

a_{n} = ∑_{π∈Π_{n}} ∏_{p∈π} f_{card(p)}  (8)

with Π_{n} being the set of all partitions of [1..n] (in partic-

ular for n = 0, a_{0} = 1) and e^{z} = ∑_{n≥0} \frac{z^{n}}{n!} ∈ R[[z]].

In what follows [1..n] denotes the interval {j ∈ ℕ^{+} : 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 exponential generating series

EGF(X; z) = ∑_{n=0}^{∞} c(X_{[1..n]})\frac{z^{n}}{n!} .  (9)

thm 4.1 (exponential formula). Let S be a locally finite SFD and c be a multiplicative equivariant statistics. We have

EGF(S; z) = c(ϵ) − 1 + e^{EGF(atoms(S);z)} ..  (10)

In particular if c(ϵ) = 1 (for instance if c is proper and R is an integral domain),

EGF(S; z) = e^{EGF(atoms(S);z)} .  (11)

Proof — Let n = 0. Then the unique element of S_{∅} is ϵ. Therefore c(S_{∅}) = c(ϵ). Now suppose that n > 0 and let ω ∈ S_{[1..n]}. According to proposition 3.1, there is a unique finite set {α_{1}, …, α_{k}} ⊆ atoms(S) such that ω = ⊕_{i=1}^{k}α_{i}. By lemma 3.1, {σ(α_{i}) : 1 ≤ i ≤ k} is a partition of [1..n] into k blocks. Therefore ω ∈ atoms(S)_{P_{1}} ⊕ ⋯ ⊕ atoms(S)_{P_{k}} where P_{i} = σ(α_{i}) for i = 1, …, k. We can remark that α_{1} ⊕ ⋯ ⊕ α_{k} is well-defined for each (α_{1}, …, α_{k}) ∈ atoms(S)_{P_{1}} × ⋯ × atoms(S)_{P_{k}} since the supports are disjoint. Now, one has, thanks to the partitions of [1..n]

S_{[1..n]} = ⨆_{π∈Π_{n}} ⨁_{p∈π} atoms(S)_{p}  (12)
c(S_{[1..n]}) = ∑_{π∈Π_{n}} ∏_{p∈π} c(atoms(S)_{p})  (13)

as, for disjoint (finite) sets F and G of ℕ^{+}, it is easy to check that c(X_{F} ⊕ X_{G}) = c(X_{F})c(X_{G}) 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

c(S_{[1..n]}) = ∑_{π∈Π_{n}} ∏_{p∈π} c(atoms(S)_{[1..card(p)]}) .  (14)

But c(atoms(S)_{[1..card(p)]}) is the card(p)th coefficient of the series EGF(atoms(S); z). Therefore due to the usual exponential formula, EGF(S; z) = c(ϵ) − 1 + e^{EGF(atoms(S);z)}. Now if c(ϵ) = 1, then we obtain EGF(S; z) = e^{EGF(atoms(S);z)}.

5 Two examples

The examples provided here pertain to the class of labelled graphs where the “classic” exponential formula applies, namely Burnside’s Classes^{1} Burn_{a,b}, defined, for 0 ≤ a < b two integers, as the class of graphs of numeric endofunctions f such that

f^{a} = f^{b}  (15)

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 B_{1,ℓ+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).

The second example: the class of finite partitions which can be (and should here) identified as graphs of equivalence relations on finite subsets F ⊆ ℕ^{+}. Call this class “Stirling class” as the number of such graphs with support [1..n] and k connected components is exactly the Stirling number of the second kind S_{2}(n, k) and, using the statistics x^{(number of points)}y^{(number of connected components)}, one obtains

∑_{n,k≥0} S_{2}(n, k)\frac{x^{n}}{n!} y^{k} = e^{y(e^{x}−1)} .  (16)

Examples of this kind bring us to the conclusion that bivariate statistics like Burn_{a,b}(n, k), S_{2}(n, k) or S_{1}(n, k) (Stirling numbers of the second and first kind) are better understood through the notion of one-parameter group, conversely such groups naturally arinsing in Combinatorial Physics lead to such statistics and new ones some of which can be interpreted combinatorially.

6 Generalized Stirling numbers in Combinatorial Physics

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 complex algebra generated by these two symbols and this unique relation, the Heisenberg-Weyl algebra, will be here denoted by HW_{ℂ}. The consideration of evolution (one-parameter) groups e^{λΩ} where Ω = ∑_{ω∈HW_{ℂ}} α(ω)ω is

an element of HW_{ℂ}, 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

Ω^{n} = ∑ β_{i,j}(a^{†})^{i}a^{j} .  (18)

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}a^{j} of the support (for which β_{i,j} ≠ 0). Thus, for

Ω = ∑_{i−j=e} β_{i,j}(a^{†})^{i}a^{j}  (19)

one has, for all n ∈ ℕ,

Normal(Ω^{n}) = (a^{†})^{ne} ∑_{k=0}^{∞} S_{Ω}(n, k)(a^{†})^{k}a^{k}  (20)

when e ≥ 0, and

Normal(Ω^{n}) = (∑_{k=0}^{∞} S_{Ω}(n, k)(a^{†})^{k}a^{k}) a^{n|e|}  (21)

otherwise. It turns out that, when there is only one annihilation, one gets a formula of the type (x, y are formal commutative variables)

∑_{n,k≥0} S_{Ω}(n, k)\frac{x^{n}}{n!} y^{k} = g(x)e^{y ∑_{n≥1} S_{Ω}(n,1) \frac{x^{n}}{n!}}  (22)

which is a generalization of formula (16). A complete study of such a procedure and the details to perform the solution of the normal ordering problem may be found in [5].

7 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 fields on the line. The general combinatorial theory of the correspondence (vector fields ↔ bivariate statistics) is still to be done despite the fact that we have already a wealth of results in this direction.

1The 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].

2A part of our setting can be reformulated in the categorical context [2, 3]

3Another direction is the q-exponential formula [10, 16].

Statistics on Graphs, Exponential Formula and Combinatorial Physics 5

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” “Polyzêta functions”.

References

[1] R. H. Bruck, A survey of binary systems, Ergebnisse der Mathematik und ihrer Grenzgebiete, new series, vol. 20, Berlin-Gttingen-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. Müller, Decomposable functors and the exponential principle II, to appear.

[4] A. Dress and T. W. Müller, Decomposable functors and the exponential principle, Advances in Mathematics, vol. 129, pp. 188-221, 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), Porto-Novo (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 théorie combinatoire des sé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. Mü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.