Séminaire Lotharingien de Combinatoire 54 (2007), Article B54m

GRAPH WEIGHTS ARISING FROM MAYER’S THEORY OF CLUSTER INTEGRALS

G. Labelle, P. Leroux and M. G. Ducharme

LaCIM, Université du Québec à Montréal

A notre très bon ami Xavier Viennot

Abstract. We study graph weights (i.e., graph invariants) which arise naturally in Mayer’s theory of cluster integrals in the context of a non-ideal gas. Various choices of the interaction potential between two particles yield various graph weights w(g). For example, in the case of the Gaussian interaction, the so-called Second Mayer weight w(c) of a connected graph c is closely related to the graph complexity, i.e., the number of spanning trees, of c. We give special attention to the Second Mayer weight w(c) which arises from the hard-core continuum gas in one dimension. This weight is a signed volume of a convex polytope P(c) naturally associated with c. Among our results are the values w(c) for all 2-connected graphs c of size at most 6, in Appendix B, and explicit formulas for three infinite families: complete graphs, (unoriented) cycles and complete graphs minus an edge.

Introduction.

Graph weights can be defined as functions on (simple, finite) graphs taking scalar or polynomial values and which are invariant under isomorphisms, i.e., under vertex relabellings. Since most graphical concepts share this invariance property, examples of graph weights abound. For a graph g, α(g) = the independence number of g and χ_{g}(λ) = the chromatic polynomial of g are examples of graph weights. Another example is given by the graph complexity of G, denoted by γ(g), which is defined as the number of maximal spanning forests of g.

In the present paper, we study graph weights which arise naturally in Mayer’s theory of cluster integrals in the context of a non-ideal gas in a vessel V ⊆ IR^{d}. Various choices of the dimension d and of the interaction potential φ(r) between two particles at distance r yield various graph weights w(g). In the thermodynamic limit, the gas pressure is closely related to the exponential generating function C_{w}(z) of connected graphs c weighted by the so-called Second Mayer weight w(c). There has been continued interest from the physicists for Mayer and virial expansions. See for example Clisby and McCoy [6] and the references therein. While physicists are interested in summing the weights of all connected or 2-connected graphs of a given order, the present paper focuses on individual graph contributions and their combinatorial significance.

In the first section, we review Mayer’s theory following the lines of Uhlenbeck and Ford [31] and Leroux [16]. See also Thompson [30]. Special emphasis is put on the existence conditions of the thermodynamic limit which defines the second Mayer weight w(c) of a connected graph c and on its property of block multiplicativity. A complete proof for the existence of the thermodynamic limit, not found in [31] and [16] is given in Appendix A. Also reviewed are the functional relations between weighted connected graphs and 2-connected graphs.

The example of the Gaussian interaction, is studied in Section 2. In this case, the weight w(c) involves three block multiplicative parameters of the connected graph c, namely the number of vertices minus 1, the number of edges e(c) and the graph complexity γ(c) which is the number of spanning trees of c. The proof of this known result is reviewed here. It uses the multidimensional Gaussian integral and the Theorem of Kirchhoff relating γ(c) to the determinant of a matrix K associated to c. Moreover, we give an extension of the Gaussian weight which refines γ(c) in order to reflect the degree sequence of the spanning subtrees of c.

The last section is devoted to the Second Mayer weight w(c) which arises from the hard-core continuum gas in one dimension. This weight is a signed volume of a convex polytope P(c) naturally associated with c. It is known that in this case, the generating function C_{w}(z) (the pressure) is equal to the Lambert function L(z) which is defined by the functional equation L(z) exp(L(z)) = z. We give a combinatorial proof of this result. This implies that the total weight of all connected graphs over a set of size N is (−N)^{N−1} and that of all 2-connected graphs is −N(N − 2)!. Naturally, it raises the question of finding a combinatorial explanation of these formulas and of computing or understanding better the weight of individual connected graphs and perhaps expressing it in terms of other graph invariants. We have only partial answers to these questions to offer. First, we have computed the volume Vol(P(c)) of all 2-connected graphs c of size at most 6, together with the Ehrhart polynomial, using the fact that the vertices of the polytope P(c) have integer coordinates. This data is given in Appendix B. The weight of any connected graph c whose blocks have size at most 6 can then be deduced by block multiplicativity. Secondly, we have found explicit formulas for three infinite families of connected graphs namely complete graphs, (unoriented) cycles and complete graphs minus an edge. An alternate useful tool, a decomposition of the polytope P(c) into a certain number of (N − 1)-dimensional simplexes, of volume 1/(N − 1)! is exploited in the final subsection.

Acknowledgements. This paper has benefited from discussions with numerous colleagues, in particular at the Banff International Research Station Workshop on Statistical Mechanics of Polymer Models in May 2003 and at the 54^{th} Séminaire Lotharingien de Combinatoire, Lucelle, France, in April 2005, where this work was presented. We would like to acknowledge particularly the contribution of George Andrews, Mireille Bousquet-Mélou, David Brydges, Frédéric Chapoton, Bodo Lass, Alan Sokal, Xavier Viennot, Herbert Wilf and the two referees.

1. A review of Mayer’s theory of cluster integrals

1.1. The grand canonical partition function. In the context of a non-ideal gas with N particles in a vessel V included in IR^{d}, we represent the particles’ positions by vectors x⃗_{1}, …, x⃗_{N}. If we consider that the system is free from external influences, the partition function is defined as

Z(V, T, N) = \frac{1}{N!λ^{dN}} ∫_{V} ⋯ ∫_{V} exp (−β ∑_{i<j} φ(|x⃗_{i} − x⃗_{j}|)) dx⃗_{1} … dx⃗_{N}, (1)

where λ and β depend on the temperature T and where the interaction between two particles at distance r is expressed by a potential function φ(r) as illustrated in Figure 1a).

Figure 1. a) the function φ(r) b) the function f(r)

We also define the grand canonical partition function as the generating series of the partition functions:

Z_{gr}(V, T, z) = ∑_{n=0}^{∞} Z(V, T, N)(λ^{d}z)^{N},  (2)

where z is called the fugacity or the activity of the system. The generating function identities that we consider are in the sense of formal power series in the activity z. For issues of convergence, see Ruelle [24]. The system’s macroscopic parameters can be described using the grand canonical partition function. In particular, the pressure P, the mean number of particles N̄ and the density ρ can be written as

\frac{P}{kT} = \frac{1}{V} log Z_{gr}(V, T, z), N̄ = z \frac{∂}{∂z} log Z_{gr}(V, T, z) and ρ := \frac{N̄}{V} ,  (3)

where V is also used as the volume of the vessel.

1.2. Mayer’s idea. In order to study these functions, Mayer (1940) sets

1 + f_{ij} = exp (−βφ(|\overrightarrow{x_{i}} − \overrightarrow{x_{j}}|)),  (4)

where f_{ij} = f(|\overrightarrow{x_{i}} − \overrightarrow{x_{j}}|). The general form of Mayer’s function

f(r) = exp(−βφ(r)) − 1,  (5)

compared to the potential function φ(r), is shown in Figure 1. Since

∏_{1≤i<j≤N}(1 + f_{ij}) = ∑_{g∈G[N]} ∏_{{i,j}∈g} f_{ij},  (6)

where G[N] denotes the set of all (simple) graphs over the set of vertices [N] = {1, 2, …, N}, the partition function Z(V, T, N) becomes

Z(V, T, N) = \frac{1}{N!λ^{dN}} ∫_{V^{N}} exp (−β ∑_{i<j} φ(|\overrightarrow{x_{i}} − \overrightarrow{x_{j}}|))d\overrightarrow{x_{1}} ⋯ d\overrightarrow{x_{N}}

= \frac{1}{N!λ^{dN}} ∫_{V^{N}} ∏_{1≤i<j≤N} (1 + f_{ij}) d\overrightarrow{x_{1}} ⋯ d\overrightarrow{x_{N}}

= \frac{1}{N!λ^{dN}} ∑_{g∈G[N]} ∫_{V^{N}} ∏_{\{i,j\}∈g} f_{ij} d\overrightarrow{x_{1}} ⋯ d\overrightarrow{x_{N}}

= \frac{1}{N!λ^{dN}} ∑_{g∈G[N]} W (g),  (7)

where the weight W (g) of a graph g is given by the integral

W (g) = ∫_{V^{N}} ∏_{\{i,j\}∈g} f_{ij}d\overrightarrow{x_{1}} ⋯ d\overrightarrow{x_{N}}.  (8)

This is the First Mayer weight of a graph g. It should be clear that W (g) is invariant under graph isomorphisms, since any relabelling defined by a vertex bijection also induces a change of variables whose Jacobian is the determinant of the corresponding permutation matrix and which transforms one integral into the other.

In terms of W (g), the grand-canonical function becomes

Z_{gr}(V, T, z) = ∑_{N=0}^{∞} Z(V, T, N)(λ^{d}z)^{N}

= ∑_{N=0}^{∞} \frac{1}{N!λ^{dN}} ∑_{g∈G[N]} W (g)(λ^{d}z)^{N}

= ∑_{N=0}^{∞} \frac{1}{N!} ∑_{g∈G[N]} W (g)z^{N}

= G_{W} (z),  (9)

the exponential generating series of graphs weighted by the function W.

Proposition 1. W (g), the First Mayer Weight of a simple graph g, is multiplicative on the connected components of g. In other words, for c_{1}, c_{2}, …, c_{m} the m connected components of g, we have

W (g) = W (c_{1})W (c_{2}) … W (c_{m}).

Proof. Since the connected components of g are disjoint, we can label the vertices in such a way that 1 to k_{1} are in the component c_{1}, k_{1} + 1 to k_{2} in c_{2}, and so on until k_{m−1} + 1 to k_{m} = N in c_{m}. We then have

W (g) = ∫_{V^{N}} ∏_{{i,j}∈g} f_{ij}dx⃗_{1} … dx⃗_{N}

= ∫_{V^{N}} ∏_{{i,j}∈c_{1}} f_{ij} ∏_{{i,j}∈c_{2}} f_{ij} … ∏_{{i,j}∈c_{m}} f_{ij}dx⃗_{1} … dx⃗_{N}

= ∫_{V^{k_{1}}} ∏_{{i,j}∈c_{1}} f_{ij}dx⃗_{1} … dx⃗_{k_{1}} × ∫_{V^{k_{2}−k_{1}}} ∏_{{i,j}∈c_{2}} f_{ij}dx⃗_{k_{1}+1} … dx⃗_{k_{2}}×

⋯ × ∫_{V^{km−k_{m−1}}} ∏_{{i,j}∈c_{m}} f_{ij}dx⃗_{k_{m−1}+1} … dx⃗_{N}

= W (c_{1}) · W (c_{2}) · . . . · W (c_{m}).  (10)
□

Since W is multiplicative on connected components, the exponential formula can be used:

G_{W} (z) = exp(C_{W} (z)),  (11)

where C denotes the species (class) of connected graphs, so that

log G_{W} (z) = C_{W} (z)
= ∑_{N=1}^{∞} \frac{1}{N!} ∑_{c∈C[N]} W (c)z^{N}.  (12)

Corollary 2. The pressure of the system can be expressed in terms of the exponential generating function of connected graphs weighted by W. More precisely, we have

\frac{P}{kT} = \frac{1}{V} log Z_{gr}(V, T, z) = \frac{1}{V} C_{W} (z).

□

1.3. The thermodynamic limit w(c). Let c be a connected graph over {1, 2, …, N}. The Second Mayer weight w(c) is defined as the limit

w(c) = lim_{V →∞} \frac{1}{V} W (c)
= lim_{V →∞} \frac{1}{V} ∫_{V^{N}} ∏_{\{i,j\}∈c} f_{ij} dx⃗_{1} … dx⃗_{N}.  (13)

Here, V going to infinity has the following meaning. The vessel V ∈ IR^{d} must contain a ball B(0, R) centered at the origin, with radius R ∈ ]0, ∞). V goes to infinity means that R goes to infinity. Let us recall that the symbol V denotes both the vessel and the volume.

The following proposition gives us the conditions on Mayer’s function f for w(c) to exist.

Proposition 3. If the function f : [0, ∞) → IR is integrable and bounded and if

∫_{0}^{∞} r^{d−1}|f(r)| dr < ∞,  (14)

for example if |f(r)| = O(1/r^{d+ϵ}), r → ∞, for some ϵ > 0, then for any fixed x⃗_{N} ∈ IR^{d}, the function Fx⃗_{N} : IR^{d·(N−1)} → IR, defined by

Fx⃗_{N} (x⃗_{1}, …, x⃗_{N−1}) = ∏_{{i,j}∈c} f(|x⃗_{i} − x⃗_{j}|) = ∏_{{i,j}∈c} f_{ij}  (15)

is integrable over (IR^{d})^{N−1} and its integral is independent of x⃗_{N}. Moreover the limit (13) exists and is equal to

w(c) = ∫_{(IR^{d})^{N−1}} ∏_{{i,j}∈c; x⃗_{N} =0} f_{ij} dx⃗_{1} … dx⃗_{N−1}.  (16)

Proof. See Appendix A. □

We will often use equation (16) as an alternate definition for w(c). It also follows from the proof of Proposition 3 that the rooting at the vertex N, for which x⃗_{N} is set equal to 0 in (16), can be replaced by any other vertex J. For example, with J = 1, the formula becomes

w(c) = ∫_{(IR^{d})^{N−1}} ∏_{{i,j}∈c; x⃗_{1}=0} f_{ij} dx⃗_{2} … dx⃗_{N}.  (17)

In the thermodynamic limit, the pressure is given by

\frac{P}{kT} = lim_{V →∞} \frac{1}{V} log Z_{gr}(V, T, z)

= lim_{V →∞} \frac{1}{V} C_{W} (z)

= ∑_{N=1}^{∞} \frac{1}{N!} ∑_{c∈C[N]} lim_{V →∞} \frac{1}{V} W (c)z^{N}

= ∑_{N=1}^{∞} \frac{1}{N!} ∑_{c∈C[N]} w(c)z^{N}.

In other words,

\frac{P}{kT} = C_{w}(z).  (18)

Proposition 4. In the thermodynamic limit, the pressure of the system is given directly in terms of the exponential generating function of connected graphs weighted by the Second Mayer Weight w(c), according to formula (18).

A 2-connected graph is defined as a connected graph that stays connected if any one of its vertices is removed. This includes the complete graph on two vertices K_{2}. A block in a connected graph is a maximal 2-connected subgraph. A cutpoint in a connected graph is a vertex whose removal disconnects the graph. Any connected graph c can be uniquely decomposed into 2-connected graphs (the blocks of c) which are linked together by the cutpoints of c in a tree-like fashion (see [1], p.266). This decomposition partitions the edges of c. A leaf-block b is a block of c which is linked to the rest of the graph by only one cutpoint p. In that case, the graph c \ b, which is obtained from c by removing all edges and all vertices of b except the cutpoint p, remains connected.

Proposition 5. The second Mayer weight w is block-multiplicative. More precisely, for any connected graph c whose blocks are b_{1}, b_{2}, …, b_{m}, we have

w(c) = w(b_{1})w(b_{2}) … w(b_{m}).  (19)

Proof. The proof is by induction on the number of blocks in c. If c is composed of exactly one block, the multiplicativity is trivial. Let us suppose that the property is true for all connected graphs composed of m blocks, and let us consider a connected graph c composed of m + 1 blocks. Its vertices are labelled from 1 to N. We choose in c a leaf-block that we denote by b, and call S the set of its vertices. Without loss of generality, we can assume that the cutpoint linking b to c is labelled N, and that S = {1, 2, …, k, N}, |S| = k + 1. Let us name b_{1}, b_{2}, …, b_{m} the other blocks of c. We then have, using (16),

w(c) = ∫_{IR_{d(N−1)}} ∏_{{i,j}∈c; x⃗_{N} =0} f_{ij} dx⃗_{1}dx⃗_{2} … dx⃗_{N−1}

= ∫_{IR_{d(N−1)}} ∏_{{i,j}∈b; x⃗_{N} =0} f_{ij} ∏_{{i,j}∈c\b; x⃗_{N} =0} f_{ij} dx⃗_{1}dx⃗_{2} … dx⃗_{N−1}

= ∫_{IR_{dk}} ∏_{{i,j}∈b; x⃗_{N} =0} f_{ij} dx⃗_{1}dx⃗_{2} … dx⃗_{k}

× ∫_{IR_{d(N−k−1)}} ∏_{{i,j}∈c\b; x⃗_{N} =0} f_{ij} dx⃗_{k+1}dx⃗_{k+2} … dx⃗_{N−1}

= w(b) · w(c \ b).  (20)

Since c \ b is made of m blocks, the induction hypothesis can be used and we have

w(c) = w(b) · w(b_{1}) · w(b_{2}) · . . . · w(b_{m}),  (21)

proving that the w(c) function is block-multiplicative. □

1.3.1. The virial expansion. In order to better explain the thermodynamic behaviour of non ideal gases, Kamerlingh Onnes proposed, in 1901, a series expansion of the form

\frac{P}{kT} = ρ + γ_{2}(T)ρ^{2} + γ_{3}(T)ρ^{3} + ⋯,  (22)

where ρ = \frac{\overline{N}}{V} is the density, called the virial expansion. A benefit of Mayer’s theory is a formal derivation of this expansion and an interpretation of the virial coefficients γ_{n}(T), n ≥ 2, as the total weight of all (labelled) 2-connected graphs with n vertices (see [31] and [16]):

γ_{n}(T) = −\frac{(n − 1)}{n!}|B[n]|_{w}.  (23)

1.4. Functional equation for weighted connected graphs. The block-multi-plicativity of w(c) allows us to establish a functional relation between the species C_{w} of weighted connected graphs, and B_{w}, of weighted 2-connected graphs. But first, let us recall a few notions in the theory of species.

For any species F, the derivative F′ of F is the species whose structures on any set U are F -structures on the set U ∪{∗}, where ∗ is a non-labelled external element. See [1] for more information about species. The rooting operation F ↦ F^{•} consists of choosing a “root” (i.e., any element) in the set on which the F -structure is built. It can be defined as

F^{•} = X · F′,  (24)

where X denotes the species of one-element sets. Notice that in terms of exponential generating series we have F′(z) = \frac{d}{dz}F (z) and F^{•}(z) = zF′(z).

Theorem 6 below, and its weighted version theorem 7, can be found in various forms in the mathematical and physical literature (see [1], [9], [10], [11], [12], [15], [17], [21], [22], [25], [31]).

Theorem 6. Let B be a particular class of 2-connected graphs and C_{B} the species of connected graphs with all blocks in B. Then we have the combinatorial functional equation

C′_{B} = E(B′(C_{B}^{•})),  (25)

where E denotes the species of sets, and, in terms of exponential generating functions,

C′_{B}(z) = exp (B′(C_{B}^{•}(z))) .  (26)

Figure 2. C′_{B} = E(B′(C_{B}^{•}))

Proof. Figure 2 will help us understand the isomorphism between the two classes of structures. On the left hand side of the figure we have a C′_{B}-structure, which is a C_{B}-structure over a set U ∪ {∗}. On the right hand side, the ∗ vertex has been split between the blocks to which it belongs. The vertices in pale colour are different from the others because they are forming B′-structures with the ∗ vertices. Also each of these pale colour vertices is the root of a C_{B}^{•}-structure, circled by a dotted line. We thus see that the B′-structures are built on a set of C_{B}^{•}-structures.

Therefore we have a bijection between the C′_{B}-structures on U and sets of B′(C_{B}^{•})- structures on U. Since this construction commutes with any relabelling, we have a species isomorphism which is expressed by (25). Formula (26) then follows automatically. □

Multiplying (25) by X gives

C_{B}^{•} = X · E(B′(C_{B}^{•})).  (27)

In terms of the exponential generating functions, we obtain the perhaps more familiar expression

C_{B}^{•}(z) = z · exp (B′(C_{B}^{•}(z))) .  (28)

Theorem 7. Let w be a block-multiplicative weight function on connected graphs with all blocks in a particular species B. Then we have

C_{B,w}^{•} = X · E (B′_{w}(C_{B,w}^{•})) .  (29)

Proof. The same proof as in Theorem 6 can be used. One has only to check that the weight of a global C′_{B}-structure is equal to the product of the weights of the individual structures that appear in the corresponding E (B′_{w}(C_{B,w}^{•}))-structure. This is ensured by the block-multiplicativity of w. □

When we take the generating functions, formula (29) becomes

C_{B,w}^{•}(z) = z exp (B′_{w}(C_{B,w}^{•}(z))) .  (30)

Note that the series y = C_{B,w}^{•}(z) is a solution of the functional equation

y = z exp (B′_{w}(y)) ,  (31)

and the Lagrange inversion formula can be used to express the coefficients of y in terms of those of R(t) := exp(B′_{w}(t)).

2. The Gaussian model

2.1. Relation between the Gaussian model and graph complexity. Let

f_{ij} = − exp(−α∥x⃗_{i} − x⃗_{j}∥^{2}), α > 0,  (32)

which corresponds to a soft repulsive potential at constant temperature. In this case, the function

f(r) = − exp(−αr^{2})  (33)

satisfies the hypothesis of Proposition 3 and the second Mayer weight w(c) can be explicitly computed for any connected graph c (see [31]). Here we give a complete proof and an extension of this result.

The graph complexity γ(c) of a connected graph c is equal to the number of spanning subtrees of c. Let e(c) denote the number of edges of c.

Theorem 8. In dimension d, the second Mayer weight

w(c) = lim_{V →∞} \frac{1}{V} ∫_{V^{n}} ∏_{\{i,j\}∈c} − exp(−α∥x⃗_{i} − x⃗_{j}∥^{2})dx⃗_{1} … dx⃗_{n}  (34)

of a connected graph c with n vertices, has value

w(c) = (−1)^{e(c)} (\frac{π}{α})^{\frac{d(n−1)}{2}} γ(c)^{− \frac{d}{2}} .  (35)

Proof.

w(c) = lim_{V →∞} \frac{1}{V} ∫_{V^{n}} ∏_{\{i,j\}∈c} − exp(−α∥x⃗_{i} − x⃗_{j}∥^{2})dx⃗_{1} … dx⃗_{n}

= (−1)^{e(c)} lim_{V →∞} \frac{1}{V} ∫_{V^{n}} ∏_{\{i,j\}∈c} exp(−α∥x⃗_{i} − x⃗_{j}∥^{2})dx⃗_{1} … dx⃗_{n}.

Without loss of generality, we can consider the vessel V as a d-dimensional hypercube centered at the origin, of the form of the Cartesian product [−D, D]^{d} of intervals. Let us set x⃗_{i} = (x_{i1}, x_{i2}, …, x_{id}). We have

w(c) = (−1)^{e(c)} lim_{D→∞} \frac{1}{(2D)^{d}} ∫_{[−D,D]^{dn}} ∏_{\{i,j\}∈c} exp ( − α[(x_{i1} − x_{j1})^{2}

+ (x_{i2} − x_{j2})^{2} + … + (x_{id} − x_{jd})^{2}])dx_{11}dx_{12} … dx_{1d}dx_{21} … dx_{nd}

= (−1)^{e(c)}[ lim_{D→∞} \frac{1}{2D} ∫_{[−D,D]^{n}}

∏_{{i,j}∈c} exp(−α(x_{i1} − x_{j1})^{2})dx_{11}dx_{21} … dx_{n1}]^{d},  (36)

since the components of the vectors x⃗_{i} are independent of each other and appear symmetrically in the Gaussian weight (32). Applying (16) and removing the unnecessary second lower index 1, we find

w(c) = (−1)^{e(c)} [∫_{IR_{n−1}} ∏_{{i,j}∈c; x_{n}=0} exp (−α(x_{i} − x_{j})^{2}) dx_{1} ⋯ dx_{n−1}]^{d}

= (−1)^{e(c)} [∫_{IR_{n−1}} exp (−α ∑_{{i,j}∈c; x_{n}=0}(x_{i} − x_{j})^{2}) dx_{1} ⋯ dx_{n−1}]^{d} .

Let K = K(c) be the Kirchhoff matrix, of size (n − 1) × (n − 1), of the connected graph c, defined by

k_{ij} = \{ \begin{matrix}−1 & if \{i, j\} ∈ c, \\ d(i) & if i = j, \\ 0 & otherwise. \end{matrix}

Note that the degree d(i) takes into account edges attached to the “missing” vertex n. It is easily verified that

∑_{{i,j}∈c; x_{n}=0}(x_{i} − x_{j})^{2} = XKX^{T} ,  (37)

for X = (x_{1}, x_{2}, …, x_{n−1}), so that K is positive definite and we obtain, for the weight function,

w(c) = (−1)^{e(c)} [∫_{IR_{n−1}} exp(−αXKX^{T})dx_{1} … dx_{n−1}]^{d} .  (38)

We then can use the following classical multidimensional Gaussian integral:

Proposition 9. Let P be a p × p positive definite symmetric matrix. Then we have

∫_{IR_{p}} exp(−XP X^{T})dX = π^{\frac{p}{2}} det(P)^{− \frac{1}{2}} .
□

With P = αKand p = n − 1 we obtain

w(c) = (−1)^{e(c)} [(π)^{\frac{n−1}{2}} det(αK)^{−1/2}]^{d}
= (−1)^{e(c)} [(\frac{π}{α})^{\frac{n−1}{2}} det(K)^{−1/2}]^{d} .  (39)

We now use the spanning tree theorem of Kirchhoff (see [20]).

Theorem 10 (Kirchhoff). Let K be the Kirchhoff matrix of the connected graph c. Then, the number γ(c) of spanning trees of c satisfies γ(c) = det(K).

□

We finally obtain

w(c) = (−1)^{e(c)} (\frac{π}{α})^{\frac{d(n−1)}{2}} γ(c)^{− \frac{d}{2}} ,  (40)

concluding the proof of Theorem 8. □

2.2. An extension of the Gaussian potential. Following a suggestion of participants (G. Andrews and H. Wilf) at the 54th Séminaire Lotharingien de Combinatoire in Lucelle, France, in April 2005, we can generalize this result to include the degree distribution of the vertices of the spanning subtrees. Let T (c) be the set of all spanning subtrees of the connected graph c, and let d_{t}(i) be the degree of the vertex i in the spanning subtree t.

Theorem 11. With the potential function f_{ij} defined as

f_{ij} = − exp (−αy_{i}y_{j}∥x⃗_{i} − x⃗_{j}∥^{2}) ,  (41)

where the y_{i}’s are positive variables, the second Mayer weight function in d dimensions

w(c) = lim_{V →∞} \frac{1}{V} ∫_{V^{n}} ∏_{\{i,j\}∈c} − exp(−αy_{i}y_{j}∥x⃗_{i} − x⃗_{j}∥^{2})dx⃗_{1} … dx⃗_{n}  (42)

of a connected graph c with vertices {1, 2, …, n}, has value

w(c) = (−1)^{e(c)} (\frac{π}{α})^{\frac{d(n−1)}{2}} ( ∑_{t∈T (c)} y_{1}^{d_{t}(1)}y_{2}^{d_{t}(2)} … y_{n}^{d_{t}(n)})^{− \frac{d}{2}} .  (43)

Proof. It suffices to define the matrix K by

k_{ij} = \{ \begin{matrix}−y_{i}y_{j} & if \{i, j\} ∈ c, \\ y_{i} ∑_{\{i,h\}∈c} y_{h} & if i = j, \\ 0 & otherwise. \end{matrix}

As before, we have

w(c) = lim_{V →∞} \frac{1}{V} ∫_{V^{n}} ∏_{\{i,j\}∈c} − exp(−αy_{i}y_{j}∥x⃗_{i} − x⃗_{j}∥^{2})dx⃗_{1} … dx⃗_{n}

= (−1)^{e(c)} [∫_{IR_{n−1}} exp(−αXKX^{T})dx_{1} ⋯ dx_{n−1}]^{d}

= (−1)^{e(c)} [(\frac{π}{α})^{\frac{n−1}{2}} det(K)^{−1/2}]^{d} .  (44)

But Lovász shows (see [18], problem 4.10) that for such a matrix K,

det(K) = ∑_{t∈T (c)} y_{1}^{d_{t}(1)}y_{2}^{d_{t}(2)} … y_{n}^{d_{t}(n)};  (45)

therefore, (43) is established. □

Remark. It is possible to further extend this result by setting

f_{ij} = − exp (−w_{i,j}∥x⃗_{i} − x⃗_{j}∥^{2}) ,  (46)

where the w_{i,j}’s are general (positive) weights associated to edges. In this case the weight of a connected graph c gives the edge enumerator of spanning subtrees of c. Indeed, invoking a more general form of Kirchhoff’s formula (see, for example Sylvester [29], Borchardt [3] and Chaiken and Kleitman [5], we find that

w(c) = (−1)^{e(c)} (π)^{\frac{d(n−1)}{2}} ( ∑_{t∈T (c)} ∏_{\{i,j\}∈t} w_{i,j})^{− \frac{d}{2}} .  (47)

3. The hard-core continuum gas in one dimension

Consider N hard particles of diameter 1 on a line segment, of the form [−D, D]. The hard-core constraint translates into the interaction potential χ(|x_{i} − x_{j}| ≥ 1) (with φ(r) = ∞, if r < 1, and φ(r) = 0, if r ≥ 1) and the Mayer function f_{ij} is defined by

1 + f_{ij} = χ(|x_{i} − x_{j}| ≥ 1)
⇔ f_{ij} = −χ(|x_{i} − x_{j}| < 1).  (48)

The hypothesis of Proposition 3 is verified for the function

f(r) = −χ(r < 1),  (49)

allowing us to write the weight function w(c) of a connected graph c as

w(c) = (−1)^{e(c)} ∫_{IR_{N−1}} ∏_{{i,j}∈ c; x_{N} =0} χ(|x_{i} − x_{j}| < 1) dx_{1} … dx_{N−1}.  (50)

With this potential, the pressure can still be expressed in terms of the exponential generating function of the weighted species of connected graphs, as in (18):

\frac{P}{kT} = C_{w}(z).  (51)

3.1. Global formulas. It is known (see [4]) that for the hard-core gas, the pressure of the system is given by

\frac{P}{kT} = L(z),  (52)

where L(z) denotes the Lambert function, defined by the functional equation

L(z) exp(L(z)) = z.  (53)

Here, we give a combinatorial proof of this result.

Proposition 12. In the thermodynamic limit D → ∞, the pressure \frac{P}{kT} of the continuous unidimensional hard-core gas model is given by (52).

Proof. Note that the Lambert function satisfies L(z) = −T (−z), where T (z) is the exponential generating function of labelled rooted trees. Let us consider the particles on a segment of the form [0, 2D]. Then, since the N! possible relative positions of the x_{i} give rise to integrals of equal value, the grand-canonical partition function can be written as

Z_{gr}(D, z) = ∑_{N≥0} \frac{z^{N}}{N!} ∫_{[0, 2D]^{N}} ∏_{i<j} χ(|x_{i} − x_{j}| ≥ 1)dx_{1}dx_{2} ⋯ dx_{N}

= ∑_{N≥0} z^{N} ∫_{0}^{2D} dx_{1} ∫_{x_{1}+1}^{2D} dx_{2} ⋯ ∫_{x_{N−1}+1}^{2D} dx_{N}.  (54)

Now the integral in (54) is the volume of the simplex

0 ≤ x_{1} ≤ x_{2} − 1 ≤ x_{3} − 2 ≤ ⋯ ≤ x_{N} − N + 1 ≤ 2D − N + 1,

and has value (2D − N + 1)^{N}/N!. See for example Section 4.2 of [30] on the onedimensional Tonks gas. It follows that

Z_{gr}(−D, −z) = ∑_{N≥0}(N + 2D − 1)^{N}z^{N}/N! ,  (55)

which is the exponential generating function of structures which consist of functions of the form f : U → U +V, where U is a finite set (of varying size N), V is a fixed set of size |V | = 2D − 1 and + denotes the disjoint union. By considering the saggital graph of such functions, obtained by taking the oriented edges (u, f(u)), u ∈ U, we see that the connected components consist of either connected endofunctions on subsets U′ of U or rooted trees on U′ pointing to an element of V. Thus there are 2D − 1 kinds of connected components of the sort “rooted trees”. Let f_{N} be the number of connected endofunctions on an N-element set and let F (z) = ∑_{N≥0} f_{n}z^{N}/n! be their generating function. Then we have

Z_{gr}(−D, −z) = exp (F (z) + (2D − 1)T (z))  (56)

and, reverting back to D and z and taking the thermodynamic limit,

\frac{P}{kT} = lim_{D→∞} \frac{1}{2D} log Z_{gr}(D, z)

= lim_{D→∞} \frac{1}{2D}(F (−z) − (2D + 1)T (−z))

= −T (−z) = L(z),

which concludes the proof. □

Corollary 13. Let N be an integer ≥ 1; the total weight |C[N]|_{w} of the set of all connected graphs over the set [N] = {1, 2, …, N} of vertices is given by

∑_{c∈C[N]} w(c) = (−N)^{N−1}.  (57)

Proof. This follows immediately from the fact that

C_{w}(z) = \frac{P}{kT} = −T (−z)

by extracting coefficients. □

We now invoke the functional equation (29) in the case where B is the species of all 2-connected graphs and hence C_{B} = C, the species of all connected graphs, with the weight function w given by (50):

C_{w}^{•}(z) = z exp (B′_{w}(C_{w}^{•}(z))) .  (58)

Proposition 14. For the total weight of 2-connected graphs, we have

B_{w}(z) = z log(1 − z).  (59)

Conversely, formula (59) implies that C_{w}(z) = L(z).

Proof. It is clear from (58) that any one of the functions C_{w}(z) and B_{w}(z) determines uniquely the other, since C_{w}(z) is of the form z + … and B′_{w}(z) = −2z + …. Hence it suffices to prove that

L^{•}(z) = z exp (B′(L^{•}(z)) ,  (60)

where the function B(z) is defined by

B(z) = z log(1 − z),  (61)

in order to establish the Proposition. It is easily seen that

B′(z) = log(1 − z) − \frac{z}{1 − z} ,

and that L^{•}(z) = zL′(z) satisfies

L^{•}(z) = \frac{L(z)}{1 + L(z)},

upon differentiation of (53). We then have

z exp(B′(L^{•}(z))) = z exp (log(1 − L^{•}(z)) − \frac{L^{•}(z)}{1 − L^{•}(z)})

= z(1 − L^{•}(z)) exp (\frac{−L^{•}(z)}{1 − L^{•}(z)})

= z (1 − \frac{L(z)}{1 + L(z)}) exp (\frac{−\frac{L(z)}{1+L(z)}}{1 − \frac{L(z)}{1+L(z)}} )

= z \frac{1}{1 + L(z)} exp(−L(z))

= \frac{L(z)}{1 + L(z)}

= L^{•}(z),

which proves (60). □

Proposition 15. Let N be an integer ≥ 2; the total weight |B[N]| of the set of all 2-connected graphs with N vertices is given by

∑_{c∈B[N]} w(c) = −N(N − 2)!  (62)

Proof. This follows immediately from (59) by extracting coefficients. □

Corollary 16. The virial expansion for the hard core one-dimensional gas is given by

\frac{P}{kT} = \frac{ρ}{1 − ρ}.  (63)

Proof. Using equations (23) and (62), we see that γ_{n}(T) = 1, for all n ≥ 2 and the result follows. □

Question 1: Are there direct combinatorial proofs of (57) and (62), independently of Proposition 12 ?

Question 2: Can we compute the individual weights w(c) of given connected graphs c and interpret them in terms of other graph invariants?

3.2. The Ehrhart polynomial. While trying to answer these questions, we have made the following observation. Except for the sign, the weight

w(c) = (−1)^{e(c)} ∫_{IR_{N−1}} ∏_{{i,j}∈c; x_{N} =0} χ(|x_{i} − x_{j}| < 1) dx_{1} … dx_{N−1}  (64)

can be seen as the volume of a convex polytope P(c) in IR^{N} bounded by the constraints |x_{i} − x_{j}| ≤ 1, for {i, j} ∈ c, with x_{N} = 0. We can compute this volume using Ehrhart polynomials (see [28]).

Theorem 17 (Ehrhart). Let P be a convex polytope of dimension d in IR^{m}, with vertices having integer coordinates. Let nP = {nα : α ∈ P} denote the n-fold expansion of P, and I(P, n), the number of points with integer coordinates which lie inside nP. Then I(P, n) is a polynomial function of n of degree d whose leading coefficient is the volume Vol(P) of P.

□

In order to apply Ehrhart’s theorem, we have to prove the following:

Proposition 18. Let c be a connected graph with its N vertices labelled {1, 2, …, N}, and define the convex polytope P(c) ⊂ IR^{N} by

P(c) = {X ∈ IR^{N} | x_{N} = 0 and |x_{i} − x_{j}| ≤ 1 ∀ {i, j} ∈ c} ,  (65)

where X = (x_{1}, …, x_{N}). Then the vertices of P(c) have integer coordinates.

Proof. Notice that P(c) is of dimension N − 1. Every vertex of P(c) is at the intersection of N − 1 faces of the polytope. Each equation of the form |x_{i} − x_{j}| = 1, {i, j} ∈ c, generates two faces: one that satisfies the equation x_{i} − x_{j} = 1, and the other which satisfies x_{j} − x_{i} = 1, corresponding to the two possible orientations of the edge {i, j}. We can express all these equations in the matrix form

X Ω = (1, 1, …, 1),  (66)

where Ω is the incidence matrix of the oriented graph obtained from c by replacing each edge by the two corresponding opposite oriented edges. The result then follows from the fact that this matrix is totally unimodular, i.e., all its subdeterminants have values 0, ±1. See [26]. □

It follows that the volume of P(c) and the weight

w(c) = (−1)^{e(c)} Vol(P(c))  (67)

can be obtained by computing the Ehrhart polynomial I(P(c), n). Notice that the n-fold expansion of P(c) is given by

nP(c) = {X ∈ IR^{N} | x_{N} = 0 and |x_{i} − x_{j}| ≤ n ∀{i, j} ∈ c} .  (68)

For all 2-connected graphs c having N vertices, with N ≤ 6, we have carried out the computation of the Ehrhart polynomial I(P(c), n) and hence the volume Vol(P(c)), by counting the number of points with integer coordinates in the n-fold expansion n P(c), for n = 2, …, 6. See Appendix B for the results. The weight of any connected graph c all of whose blocks have size at most 6 can then be deduced by block multiplicativity. The individual weights w(c) for 2-connected graphs c of size up to 5 were already known. See Riddell and Uhlenbeck [23], p. 2063, for example.

3.3. Particular weight values. The numerical results have led us to conjecture and then prove a formula for the weight w(K_{N}) of the complete graph with N vertices (N ≥ 2). In this section, we also give two formulas for the weight w(C_{N}) of the N-cycle (N ≥ 3). The weight w(K_{N}\e) for the complete graph minus an edge (N ≥ 3) is given in the following section.

3.3.1. The complete graph K_{N}.

Proposition 19. For the complete graph K_{N}, we have

w(K_{N}) = (−1)^{\binom{N}{2}}N.  (69)

Proof. Starting with formula (50), we have

w(K_{N}) = (−1)^{\binom{N}{2}} ∫_{IR_{N−1}} ∏_{\{i,j\}∈K_{N}; x_{N} =0} χ(|x_{i} − x_{j}| < 1) dx_{1} ⋯ dx_{N−1}

= (−1)^{\binom{N}{2}} ∫_{−1}^{1} ⋯ ∫_{−1}^{1} ∏_{1≤i<j≤N−1} χ(|x_{i} − x_{j}| < 1) dx_{1} ⋯ dx_{N−1}.  (70)

Replacing each x_{i} by x_{i} + 1, for i = 1, … N − 1, yields

|w(K_{N})| = ∫_{0}^{2} ⋯ ∫_{0}^{2} ∏_{1≤i<j≤N−1} χ(|x_{i} − x_{j}| < 1) dx_{1} ⋯ dx_{N−1}

= (N − 1)! ∫_{A} ∏_{1≤i<j≤N−1} χ(x_{i} − x_{j} < 1) dx_{1} ⋯ dx_{N−1},  (71)

where A denotes the region 0 ≤ x_{1} ≤ ⋯ ≤ x_{N−1} ≤ 2, by symmetry. Let us make the change of variables

y_{i} = x_{i+1} − x_{i}, for 1 ≤ i ≤ N − 2,
y_{N−1} = 2 − x_{N−1},  (72)

which is equivalent to

x_{i} = 2 − y_{i} − ⋯ − y_{N−1}, for 1 ≤ i ≤ N − 2,
x_{N−1} = 2 − y_{N−1}.  (73)

The domain of integration A is transformed into the region B defined by y_{i} ≥ 0, for i = 1, …, N − 1, and

y_{1} + ⋯ + y_{N−1} ≤ 2.

Moreover, in this region, the integrand of (71) is not zero, and has value 1, if and only if

y_{1} + y_{2} + ⋯ + y_{N−2} < 1.

We can decompose the region B into the subregions B_{1}, where y_{1} + ⋯ + y_{N−1} ≤ 1, and B_{2}, where 1 ≤ y_{1} + ⋯ + y_{N−1} ≤ 2 and (71) becomes

|w(K_{N})| = (N − 1)! ∫_{B} χ(y_{1} + ⋯ + y_{N−2} < 1) dy_{1} ⋯ dy_{N−1}

= (N − 1)! ∫_{B_{1}⊎B_{2}} χ(y_{1} + ⋯ + y_{N−2} < 1) dy_{1} ⋯ dy_{N−1}

= (N − 1)! (∫_{IR{N−1 \atop +}} χ(y_{1} + ⋯ + y_{N−1} < 1) dy_{1} ⋯ dy_{N−1}

+ ∫_{IR{N−2 \atop +}} (∫_{1−y_{1}−···−y_{N−2}}^{2−y_{1}−···−y_{N−2}} dy_{N−1}) χ(y_{1} + ⋯ + y_{N−2} < 1) dy_{1} ⋯ dy_{N−2})

= (N − 1)! (\frac{1}{(N − 1)!} + \frac{1}{(N − 2)!})

= 1 + N − 1 = N.

□

3.3.2. The Cycle graph C_{N}. Proposition 20. For the (unoriented) cycle C_{N} with N vertices, we have

w(C_{N}) = (−1)^{N} \frac{2^{N}}{2π} ∫_{−∞}^{∞} (\frac{sin t}{t})^{N} dt.  (74)

Proof. Starting with (50), let us make the change of variables

t_{i} = x_{i} − x_{i+1}, for 1 ≤ i ≤ N − 1,

of Jacobian 1. The conditions |x_{i} −x_{i+1}| ≤ 1 corresponding to the edges {i, i+1} of C_{N} give |t_{i}| ≤ 1 and the condition |x_{1} − x_{N}| ≤ 1 corresponding to the edge {1, N} yields |t_{1} + ⋯ + t_{N−1}| ≤ 1. Then, writing χ(x) := χ(|x| ≤ 1) for simplicity, we have

w(C_{N}) = (−1)^{N} ∫_{IR_{N−1}} ∏_{{i,j}∈ C_{N} ; x_{N} =0} χ(x_{i} − x_{j}) dx_{1} … dx_{N−1}

= (−1)^{N} ∫_{IR_{N−1}} χ(t_{1} + t_{2} + ⋯ + t_{N−1})χ(t_{1}) ⋯ χ(t_{N−1}) dt_{1} ⋯ dt_{N−1}
= (−1)^{N} Vol {T ∈ IR^{N−1} | − 1 ≤ T ≤ 1, −1 ≤ ⟨ T, 1 ⟩ ≤ 1 } ,  (75)

where T = (t_{1}, …, t_{N−1}), 1 = (1, …, 1) and ⟨ X, Y ⟩ denotes the scalar product.

Let U_{1}, U_{2}, …, U_{N−1} be independent identically distributed uniform random variables on the interval [−1, 1], with common density function u(x) = \frac{1}{2}χ(x) and let S = U_{1} + ⋯ + U_{N−1}. Then, by (75),

w(C_{N}) = (−1)^{N} 2^{N−1} Prob(−1 ≤ S ≤ 1).  (76)

GRAPH WEIGHTS ARISING FROM MAYER’S THEORY OF CLUSTER INTEGRALS 19

The density function s(x) of S is given by the (N − 1)-fold convolution product

s = u^{∗(N−1)} = u ∗ ⋯ ∗ u (N − 1 factors),

where

(f ∗ g)(x) := ∫_{−∞}^{∞} f(ξ)g(x − ξ) dξ.

We deduce from (76) that

w(C_{N}) = (−1)^{N} 2^{N−1} ∫_{−1}^{1} s(ξ) dξ
= (−1)^{N} 2^{N−1}2 ∫_{−∞}^{∞} s(ξ)u(ξ) dξ
= (−2)^{N} ∫_{−∞}^{∞} u^{∗(N−1)}(ξ)u(0 − ξ) dξ
= (−2)^{N} u^{∗N}(0).  (77)

Since the Fourier transform û(t) of u(x) is given by

û(t) = ∫_{−∞}^{∞} u(x)e^{−itx}dx = \frac{1}{2} ∫_{−1}^{1} e^{−itx}dx = \frac{sin t}{t}  (78)

and { \atop f ∗ g}(t) = f̂(t) · ĝ(t), we get

û^{∗N}(t) = (û(t))^{N} = (\frac{sin t}{t})^{N} .  (79)

Taking the inverse Fourier transform on both sides, we deduce that

u^{∗N}(x) = \frac{1}{2π} ∫_{−∞}^{∞} û^{∗N}(t)e^{itx}dt
= \frac{1}{2π} ∫_{−∞}^{∞} (\frac{sin t}{t})^{N} e^{itx}dt  (80)

and (74) follows via the substitution x = 0. □ Corollary 21. We have the asymptotic estimate

w(C_{N}) ∼ (−2)^{N} (\frac{3}{2πN} )^{\frac{1}{2}} (1 − \frac{3}{20N} − \frac{13}{1120N^{2}} + …)  (81)

as N → ∞. Proof. Make the local substitution \frac{sin t}{t} = exp(−u^{2}) around the origin and integrate term by term. □ Proposition 22. For the cycle C_{N} with N vertices, we also have

w(C_{N}) = \frac{(−1)^{N}}{(N − 1)!} ∑_{i=0}^{⌊ \frac{N−1}{2} ⌋}(−1)^{i}\binom{N}{i}(N − 2i)^{N−1}.  (82)

Proof. Note first that the density function u(x) = \frac{1}{2} χ(|x| ≤ 1) satisfies

u = \frac{1}{2}(δ_{−1} − δ_{1}) ∗ H(x) (a.e.),  (83)

where δ_{a} and H are defined by

(δ_{a} ∗ f)(x) = f(x − a), H(x) = \{ \begin{matrix}1, & if x > 0, \\ 1/2, & if x = 0, \\ 0, & if x < 0. \end{matrix}

Using (77), (83), commutativity of the convolution product and the binomial theorem, we obtain

w(C_{N}) = (−1)^{N}((δ_{−1} − δ_{1})^{∗N} ∗ H^{∗N})(0)

= (−1)^{N} (∑_{i=0}^{N}(−1)^{i}\binom{N}{i}δ_{2i−N} ∗ \frac{(x^{+})^{N−1}}{(N − 1)!}) | x = 0

= \frac{(−1)^{N}}{(N − 1)!} ∑_{i=0}^{N}(−1)^{i}\binom{N}{i}((x + N − 2i)^{+})^{N−1} | x = 0

= \frac{(−1)^{N}}{(N − 1)!} ∑_{i=0}^{⌊ \frac{N−1}{2} ⌋}(−1)^{i}\binom{N}{i}(N − 2i)^{N−1},

since H^{∗N}(x) = (x^{+})^{N−1}/(N − 1)!, where x^{+} := H(x)x. □

Combinatorial proof of Proposition 22 for N even. We can give a combinatorial proof of (82) when N is even, based on the geometric properties of the Eulerian numbers A_{n,k} (n ≥ 1, 1 ≤ k ≤ n). They can be defined by the Worpitzky formula (see [8])

A_{n,k} = ∑_{0≤i≤k−1}(−1)^{i}(k − i)^{n}\binom{n + 1}{i}.  (84)

These numbers admit a geometric interpretation using the volume of a closed region of IR^{n} (see [8] and the note [27] following it):

A_{n,k}/n! = Vol { Y ∈ IR^{n} | 0 ≤ Y ≤ 1, k − 1 ≤ ⟨ Y, 1 ⟩ ≤ k },  (85)

where 0 and 1 denote the constant vectors with entries 0 and 1, respectively. Starting with (75) let us make the transformation

z_{i} := t_{i} + 1, for 1 ≤ i ≤ N − 1

and set Z = (z_{1}, …, z_{N−1}) and 2 = (2, …, 2). Then we see that

w(C_{N}) = (−1)^{N}Vol { Z ∈ IR^{N−1} | 0 ≤ Z ≤ 2, N − 2 ≤ ⟨ Z, 1 ⟩ ≤ N }. (86)

If N is even, we can simplify the expression (86) further by setting y_{i} := z_{i}/2. We then find, using (85) and (84),

w(C_{N}) = (−1)^{N} 2^{N−1} Vol { Y ∈ IR^{N−1} | 0 ≤ Y ≤ 1, N/2 − 1 ≤ ⟨ Y, 1 ⟩ ≤ N/2 }

= (−1)^{N} 2^{N−1} \frac{1}{(N − 1)!} A_{N−1,N/2}

= (−1)^{N} \frac{2^{N−1}}{(N − 1)!} ∑_{0≤i≤N/2−1}(−1)^{i}(N/2 − i)^{N−1}\binom{N}{i}

= \frac{(−1)^{N}}{(N − 1)!} ∑_{0≤i≤N/2−1}(−1)^{i}(N − 2i)^{N−1}\binom{N}{i},  (87)

which establishes (82). □

Remark. For N odd (or general), by analogy with the Eulerian numbers, it is tempting to define numbers B_{n,k} by the formula

B_{n,k}/n! = Vol { Z ∈ IR^{n} | 0 ≤ Z ≤ 2, k − 1 ≤ ⟨ Z, 1 ⟩ ≤ k }  (88)

so that (N − 1)! w(C_{N}) = B_{N−1,N−1} + B_{N−1,N}. There remains to interpret these numbers combinatorially and to use them to establish (82) in complete generality.

3.4. Graph homomorphisms. As observed by Bodo Lass [13], it is possible to evaluate the volume of the polytope P(c) by decomposing it into a certain number ν(c) of subpolytopes which are all simplices of volume 1/(N −1)!. Each subpolytope is obtained by fixing the integral parts and the relative positions of the fractional parts of the coordinates x_{1}, …, x_{N} of points X ∈ P(c). The number of such configurations will then yield ν(c) and we will have Vol(P(c)) = ν(c)/(N − 1)!.

In order to make this correspondence more precise, we consider the following fractional representation of real numbers

IR → ([0, 1] × ZZ) : x ↦ (ξ_{x}, h_{x}),  (89)

where h_{x} = ⌊x⌋ is the integral part of x and ξ_{x} = x − h_{x} is the (positive) fractional part of x, so that x = ξ_{x} + h_{x}. For example,

0.25 ↦ (0.25, 0), 3.75 ↦ (0.75, 3) and − 1.25 ↦ (0.75, −2).

See Figure 3. Notice that 0 ≤ ξ_{x} < 1. However, for x = 0, it will be convenient to use the special representation 0 ↦ (1.0, −1), as if 0 was infinitesimally negative.

In this representation, the condition |x − y| < 1 for two real numbers x and y translates into “ξ_{x} ≠ ξ_{y} and assuming ξ_{x} < ξ_{y}, then h_{x} = h_{y} or h_{x} = h_{y} + 1”. This can be visualized as follows: the slope of the line segment between x and y should be either null or negative. See Figure 3 where the interval (x − 1, x + 1) is represented by the thick segments.

Now consider a connected graph c with vertex set V = [N] = {1, 2, …, N}, and let X = (x_{1}, …, x_{N}) be a point in the polytope P(c). Let us write x_{i} ↦ (ξ_{i}, h_{i}) for the fractional representation of the coordinate x_{i} of X, i = 1, …, N. Recall that x_{N} = 0 so that ξ_{N} = 1.0 and h_{N} = −1, with our convention.

y ↦ (ξ_{y}, h_{y}) x ↦ (ξ_{x}, h_{x}) 3.75 ↦ (0.75, 3) 0.25 ↦ (0.25, 0) 0 ↦ (1.0, −1) −1.25 ↦ (0.75, −2)

Figure 3. Fractional representation of real numbers

The volume of P(c) is not changed by removing all hyperplanes {x_{i} −x_{j} = k}, for k ∈ ZZ. Hence, we can assume that all the fractional parts ξ_{i} are distinct. We form a subpolytope of P(c) by keeping the “heights” h_{1}, h_{2}, …, h_{N} fixed as well as the relative positions (total order) of the fractional parts ξ_{1}, ξ_{2}, …, ξ_{N}. Let h : V → ZZ denote the height function i ↦ h_{i} and β : V → [N] be the permutation of [N] for which β(i) gives the rank of ξ_{i} in this total order. Note that β(N) = N. For example, if N = 5 and ξ_{3} < ξ_{4} < ξ_{2} < ξ_{1} < ξ_{5}, then β(1) = 4, β(2) = 3, β(3) = 1, β(4) = 2 and β(5) = 5, i.e., β = (4, 3, 1, 2, 5).

The corresponding subpolytope will be denoted by P(h, β). Let us choose a canonical point X = X_{h,β} of P(h, β), say the centroid, obtained by setting ξ_{i} = β(i)/N, i = 1, …, N. Using the fractional coordinates to represent this canonical point X_{h,β} of P(h, β), and drawing a dotted line segment between x_{i} and x_{j} for each edge i, j of the graph c, we obtain a configuration in the plane which can be seen as an homomorphic image of c and which characterizes the subpolytope P(h, β). For example, with N = 5 and c = C_{5}, the 5-cycle, we can take h = (0, 1, 1, 0, −1) and β = (4, 3, 1, 2, 5) as above. This indeed defines a subpolytope P(h, β) of P(C_{5}), for which X_{h,β} = (0.8, 1.6, 1.2, 0.4, 0). Figure 4 illustrates the corresponding configuration, where the homomorphic image of C_{5} appears clearly.

Proposition 23. Let c be a connected graph with vertex set V = [N] and consider a function h : V → ZZ and a bijection β : V → [N] satisfying β(N) = N. Then the pair (h, β) determines a valid subpolytope P(h, β) of P(c) if and only if the following

x_{4} x_{3}  x_{5} x_{2}x_{1}  ^{1}

Figure 4. Fractional representation of a simplicial subpolytope of P(C_{5})

condition is satisfied:

for any edge {i, j} of c, β(i) < β(j) implies h_{i} = h_{j} or h_{i} = h_{j} + 1. (90)

Proof. Let X_{h,β} = (x_{1}, …, x_{N}) denote the canonical point associated with (h, β), i.e., where x_{i} = h_{i} + ξ_{i}, with ξ_{i} := β(i)/N, i = 1, …, N. Then the pair (h, β) determines a valid subpolytope P(h, β) of P(c) if and only if the point X_{h,β} is in P(c). But the condition (90) expresses exactly that |x_{i} − x_{j}| < 1, whenever {i, j} is an edge of c, that is, the defining condition of P(c). □

Proposition 24. Let c be a connected graph and let (h, β) be such that β(N) = N and condition (90) is satisfied. Then the volume of the associated subpolytope P(h, β) is equal to 1/(N − 1)!.

Proof. The simplest case is when β is the identity, i.e., when 0 < ξ_{1} < ξ_{2} < ⋯ < ξ_{N−1} < 1, and all levels h_{1}, h_{2}, …, h_{N−1} are 0. Since x_{N} = 0, this corresponds to the standard (N − 1)-dimensional simplex whose volume is 1/(N − 1)!. But it is clear that the same is true for any β and that all the other subpolytopes P(h, β) are translates of these, hence also (N − 1)-simplexes, of volume 1/(N − 1)!. □

Proposition 25. Let c be a connected graph and let ν(c) be the number of pairs (h, β) such that the condition (90) is satisfied. Then the volume of the polytope P(c) defined by (65) is given by

Vol(P(c)) = ν(c)/(N − 1)!.  (91)

Proof. It is clear that the polytope P(c) is the disjoint union of all its subpolytopes P(h, β) and the result follows from Proposition 24. □

Proposition 25 can be used to compute the weight of some infinite families of graphs, since w(c) = (−1)^{e(c)}Vol(P(c)). As a first example, we give an alternate proof of the formula (69): w(K_{N}) = (−1)^{\binom{N}{2}}N. Indeed, since all edges are present in the complete graph, any of the (N − 1)! permutations beta for which β(N) = N can occur, by symmetry, and there are only N possible height sequences h∘β^{(−1)}, of the form (0, …, 0, −1, …, −1), from (0, …, 0, −1) to (−1, …, −1), which give rise to legal configurations (h, β). Hence ν(K_{N}) = N(N − 1)! and the result follows.

Another example is the following, due to Bodo Lass:

Proposition 26. [13] For N ≥ 3, let K_{N}\e denote the complete graph on N vertices from which an arbitrary edge has been removed. Then we have

w(K_{N}\e) = (−1)^{\binom{N}{2}−1} (N + \frac{2}{(N − 1)}) .  (92)

Proof. We can assume that the missing edge is e = {1, N}. Note that all the configurations (h, β) of K_{N} are also valid here. In addition, there are two other possibilities for h: a) set h_{1} = 1, h_{N} = −1 and all other h_{i} = 0, so that β(1) must be 1, and b) h_{1} = −2 and all other h_{i} = −1, so that β(1) must be N − 1. In both cases β can be extended in (N − 2)! ways. □

Finally, an elegant description of all the compatible configurations can be given for the cycle graph C_{N} on [N], with edge set {{i, i + 1}(mod N) | i = 1, …, N}. Indeed, following the cycle, the sequence of heights

h^{∗} = (h_{N} = −1, h_{1}, h_{2}, …, h_{N−1}, h_{N} = −1)  (93)

defines a path of Motzkin type, i.e., where the only permitted “moves” are rises (by 1), levels and descents (by 1), denoted by r, l and d, respectively. Starting and ending at height −1, the path h^{∗} can thus be encoded by a generalized Motzkin word μ in the letters r, l, d. As an example, for the configuration of Figure 4, we have

h^{∗} = (−1, 0, 1, 1, 0, −1) and μ = rrldd .

Notice that the first step cannot be a descent and the last step, a rise. But the path is allowed to attain heights below -1. Thus the legal configurations of C_{N} can be classified according to the corresponding words μ and the compatible permutations β can be given a simple description in terms of μ. Details are left to the reader.

Remark. Olivier Bernardi [2] has partially answered Question 1 given at the end of Section 3.1. Using the subpolytope representations of this section, he has described an involution which establishes (57), namely that the sum of all weights w(c) of connected graphs c over an N-element set is (−N)^{N−1}.

References

[1] F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Encyclopedia of mathematics and its applications, Vol. 67, Cambridge University Press, 1997, 457 p.

[2] O. Bernardi, “Preuve bijective pour la somme des poids de Mayer des graphes connexes”, Manuscript, May 2006.

[3] C. W. Borchardt, “Ueber eine der Interpolation entsprechende Darstellung der Eliminations-Resultante.” Journal für die reine und angewandte Mathematik, 57 (1860), 111–121.

[4] D. C. Brydges and J. Z. Imbrie, “Dimensional reduction formulas for branched polymer correlation functions.” Journal of Statistical Physics 110 (2003), 503–518.

arχiv:math-ph/0203055 v2.

[5] S. Chaiken and D. J. Kleitman, “Matrix tree theorems.” Journal of Combinatorial Theory Ser. A 24 (1978), 377–381.

[6] Nathan Clisby and Barry M. McCoy, “Ninth and tenth order virial coefficients for hard spheres in D dimensions.” Journal of Statistical Physics, 122 (2006), 15–57.

[7] Martin G. Ducharme, Intégrales de Mayer et graphes 2-connexes pondérés, M.Sc. Thesis, UQÀM, Montréal, Dec. 2004, 71 p.

[8] D. Foata, “Distributions eulériennes et mahoniennes sur le groupe des permutations,” in Higher Combinatorics (M. Aigner, ed.), Reidel, Dordrecht/Boston, 1977, 27–49.

[9] F. Harary and E. M. Palmer, Graphical Enumeration, New York and London: Academic Press, 1973, 271 p.

[10] K. Husimi, “Note on Mayer’s theory of cluster integrals.” The Journal of Chemical Physics, 18 (1950), 682–684.

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

[12] Jacques Labelle, “Applications diverses de la théorie combinatoire des espèces de structures.” Annales des sciences mathématiques du Québec, 7 (1983), 59–94.

[13] Bodo Lass, Personal communication, 2005.

[14] Pierre Leroux, Algèbre linéaire: une approche matricielle, Montréal: Modulo Éditeur, 1983, 500 pp.

[15] Pierre Leroux, “Methoden der Anzahlbestimmung für einige Klassen von Graphen,” Bayreuther Mathematische Schriften, 26 (1988), 1–36.

[16] Pierre Leroux, “Enumerative problems inspired by Mayer’s theory of cluster integrals.” The Electronic Journal of Combinatorics, 11 (2004), R32.

[17] Pierre Leroux and Brahim Miloudi, “Généralisation de la formule d’Otter,” Annales des Sciences Mathématiques du Québec, 16 (1992), 53–80.

[18] László Lovász, Combinatorial Problems and Exercises, Amsterdam: North-Holland Publishing Company, 1979, 551 p.

[19] J. E. Mayer and M. G. Mayer, Statistical Mechanics, New York: Wiley, 1940.

[20] J. W. Moon, Counting Labelled Trees, Monographies canadiennes de mathématiques, 1970, 113 p.

[21] R. Z. Norman, On the Number of Linear Graphs With Given Blocks, Dissertation, University of Michigan, 1954.

[22] R. J. Riddell, Contribution on the Theory of Condensation, Dissertation, University of Michigan, 1951.

[23] R. J. Riddell and G. E. Uhlenbeck, “On the theory of the virial development of the equation of state of monoatomic gases,” The Journal of Chemical Physics, 21 (1953), 2056–2064.

[24] David Ruelle, Statistical Mechanics, Addison-Wesley, 1989, 219 p.

[25] R. W. Robinson, “Enumeration of non-separable graphs,” Journal of Combinatorial Theory, 9 (1970), 327–356.

[26] Alexander Schrijver, Theory of Linear and Integer Programming, John Wiley & Sons, Ltd., Chichester, 1986, 471 pp.

[27] Richard P. Stanley, Eulerian partitions of a unit hypercube, in Higher Combinatorics (M. Aigner, ed.), Reidel, Dordrecht/Boston, 1977, p. 49.

[28] Richard P. Stanley, Enumerative Combinatorics, vol. 1, Belmont, California: Wadsworth, 1986, 306 p.

[29] J. J. Sylvester, “On the change of systems of independent variables,” Quarterly Journal of Mathematics, 1, (1857), 42–56.

[30] Colin J. Thompson, Mathematical Statistical Mechanics, Princeton University Press, 1972, 278 p.

[31] G. E. Uhlenbeck and G. W. Ford, Lectures in Statistical Mechanics, Providence, Rhode Island: American Mathematical Society, 1963, 181 p.

Appendix A. Proof of Proposition 3

First we have to show that the function

Fx⃗_{N} (x⃗_{1}, x⃗_{2}, …, x⃗_{N−1}) = ∏_{{i,j}∈c} f(|x⃗_{i} − x⃗_{j}|)  (94)

is integrable. In order to prove this, we need to show that Fx⃗_{N} is measurable and that

Ix⃗_{N} := ∫_{IR_{d(N−1)}} |Fx⃗_{N} (x⃗_{1}, …, x⃗_{N−1})|dx⃗_{1} ⋯ dx⃗_{N−1} < ∞.  (95)

Since f is integrable, it is measurable and the function f(|x⃗_{i} − x⃗_{j}|) is measurable for all i, j ≤ N. This implies that the product Fx⃗_{N} is measurable. In order to prove that Ix⃗_{N} < ∞, let us choose a spanning subtree a of the connected graph c. Since f is bounded, we can denote its bound by

A = sup_{r≥0} |f(r)| < ∞.  (96)

We then have

Ix⃗_{N} = ∫_{IR_{d(N−1)}} ∏_{{i,j}∈a} |f(|x⃗_{i} − x⃗_{j}|)| ∏_{{i,j}∈c\a} |f(|x⃗_{i} − x⃗_{j}|)|dx⃗_{1} ⋯ dx⃗_{N−1}

≤ A^{|c\a|} ∫_{IR_{d(N−1)}} ∏_{{i,j}∈a} |f(|x⃗_{i} − x⃗_{j}|)|dx⃗_{1} ⋯ dx⃗_{N−1}.  (97)

Under the change of variables

z⃗_{i} = x⃗_{i} − x⃗_{N}, i = 1, …, N − 1,  (98)

we have, for i, j ≠ N,

x⃗_{i} − x⃗_{j} = x⃗_{i} − x⃗_{N} + x⃗_{N} − x⃗_{j} = z⃗_{i} − z⃗_{j}.

Since x⃗_{N} is fixed, the Jacobian of this transformation is 1 and (97) becomes

Ix⃗_{N} ≤ A^{|c\a|} ∫_{IR_{d(N−1)}} ∏_{{i,j}∈a; i,j<N} |f(|z⃗_{i} − z⃗_{j}|)| ∏_{{i,N}∈a} |f(|z⃗_{i}|)|dz⃗_{1} ⋯ dz⃗_{N−1}.

Let us give the edges of a an orientation towards the “root” N. Consider the function σ : {1, …, N − 1} → {1, …, N} such that σ(i) is the end of the arrow going out of vertex i. We can write

Ix⃗_{N} ≤ A^{|c\a|} ∫_{IR_{d(N−1)}} ∏_{σ(i)<N} |f(|z⃗_{i} − z⃗_{σ(i)}|)| ∏_{{i,N}∈a} |f(|z⃗_{i}|)|dz⃗_{1} … dz⃗_{N−1}.  (99)

Let us consider the linear transformation

T : \{ \begin{matrix}y⃗_{i} = z⃗_{i} − z⃗_{σ(i)}, & σ(i) ≠ N \\ y⃗_{i} = z⃗_{i}, & σ(i) = N \end{matrix}  (100)

Let us also denote by T the corresponding (N − 1) × (N − 1) matrix. This means that for Y = (y⃗_{1}, …, y⃗_{N−1}) and Z = (z⃗_{1}, …, z⃗_{N−1}), we have Y = T Z and if we denote by

Y_{i} = (y_{1i}, y_{2i}, …, y_{(N−1) i}), Z_{i} = (z_{1i}, z_{2i}, …, z_{(N−1) i}), i = 1, …, d,

the vectors made of the i-th components of every vector y⃗_{j} and z⃗_{j}, for j = 1, …, N − 1, we also have Y_{i} = T Z_{i}. For the Jacobian, we have

|\frac{∂(z⃗_{1}, …, z⃗_{N−1})}{∂(y⃗_{1}, …, y⃗_{N−1})}| = \frac{1}{| det(T)|^{d}} .

But T is the incidence matrix of the tree a, implying that | det(T)| = 1. Applying the transformation to (99), we obtain

Ix⃗_{N} ≤ A^{|c\a|} ∫_{IR_{d·(N−1)}} ∏_{i=1}^{N−1} |f(|y⃗_{i}|)|dy⃗_{1} … dy⃗_{N−1}

= A^{|c\a|} (∫_{IR_{d}} |f(|y⃗|)|dy⃗)^{N−1} .

Hence, it suffices to show that

∫_{IR_{d}} |f(|y⃗|)|dy⃗ < ∞

to prove the integrability of Fx⃗_{N}. Going to spherical coordinates with radius r = |y⃗|, we have dy⃗ = r^{d−1}drdS because the surface element dS on the sphere of radius 1, S(0, 1), is multiplied by r^{d−1} when the point y⃗ is at distance r from the origin. Since the surface of S(0, 1) is finite, we find

∫_{IR_{d}} |f(|y⃗|)|dy⃗ = ∫_{S(0,1)} dS ∫_{0}^{∞} r^{d−1}|f(r)|dr

= ∫_{S(0,1)} dS (∫_{0}^{1} r^{d−1}|f(r)|dr + ∫_{1}^{∞} r^{d−1}|f(r)|dr)

≤ ∫_{S(0,1)} dS (∫_{0}^{1} |f(r)|dr + ∫_{1}^{∞} r^{d−1}|f(r)|dr)
≤ ∫_{S(0,1)} dS (A + ∫_{0}^{∞} r^{d−1}|f(r)|dr)
< ∞,

using (14). Therefore Fx⃗_{N} is integrable. Moreover, the transformation (98) shows that its integral is independent of x⃗_{N}.

We now can prove the existence of the thermodynamic limit and show that

w(c) := lim_{V →∞} \frac{1}{V} ∫_{V^{N}} ∏_{\{i,j\}∈c} f_{ij} dx⃗_{1} ⋯ dx⃗_{N}

= ∫_{IR_{d(N−1)}} ∏_{{i,j}∈c; x⃗_{N} =0} f_{ij}dx⃗_{1} ⋯ dx⃗_{N−1},  (101)

where f_{ij} = f(|x⃗_{i} − x⃗_{j}|). Let us consider the vessel V like a ball with radius R centered at the origin, denoted by B(0, R). More precisely,

V = B(0, R) = {x⃗ ∈ IR^{d} | |x⃗| ≤ R}.

We denote its volume by K(d)R^{d}. The thermodynamic limit can then be written as

lim_{R→∞} \frac{1}{K(d)R^{d}} ∫_{B(0,R)^{N}} ∏_{\{i,j\}∈c} f_{ij} dx⃗_{1} … dx⃗_{N}.

Let us study the function

ϵ(R, x⃗_{N}) := ∫_{IR_{d(N−1)}} ∏_{{i,j}∈c} f_{ij} dx⃗_{1} ⋯ dx⃗_{N−1} − ∫_{B(0,R)^{N−1}} ∏_{{i,j}∈c} f_{ij} dx⃗_{1} ⋯ dx⃗_{N−1}

= ∫_{IR^{d(N−1)}\B(0,R)^{N−1}} ∏_{{i,j}∈c} f_{ij} dx⃗_{1} ⋯ dx⃗_{N−1}

under the condition that |x⃗_{N}| < R. If we show that

lim_{R→∞} \frac{1}{K(d)R^{d}} ∫_{B(0,R)} |ϵ(R, x⃗_{N})|dx⃗_{N} = 0,  (102)

the identity (101) will directly follow since then

lim_{R→∞} \frac{1}{K(d)R^{d}} ∫_{B(0,R)^{N}} ∏_{\{i,j\}∈c} f_{ij} dx⃗_{1} ⋯ dx⃗_{N}

= lim_{R→∞} \frac{1}{K(d)R^{d}} ∫_{B(0,R)} [∫_{B(0,R)^{N−1}} ∏_{\{i,j\}∈c} f_{ij} dx⃗_{1} ⋯ dx⃗_{N−1}] dx⃗_{N}

= lim_{R→∞} \frac{1}{K(d)R^{d}} ∫_{B(0,R)} [∫_{IR_{d(N−1)}} ∏_{\{i,j\}∈c} f_{ij} dx⃗_{1} ⋯ dx⃗_{N−1} − ϵ(R, x⃗_{N})] dx⃗_{N}

= lim_{R→∞} \frac{1}{K(d)R^{d}} ∫_{B(0,R)} dx⃗_{N} ∫_{IR_{d(N−1)}} ∏_{\{i,j\}∈c} f_{ij} dx⃗_{1} ⋯ dx⃗_{N−1} − 0

= ∫_{IR_{d(N−1)}} ∏_{{i,j}∈c; x⃗_{N} =0} f_{ij} dx⃗_{1} ⋯ dx⃗_{N−1},

applying the translation x⃗_{i} := x⃗_{i} − x⃗_{N}, for i = 1, …, N − 1.

Now let A be defined by (96) and let again a be a spanning subtree of c, rooted at the vertex N. We have

|ϵ(R, x⃗_{N})| = |∫_{IR^{d(N−1)}\B(0,R)^{N−1}} ∏_{{i,j}∈c} f_{ij} dx⃗_{1} ⋯ dx⃗_{N−1}|

≤ ∫_{IR^{d(N−1)}\B(0,R)^{N−1}} ∏_{{i,j}∈c} |f_{ij}| dx⃗_{1} ⋯ dx⃗_{N−1}

= ∫_{IR^{d(N−1)}\B(0,R)^{N−1}} ∏_{{i,j}∈a} |f_{ij}| ∏_{{i,j}∈c\a} |f_{ij}| dx⃗_{1} ⋯ dx⃗_{N−1}

≤ A^{|c\a|} ∫_{IR^{d(N−1)}\B(0,R)^{N−1}} ∏_{{i,j}∈a} |f_{ij}| dx⃗_{1} ⋯ dx⃗_{N−1}

= A^{|c\a|} ∫_{IR^{d(N−1)}\B(0,R)^{N−1}} _{∏_{{i,j}∈a} ; i,j≠N}|f_{ij}| ∏_{{i,N}∈a} |f_{iN}| dx⃗_{1} ⋯ dx⃗_{N−1}.

We change the variables as in (98), considering x⃗_{N} as constant, and we define

D(R, x⃗_{N}) := IR^{d(N−1)} \ (B(0, R)^{N−1} − x_{N}^{N−1}),  (103)

where B(0, R)^{N−1} − x_{N}^{N−1} denotes the part B(0, R)^{N−1} translated by −x_{N}^{N−1} = −(x⃗_{N}, x⃗_{N}, …, x⃗_{N}) ∈ IR^{d(N−1)}. Then we can write

|ϵ(R, x⃗_{N})| ≤ A^{|c\a|} ∫_{D(R,x⃗_{N})} ∏_{{i,j}∈a; i,j≠N} |f(|z⃗_{i} − z⃗_{j}|)| ∏_{{i,N}∈a} |f(|z⃗_{i}|)| dz⃗_{1} … dz⃗_{N−1}.

As before, we orient the edges of a towards the root N and define a function σ such that σ(i) denotes the destination of the arrow that comes out of vertex i. We have

|ϵ(R, x⃗_{N})| ≤ A^{|c\a|} ∫_{D(R,x⃗_{N})} ∏_{σ(i)≠N} |f(|z⃗_{i} − z⃗_{σ(i)}|)| ∏_{σ(i)=N} |f(|z⃗_{i}|)| dz⃗_{1} … dz⃗_{N−1}. (104)

Applying the linear transformation T of (100) to (104), we find

|ϵ(R, x⃗_{N})| ≤ A^{|c\a|} ∫_{T (D(R,x⃗_{N}))} ∏_{i=1}^{N−1} |f(|y⃗_{i}|)| dy⃗_{1} … dy⃗_{N−1},  (105)

with

T (D(R, x⃗_{N})) = T (IR^{d(N−1)}) \ T (B(0, R)^{N−1} − x_{N}^{N−1})
= IR^{d(N−1)} \ T (B(0, R)^{N−1} − x_{N}^{N−1}) .

Since |x⃗_{N}| < R, the topological region B(0, R)^{N−1} − x_{N}^{N−1} contains the origin. Since T is continuous, this implies that T (B(0, R)^{N−1}−x_{N}^{N−1}) contains a Cartesian product of balls B(0, γ · (R − |x⃗_{N}|))^{N−1}, centered at the origin, where γ > 0 only depends on T. Thus we have

|ϵ(R, x⃗_{N})| ≤ A^{|c\a|} ∫_{IR^{d·(N−1)}\B(0,γ·(R−|x⃗_{N} |))^{N−1}} ∏_{i=1}^{N−1} |f(|y⃗_{i}|)| dy⃗_{1} … dy⃗_{N−1}

= A^{|c\a|} [(∫_{IR_{d}} |f(|y⃗|)| dy⃗)^{N−1} − (∫_{B(0,γ·(R−|x⃗_{N} |))} |f(|y⃗|)| dy⃗)^{N−1}] .

Since r^{d−1}f(r) is integrable, we can set

α = ∫_{IR_{d}} |f(|y⃗|)|dy⃗ < ∞ and β = ∫_{B(0,γ·(R−|x⃗_{N} |))} |f(|y⃗|)|dy⃗ < ∞.

Notice that α ≥ β. Since

α^{N−1} − β^{N−1} = (α − β)(α^{N−2} + α^{N−3}β + … + αβ^{N−3} + β^{N−2})
≤ (α − β)(α^{N−2} + α^{N−2} + … + α^{N−2})
= (α − β)(N − 1)α^{N−2},

we have

|ϵ(R, x⃗_{N})| ≤ A^{|c\a|}(N − 1)α^{N−2} [∫_{IR_{d}} |f(|y⃗|)|dy⃗ − ∫_{B(0,γ·(R−|x⃗_{N} |))} |f(|y⃗|)|dy⃗] . (106)

Let us denote by k the constant k = A^{|c\a|}(N − 1)α^{N−2}. Integrating both sides of (106) with respect to x⃗_{N} and dividing by the volume of the ball B(0, R) yields

\frac{1}{K(d)R^{d}} ∫_{B(0,R)} |ϵ(R, x⃗_{N})|dx⃗_{N}

≤ k · \frac{1}{K(d)R^{d}} ∫_{B(0,R)} [∫_{IR_{d}} |f(|y⃗|)|dy⃗ − ∫_{B(0,γ(R−|x⃗_{N} |))} |f(|y⃗|)|dy⃗] dx⃗_{N}

= k \frac{1}{K(d)R^{d}} ∫_{B(0,R)} ∫_{IR_{d}} |f(|y⃗|)|dy⃗dx⃗_{N}

− k \frac{1}{K(d)R^{d}} ∫_{B(0,R)} ∫_{B(0,γ(R−|x⃗_{N} |))} |f(|y⃗|)|dy⃗dx⃗_{N}

= k ∫_{IR_{d}} |f(|y⃗|)|dy⃗ − k \frac{1}{K(d)R^{d}} ∫_{B(0,R)} ∫_{B(0,γ(R−|x⃗_{N} |))} |f(|y⃗|)|dy⃗dx⃗_{N}

Let us change the order of integration of the second integral. Its domain of integration is

{(y⃗, x⃗_{N})| 0 ≤ |x⃗_{N}| < R and 0 ≤ |y⃗| < γ(R − |x⃗_{N}|)}.

If we let x⃗_{N} vary, we have, for a fixed y⃗,

0 ≤ |y⃗| < γ · (R − |x⃗_{N}|) ⇔ 0 ≤ \frac{|y⃗|}{γ} < R − |x⃗_{N}|

⇔ 0 ≤ |x⃗_{N}| < R − \frac{|y⃗|}{γ}

and we obtain

\frac{1}{K(d)R^{d}} ∫_{B(0,R)} |ϵ(R, x⃗_{N})|dx⃗_{N}

≤ k ∫_{IR_{d}} |f(|y⃗|)|dy⃗ − \frac{k}{K(d)R^{d}} ∫_{B(0,γR)} ∫_{B(0,R− \frac{|y⃗|}{γ})} dx⃗_{N}|f(|y⃗|)|dy⃗

= k ∫_{IR_{d}} |f(|y⃗|)|dy⃗ − \frac{k}{K(d)R^{d}} ∫_{B(0,γR)} K(d) (R − \frac{|y⃗|}{γ})^{d} |f(|y⃗|)|dy⃗

= k (∫_{IR_{d}} |f(|y⃗|)|dy⃗ − ∫_{B(0,γR)} (1 − \frac{|y⃗|}{γR})^{d} |f(|y⃗|)|dy⃗)

→ 0

as R ↑ ∞ by the Lebesgue dominated convergence theorem. This is easily seen by taking an increasing sequence of radii R_{n} ↑ ∞ and considering the sequence of measurable functions

(1 − \frac{|y⃗|}{γR_{n}} )^{d} |f(|y⃗|)| χ(y⃗ ∈ B(0, γR_{n}), n = 0, 1, 2, …

which are dominated by the integrable function |f(|y⃗|)| and converges pointwise to |f(|y⃗|)|.

This establishes (102), and concludes the proof. □

Appendix B. Table for 2-connected graphs of size at most 6

Key:

number degree sequence of c

graph c

Ehrhart Pol. in base n^{i}  nb of labellings nb of spanning subtrees Ehrhart Pol. in base \binom{n}{i} polytope’s volume  volume × (n − 1)!

With 2 vertices:

\begin{matrix}2 & & (1,1) \\ [figure] & \begin{matrix}2n + 1 & 1 & 1 \\ 1\binom{n}{0} + 2\binom{n}{1} & 2 & 2 \end{matrix} \end{matrix}

With 3 vertices:

32 G. LABELLE, P. LEROUX AND M. G. DUCHARME

\begin{matrix}3 & & (2,2,2) \\ [figure] & \begin{matrix}3n^{2} + 3n + 1 & 1 & 3 \\ 1\binom{n}{0} + 6\binom{n}{1} + 6\binom{n}{2} & 3 & 6 \end{matrix} \end{matrix}

With 4 vertices:

\begin{matrix}4.1 & (2,2,2,2) \\ [figure] & \begin{matrix}\frac{16}{3} n^{3} + 8 n^{2} + \frac{14}{3} n + 1 & 3 & 4 \\ 1\binom{n}{0} + 18\binom{n}{1} + 48\binom{n}{2} + 32\binom{n}{3} & \frac{16}{3} & 32 \end{matrix} \end{matrix}

\begin{matrix}4.2 & (3,3,2,2) \\ [figure] & \begin{matrix}\frac{14}{3} n^{3} + 7 n^{2} + \frac{13}{3} n + 1 & 6 & 8 \\ 1\binom{n}{0} + 16\binom{n}{1} + 42\binom{n}{2} + 28\binom{n}{3} & \frac{14}{3} & 28 \end{matrix} \end{matrix}

\begin{matrix}4.3 & (3,3,3,3) \\ [figure] & \begin{matrix}4 n^{3} + 6 n^{2} + 4 n + 1 & 1 & 16 \\ 1\binom{n}{0} + 14\binom{n}{1} + 36\binom{n}{2} + 24\binom{n}{3} & 4 & 24 \end{matrix} \end{matrix}

With 5 vertices:

\begin{matrix}5.1 & (2,2,2,2,2) \\ [figure] & \begin{matrix}\frac{115}{12} n^{4} + \frac{115}{6} n^{3} + \frac{185}{12} n^{2} + \frac{35}{6} n + 1 & 12 & 5 \\ 1\binom{n}{0} + 50\binom{n}{1} + 280\binom{n}{2} + 460\binom{n}{3} + 230\binom{n}{4} & \frac{115}{12} & 230 \end{matrix} \end{matrix}

\begin{matrix}5.2 & (3,3,2,2,2) \\ [figure] & \begin{matrix}\frac{49}{6} n^{4} + \frac{49}{3} n^{3} + \frac{83}{6} n^{2} + \frac{17}{3} n + 1 & 60 & 11 \\ 1\binom{n}{0} + 44\binom{n}{1} + 240\binom{n}{2} + 392\binom{n}{3} + 196\binom{n}{4} & \frac{49}{6} & 196 \end{matrix} \end{matrix}

\begin{matrix}5.3 & (3,3,2,2,2) \\ [figure] & \begin{matrix}8 n^{4} + 16 n^{3} + 14 n^{2} + 6 n + 1 & 10 & 12 \\ 1\binom{n}{0} + 44\binom{n}{1} + 236\binom{n}{2} + 384\binom{n}{3} + 192\binom{n}{4} & 8 & 192 \end{matrix} \end{matrix}

GRAPH WEIGHTS ARISING FROM MAYER’S THEORY OF CLUSTER INTEGRALS 33

\begin{matrix}5.4 & (4,4,2,2,2) \\ [figure] & \begin{matrix}\frac{15}{2} n^{4} + 15 n^{3} + \frac{27}{2} n^{2} + 6 n + 1 & 10 & 20 \\ 1\binom{n}{0} + 42\binom{n}{1} + 222\binom{n}{2} + 360\binom{n}{3} + 180\binom{n}{4} & \frac{15}{2} & 180 \end{matrix} \end{matrix}

\begin{matrix}5.5 & (4,3,3,2,2) \\ [figure] & \begin{matrix}\frac{29}{4} n^{4} + \frac{29}{2} n^{3} + \frac{51}{4} n^{2} + \frac{11}{2} n + 1 & 60 & 21 \\ 1\binom{n}{0} + 40\binom{n}{1} + 214\binom{n}{2} + 348\binom{n}{3} + 174\binom{n}{4} & \frac{29}{4} & 174 \end{matrix} \end{matrix}

\begin{matrix}5.6 & (3,3,3,3,2) \\ [figure] & \begin{matrix}\frac{41}{6} n^{4} + \frac{41}{3} n^{3} + \frac{73}{6} n^{2} + \frac{16}{3} n + 1 & 30 & 24 \\ 1\binom{n}{0} + 38\binom{n}{1} + 202\binom{n}{2} + 328\binom{n}{3} + 164\binom{n}{4} & \frac{41}{6} & 164 \end{matrix} \end{matrix}

\begin{matrix}5.7 & (4,4,3,3,2) \\ [figure] & \begin{matrix}\frac{19}{3} n^{4} + \frac{38}{3} n^{3} + \frac{35}{3} n^{2} + \frac{16}{3} n + 1 & 30 & 40 \\ 1\binom{n}{0} + 36\binom{n}{1} + 188\binom{n}{2} + 304\binom{n}{3} + 152\binom{n}{4} & \frac{19}{3} & 152 \end{matrix} \end{matrix}

\begin{matrix}5.8 & (4,3,3,3,3) \\ [figure] & \begin{matrix}6 n^{4} + 12 n^{3} + 11 n^{2} + 5 n + 1 & 15 & 45 \\ 1\binom{n}{0} + 34\binom{n}{1} + 178\binom{n}{2} + 288\binom{n}{3} + 144\binom{n}{4} & 6 & 144 \end{matrix} \end{matrix}

\begin{matrix}5.9 & (4,4,4,3,3) \\ [figure] & \begin{matrix}\frac{11}{2} n^{4} + 11 n^{3} + \frac{21}{2} n^{2} + 5 n + 1 & 10 & 75 \\ 1\binom{n}{0} + 32\binom{n}{1} + 164\binom{n}{2} + 264\binom{n}{3} + 132\binom{n}{4} & \frac{11}{2} & 132 \end{matrix} \end{matrix}

\begin{matrix}5.10 & (4,4,4,4,4) \\ [figure] & \begin{matrix}5 n^{4} + 10 n^{3} + 10 n^{2} + 5 n + 1 & 1 & 125 \\ 1\binom{n}{0} + 30\binom{n}{1} + 150\binom{n}{2} + 240\binom{n}{3} + 120\binom{n}{4} & 5 & 120 \end{matrix} \end{matrix}

With 6 vertices, ordered according to the number of edges:

34 G. LABELLE, P. LEROUX AND M. G. DUCHARME

\begin{matrix}6.1 & (2,2,2,2,2,2) \\ [figure] & \begin{matrix}\frac{88}{5} n^{5} + 44 n^{4} + 46 n^{3} + 25 n^{2} + \frac{37}{5} n + 1 & 60 & 6 \\ 1\binom{n}{0} + 140\binom{n}{1} + 1470\binom{n}{2} + 4500\binom{n}{3} + 5280\binom{n}{4} + 2112\binom{n}{5} & \frac{88}{5} & 2112 \end{matrix} \end{matrix}

\begin{matrix}7.1 & (3,3,2,2,2,2) \\ [figure] & \begin{matrix}\frac{72}{5} n^{5} + 36 n^{4} + \frac{118}{3} n^{3} + 23 n^{2} + \frac{109}{15} n + 1 & 180 & 15 \\ 1\binom{n}{0} + 120\binom{n}{1} + 1218\binom{n}{2} + 3692\binom{n}{3} + 4320\binom{n}{4} + 1728\binom{n}{5} & \frac{72}{5} & 1728 \end{matrix} \end{matrix}

\begin{matrix}7.2 & (3,3,2,2,2,2) \\ [figure] & \begin{matrix}\frac{439}{30} n^{5} + \frac{439}{12} n^{4} + \frac{118}{3} n^{3} + \frac{269}{12} n^{2} + \frac{211}{30} n + 1 & 360 & 14 \\ 1\binom{n}{0} + 120\binom{n}{1} + 1232\binom{n}{2} + 3748\binom{n}{3} + 4390\binom{n}{4} + 1756\binom{n}{5} & \frac{439}{30} & 1756 \end{matrix} \end{matrix}

\begin{matrix}7.3 & (3,3,2,2,2,2) \\ [figure] & \begin{matrix}\frac{419}{30} n^{5} + \frac{419}{12} n^{4} + 38 n^{3} + \frac{265}{12} n^{2} + \frac{211}{30} n + 1 & 180 & 16 \\ 1\binom{n}{0} + 116\binom{n}{1} + 1180\binom{n}{2} + 3580\binom{n}{3} + 4190\binom{n}{4} + 1676\binom{n}{5} & \frac{419}{30} & 1676 \end{matrix} \end{matrix}

\begin{matrix}8.1 & (4,4,2,2,2,2) \\ [figure] & \begin{matrix}\frac{64}{5} n^{5} + 32 n^{4} + \frac{112}{3} n^{3} + 24 n^{2} + \frac{118}{15} n + 1 & 15 & 32 \\ 1\binom{n}{0} + 114\binom{n}{1} + 1104\binom{n}{2} + 3296\binom{n}{3} + 3840\binom{n}{4} + 1536\binom{n}{5} & \frac{64}{5} & 1536 \end{matrix} \end{matrix}

\begin{matrix}8.2 & (4,4,2,2,2,2) \\ [figure] & \begin{matrix}\frac{194}{15} n^{5} + \frac{97}{3} n^{4} + 36 n^{3} + \frac{65}{3} n^{2} + \frac{106}{15} n + 1 & 180 & 28 \\ 1\binom{n}{0} + 110\binom{n}{1} + 1100\binom{n}{2} + 3320\binom{n}{3} + 3880\binom{n}{4} + 1552\binom{n}{5} & \frac{194}{15} & 1552 \end{matrix} \end{matrix}

\begin{matrix}8.3 & (4,3,3,2,2,2) \\ [figure] & \begin{matrix}\frac{37}{3} n^{5} + \frac{185}{6} n^{4} + \frac{104}{3} n^{3} + \frac{127}{6} n^{2} + 7 n + 1 & 360 & 32 \\ 1\binom{n}{0} + 106\binom{n}{1} + 1052\binom{n}{2} + 3168\binom{n}{3} + 3700\binom{n}{4} + 1480\binom{n}{5} & \frac{37}{3} & 1480 \end{matrix} \end{matrix}

\begin{matrix}8.4 & (4,3,3,2,2,2,2) \\ [figure] & \begin{matrix}\frac{127}{10} n^{5} + \frac{127}{4} n^{4} + \frac{106}{3} n^{3} + \frac{85}{4} n^{2} + \frac{209}{30} n + 1 & 720 & 29 \\ 1\binom{n}{0} + 108\binom{n}{1} + 1080\binom{n}{2} + 3260\binom{n}{3} + 3810\binom{n}{4} + 1524\binom{n}{5} & \frac{127}{10} & 1524 \end{matrix} \end{matrix}

\begin{matrix}8.5 & (4,3,3,2,2,2) \\ [figure] & \begin{matrix}\frac{188}{15} n^{5} + \frac{94}{3} n^{4} + \frac{104}{3} n^{3} + \frac{62}{3} n^{2} + \frac{34}{5} n + 1 & 360 & 30 \\ 1\binom{n}{0} + 106\binom{n}{1} + 1064\binom{n}{2} + 3216\binom{n}{3} + 3760\binom{n}{4} + 1504\binom{n}{5} & \frac{188}{15} & 1504 \end{matrix} \end{matrix}

\begin{matrix}8.6 & (3,3,3,3,2,2) \\ [figure] & \begin{matrix}\frac{188}{15} n^{5} + \frac{94}{3} n^{4} + \frac{104}{3} n^{3} + \frac{62}{3} n^{2} + \frac{34}{5} n + 1 & 180 & 30 \\ 1\binom{n}{0} + 106\binom{n}{1} + 1064\binom{n}{2} + 3216\binom{n}{3} + 3760\binom{n}{4} + 1504\binom{n}{5} & \frac{188}{15} & 1504 \end{matrix} \end{matrix}

\begin{matrix}8.7 & (3,3,3,3,2,2) \\ [figure] & \begin{matrix}\frac{361}{30} n^{5} + \frac{361}{12} n^{4} + \frac{100}{3} n^{3} + \frac{239}{12} n^{2} + \frac{199}{30} n + 1 & 180 & 32 \\ 1\binom{n}{0} + 102\binom{n}{1} + 1022\binom{n}{2} + 3088\binom{n}{3} + 3610\binom{n}{4} + 1444\binom{n}{5} & \frac{361}{30} & 1444 \end{matrix} \end{matrix}

\begin{matrix}8.8 & (3,3,3,3,2,2) \\ [figure] & \begin{matrix}\frac{176}{15} n^{5} + \frac{88}{3} n^{4} + \frac{100}{3} n^{3} + \frac{62}{3} n^{2} + \frac{104}{15} n + 1 & 90 & 36 \\ 1\binom{n}{0} + 102\binom{n}{1} + 1004\binom{n}{2} + 3016\binom{n}{3} + 3520\binom{n}{4} + 1408\binom{n}{5} & \frac{176}{15} & 1408 \end{matrix} \end{matrix}

\begin{matrix}8.9 & (3,3,3,3,2,2) \\ [figure] & \begin{matrix}\frac{117}{10} n^{5} + \frac{117}{4} n^{4} + \frac{98}{3} n^{3} + \frac{79}{4} n^{2} + \frac{199}{30} n + 1 & 360 & 35 \\ 1\binom{n}{0} + 100\binom{n}{1} + 996\binom{n}{2} + 3004\binom{n}{3} + 3510\binom{n}{4} + 1404\binom{n}{5} & \frac{117}{10} & 1404 \end{matrix} \end{matrix}

\begin{matrix}9.1 & (5,5,2,2,2,2) \\ [figure] & \begin{matrix}\frac{62}{5} n^{5} + 31 n^{4} + \frac{110}{3} n^{3} + 24 n^{2} + \frac{119}{15} n + 1 & 15 & 48 \\ 1\binom{n}{0} + 112\binom{n}{1} + 1074\binom{n}{2} + 3196\binom{n}{3} + 3720\binom{n}{4} + 1488\binom{n}{5} & \frac{62}{5} & 1488 \end{matrix} \end{matrix}

\begin{matrix}9.2 & (5,4,3,2,2,2) \\ [figure] & \begin{matrix}\frac{349}{30} n^{5} + \frac{349}{12} n^{4} + \frac{100}{3} n^{3} + \frac{251}{12} n^{2} + \frac{211}{30} n + 1 & 360 & 52 \\ 1\binom{n}{0} + 102\binom{n}{1} + 998\binom{n}{2} + 2992\binom{n}{3} + 3490\binom{n}{4} + 1396\binom{n}{5} & \frac{349}{30} & 1396 \end{matrix} \end{matrix}

\begin{matrix}9.3 & (5,3,3,3,2,2) \\ [figure] & \begin{matrix}\frac{169}{15} n^{5} + \frac{169}{6} n^{4} + 32 n^{3} + \frac{119}{6} n^{2} + \frac{101}{15} n + 1 & 360 & 55 \\ 1\binom{n}{0} + 98\binom{n}{1} + 964\binom{n}{2} + 2896\binom{n}{3} + 3380\binom{n}{4} + 1352\binom{n}{5} & \frac{169}{15} & 1352 \end{matrix} \end{matrix}

36 G. LABELLE, P. LEROUX AND M. G. DUCHARME

\begin{matrix}9.4 & (4,4,4,2,2,2) \\ [figure] & \begin{matrix}\frac{113}{10} n^{5} + \frac{113}{4} n^{4} + 32 n^{3} + \frac{79}{4} n^{2} + \frac{67}{10} n + 1 & 120 & 54 \\ 1\binom{n}{0} + 98\binom{n}{1} + 966\binom{n}{2} + 2904\binom{n}{3} + 3390\binom{n}{4} + 1356\binom{n}{5} & \frac{113}{10} & 1356 \end{matrix} \end{matrix}

\begin{matrix}9.5 & (4,4,3,3,2,2) \\ [figure] & \begin{matrix}11 n^{5} + \frac{55}{2} n^{4} + \frac{94}{3} n^{3} + \frac{39}{2} n^{2} + \frac{20}{3} n + 1 & 180 & 56 \\ 1\binom{n}{0} + 96\binom{n}{1} + 942\binom{n}{2} + 2828\binom{n}{3} + 3300\binom{n}{4} + 1320\binom{n}{5} & 11 & 1320 \end{matrix} \end{matrix}

\begin{matrix}9.6 & (4,4,3,3,2,2) \\ [figure] & \begin{matrix}\frac{169}{15} n^{5} + \frac{169}{6} n^{4} + 32 n^{3} + \frac{119}{6} n^{2} + \frac{101}{15} n + 1 & 360 & 55 \\ 1\binom{n}{0} + 98\binom{n}{1} + 964\binom{n}{2} + 2896\binom{n}{3} + 3380\binom{n}{4} + 1352\binom{n}{5} & \frac{169}{15} & 1352 \end{matrix} \end{matrix}

\begin{matrix}9.7 & (4,4,3,3,2,2) \\ [figure] & \begin{matrix}\frac{163}{15} n^{5} + \frac{163}{6} n^{4} + \frac{94}{3} n^{3} + \frac{119}{6} n^{2} + \frac{34}{5} n + 1 & 180 & 60 \\ 1\binom{n}{0} + 96\binom{n}{1} + 934\binom{n}{2} + 2796\binom{n}{3} + 3260\binom{n}{4} + 1304\binom{n}{5} & \frac{163}{15} & 1304 \end{matrix} \end{matrix}

\begin{matrix}9.8 & (4,4,3,3,2,2) \\ [figure] & \begin{matrix}\frac{161}{15} n^{5} + \frac{161}{6} n^{4} + \frac{94}{3} n^{3} + \frac{121}{6} n^{2} + \frac{104}{15} n + 1 & 90 & 64 \\ 1\binom{n}{0} + 96\binom{n}{1} + 926\binom{n}{2} + 2764\binom{n}{3} + 3220\binom{n}{4} + 1288\binom{n}{5} & \frac{161}{15} & 1288 \end{matrix} \end{matrix}

\begin{matrix}9.9 & (4,4,3,3,2,2) \\ [figure] & \begin{matrix}\frac{161}{15} n^{5} + \frac{161}{6} n^{4} + \frac{92}{3} n^{3} + \frac{115}{6} n^{2} + \frac{33}{5} n + 1 & 720 & 61 \\ 1\binom{n}{0} + 94\binom{n}{1} + 920\binom{n}{2} + 2760\binom{n}{3} + 3220\binom{n}{4} + 1288\binom{n}{5} & \frac{161}{15} & 1288 \end{matrix} \end{matrix}

\begin{matrix}9.10 & (4,3,3,3,3,2) \\ [figure] & \begin{matrix}\frac{51}{5} n^{5} + \frac{51}{2} n^{4} + \frac{88}{3} n^{3} + \frac{37}{2} n^{2} + \frac{97}{15} n + 1 & 360 & 69 \\ 1\binom{n}{0} + 90\binom{n}{1} + 876\binom{n}{2} + 2624\binom{n}{3} + 3060\binom{n}{4} + 1224\binom{n}{5} & \frac{51}{5} & 1224 \end{matrix} \end{matrix}

\begin{matrix}9.11 & (4,3,3,3,3,2) \\ [figure] & \begin{matrix}\frac{103}{10} n^{5} + \frac{103}{4} n^{4} + \frac{88}{3} n^{3} + \frac{73}{4} n^{2} + \frac{191}{30} n + 1 & 360 & 66 \\ 1\binom{n}{0} + 90\binom{n}{1} + 882\binom{n}{2} + 2648\binom{n}{3} + 3090\binom{n}{4} + 1236\binom{n}{5} & \frac{103}{10} & 1236 \end{matrix} \end{matrix}

\begin{matrix}9.12 & (4,3,3,3,3,2) \\ [figure] & \begin{matrix}\frac{158}{15} n^{5} + \frac{79}{3} n^{4} + 30 n^{3} + \frac{56}{3} n^{2} + \frac{97}{15} n + 1 & 360 & 64 \\ 1\binom{n}{0} + 92\binom{n}{1} + 902\binom{n}{2} + 2708\binom{n}{3} + 3160\binom{n}{4} + 1264\binom{n}{5} & \frac{158}{15} & 1264 \end{matrix} \end{matrix}

\begin{matrix}9.13 & (3,3,3,3,3,3) \\ [figure] & \begin{matrix}\frac{48}{5} n^{5} + 24 n^{4} + 28 n^{3} + 18 n^{2} + \frac{32}{5} n + 1 & 10 & 81 \\ 1\binom{n}{0} + 86\binom{n}{1} + 828\binom{n}{2} + 2472\binom{n}{3} + 2880\binom{n}{4} + 1152\binom{n}{5} & \frac{48}{5} & 1152 \end{matrix} \end{matrix}

\begin{matrix}9.14 & (3,3,3,3,3,3) \\ [figure] & \begin{matrix}\frac{49}{5} n^{5} + \frac{49}{2} n^{4} + 28 n^{3} + \frac{35}{2} n^{2} + \frac{31}{5} n + 1 & 60 & 75 \\ 1\binom{n}{0} + 86\binom{n}{1} + 840\binom{n}{2} + 2520\binom{n}{3} + 2940\binom{n}{4} + 1176\binom{n}{5} & \frac{49}{5} & 1176 \end{matrix} \end{matrix}

\begin{matrix}10.1 & (5,5,3,3,2,2) \\ [figure] & \begin{matrix}\frac{31}{3} n^{5} + \frac{155}{6} n^{4} + \frac{92}{3} n^{3} + \frac{121}{6} n^{2} + 7 n + 1 & 90 & 96 \\ 1\binom{n}{0} + 94\binom{n}{1} + 896\binom{n}{2} + 2664\binom{n}{3} + 3100\binom{n}{4} + 1240\binom{n}{5} & \frac{31}{3} & 1240 \end{matrix} \end{matrix}

\begin{matrix}10.2 & (5,4,4,3,2,2) \\ [figure] & \begin{matrix}\frac{301}{30} n^{5} + \frac{301}{12} n^{4} + \frac{88}{3} n^{3} + \frac{227}{12} n^{2} + \frac{199}{30} n + 1 & 360 & 99 \\ 1\binom{n}{0} + 90\binom{n}{1} + 866\binom{n}{2} + 2584\binom{n}{3} + 3010\binom{n}{4} + 1204\binom{n}{5} & \frac{301}{30} & 1204 \end{matrix} \end{matrix}

\begin{matrix}10.3 & (5,4,3,3,3,2) \\ [figure] & \begin{matrix}\frac{287}{30} n^{5} + \frac{287}{12} n^{4} + 28 n^{3} + \frac{217}{12} n^{2} + \frac{193}{30} n + 1 & 360 & 111 \\ 1\binom{n}{0} + 86\binom{n}{1} + 826\binom{n}{2} + 2464\binom{n}{3} + 2870\binom{n}{4} + 1148\binom{n}{5} & \frac{287}{30} & 1148 \end{matrix} \end{matrix}

\begin{matrix}10.4 & (5,4,3,3,3,2) \\ [figure] & \begin{matrix}\frac{59}{6} n^{5} + \frac{295}{12} n^{4} + \frac{86}{3} n^{3} + \frac{221}{12} n^{2} + 13/2 n + 1 & 360 & 104 \\ 1\binom{n}{0} + 88\binom{n}{1} + 848\binom{n}{2} + 2532\binom{n}{3} + 2950\binom{n}{4} + 1180\binom{n}{5} & \frac{59}{6} & 1180 \end{matrix} \end{matrix}

\begin{matrix}10.5 & (5,3,3,3,3,3) \\ [figure] & \begin{matrix}\frac{55}{6} n^{5} + \frac{275}{12} n^{4} + \frac{80}{3} n^{3} + \frac{205}{12} n^{2} + \frac{37}{6} n + 1 & 72 & 121 \\ 1\binom{n}{0} + 82\binom{n}{1} + 790\binom{n}{2} + 2360\binom{n}{3} + 2750\binom{n}{4} + 1100\binom{n}{5} & \frac{55}{6} & 1100 \end{matrix} \end{matrix}

38 G. LABELLE, P. LEROUX AND M. G. DUCHARME

\begin{matrix}10.6 & (4,4,4,4,2,2) \\ [figure] & \begin{matrix}10 n^{5} + 25 n^{4} + \frac{88}{3} n^{3} + 19 n^{2} + \frac{20}{3} n + 1 & 90 & 100 \\ 1\binom{n}{0} + 90\binom{n}{1} + 864\binom{n}{2} + 2576\binom{n}{3} + 3000\binom{n}{4} + 1200\binom{n}{5} & 10 & 1200 \end{matrix} \end{matrix}

\begin{matrix}10.7 & (4,4,4,3,3,2) \\ [figure] & \begin{matrix}\frac{47}{5} n^{5} + \frac{47}{2} n^{4} + \frac{82}{3} n^{3} + \frac{35}{2} n^{2} + \frac{94}{15} n + 1 & 360 & 114 \\ 1\binom{n}{0} + 84\binom{n}{1} + 810\binom{n}{2} + 2420\binom{n}{3} + 2820\binom{n}{4} + 1128\binom{n}{5} & \frac{47}{5} & 1128 \end{matrix} \end{matrix}

\begin{matrix}10.8 & (4,4,4,3,3,2) \\ [figure] & \begin{matrix}\frac{139}{15} n^{5} + \frac{139}{6} n^{4} + \frac{82}{3} n^{3} + \frac{107}{6} n^{2} + \frac{32}{5} n + 1 & 180 & 120 \\ 1\binom{n}{0} + 84\binom{n}{1} + 802\binom{n}{2} + 2388\binom{n}{3} + 2780\binom{n}{4} + 1112\binom{n}{5} & \frac{139}{15} & 1112 \end{matrix} \end{matrix}

\begin{matrix}10.9 & (4,4,4,3,3,2) \\ [figure] & \begin{matrix}\frac{28}{3} n^{5} + \frac{70}{3} n^{4} + \frac{82}{3} n^{3} + \frac{53}{3} n^{2} + \frac{19}{3} n + 1 & 360 & 115 \\ 1\binom{n}{0} + 84\binom{n}{1} + 806\binom{n}{2} + 2404\binom{n}{3} + 2800\binom{n}{4} + 1120\binom{n}{5} & \frac{28}{3} & 1120 \end{matrix} \end{matrix}

\begin{matrix}10.10 & (4,4,3,3,3,3) \\ [figure] & \begin{matrix}\frac{136}{15} n^{5} + \frac{68}{3} n^{4} + \frac{80}{3} n^{3} + \frac{52}{3} n^{2} + \frac{94}{15} n + 1 & 45 & 128 \\ 1\binom{n}{0} + 82\binom{n}{1} + 784\binom{n}{2} + 2336\binom{n}{3} + 2720\binom{n}{4} + 1088\binom{n}{5} & \frac{136}{15} & 1088 \end{matrix} \end{matrix}

\begin{matrix}10.11 & (4,4,3,3,3,3) \\ [figure] & \begin{matrix}\frac{44}{5} n^{5} + 22 n^{4} + 26 n^{3} + 17 n^{2} + \frac{31}{5} n + 1 & 60 & 135 \\ 1\binom{n}{0} + 80\binom{n}{1} + 762\binom{n}{2} + 2268\binom{n}{3} + 2640\binom{n}{4} + 1056\binom{n}{5} & \frac{44}{5} & 1056 \end{matrix} \end{matrix}

\begin{matrix}10.12 & (4,4,3,3,3,3) \\ [figure] & \begin{matrix}\frac{89}{10} n^{5} + \frac{89}{4} n^{4} + 26 n^{3} + \frac{67}{4} n^{2} + \frac{61}{10} n + 1 & 360 & 130 \\ 1\binom{n}{0} + 80\binom{n}{1} + 768\binom{n}{2} + 2292\binom{n}{3} + 2670\binom{n}{4} + 1068\binom{n}{5} & \frac{89}{10} & 1068 \end{matrix} \end{matrix}

\begin{matrix}11.1 & (5,5,4,3,3,2) \\ [figure] & \begin{matrix}\frac{133}{15} n^{5} + \frac{133}{6} n^{4} + \frac{80}{3} n^{3} + \frac{107}{6} n^{2} + \frac{97}{15} n + 1 & 180 & 180 \\ 1\binom{n}{0} + 82\binom{n}{1} + 772\binom{n}{2} + 2288\binom{n}{3} + 2660\binom{n}{4} + 1064\binom{n}{5} & \frac{133}{15} & 1064 \end{matrix} \end{matrix}

\begin{matrix}11.2 & (5,5,3,3,3,3) \\ [figure] & \begin{matrix}\frac{26}{3} n^{5} + \frac{65}{3} n^{4} + 26 n^{3} + \frac{52}{3} n^{2} + \frac{19}{3} n + 1 & 45 & 192 \\ 1\binom{n}{0} + 80\binom{n}{1} + 754\binom{n}{2} + 2236\binom{n}{3} + 2600\binom{n}{4} + 1040\binom{n}{5} & \frac{26}{3} & 1040 \end{matrix} \end{matrix}

\begin{matrix}11.3 & (5,4,4,4,3,2) \\ [figure] & \begin{matrix}\frac{87}{10} n^{5} + \frac{87}{4} n^{4} + 26 n^{3} + \frac{69}{4} n^{2} + \frac{63}{10} n + 1 & 360 & 185 \\ 1\binom{n}{0} + 80\binom{n}{1} + 756\binom{n}{2} + 2244\binom{n}{3} + 2610\binom{n}{4} + 1044\binom{n}{5} & \frac{87}{10} & 1044 \end{matrix} \end{matrix}

\begin{matrix}11.4 & (5,4,4,3,3,3) \\ [figure] & \begin{matrix}\frac{124}{15} n^{5} + \frac{62}{3} n^{4} + \frac{74}{3} n^{3} + \frac{49}{3} n^{2} + \frac{91}{15} n + 1 & 360 & 209 \\ 1\binom{n}{0} + 76\binom{n}{1} + 718\binom{n}{2} + 2132\binom{n}{3} + 2480\binom{n}{4} + 992\binom{n}{5} & \frac{124}{15} & 992 \end{matrix} \end{matrix}

\begin{matrix}11.5 & (5,4,4,3,3,3) \\ [figure] & \begin{matrix}\frac{41}{5} n^{5} + \frac{41}{2} n^{4} + \frac{74}{3} n^{3} + \frac{33}{2} n^{2} + \frac{92}{15} n + 1 & 60 & 216 \\ 1\binom{n}{0} + 76\binom{n}{1} + 714\binom{n}{2} + 2116\binom{n}{3} + 2460\binom{n}{4} + 984\binom{n}{5} & \frac{41}{5} & 984 \end{matrix} \end{matrix}

\begin{matrix}11.6 & (4,4,4,4,4,2) \\ [figure] & \begin{matrix}\frac{42}{5} n^{5} + 21 n^{4} + \frac{76}{3} n^{3} + 17 n^{2} + \frac{94}{15} n + 1 & 60 & 200 \\ 1\binom{n}{0} + 78\binom{n}{1} + 732\binom{n}{2} + 2168\binom{n}{3} + 2520\binom{n}{4} + 1008\binom{n}{5} & \frac{42}{5} & 1008 \end{matrix} \end{matrix}

\begin{matrix}11.7 & (4,4,4,4,3,3) \\ [figure] & \begin{matrix}\frac{241}{30} n^{5} + \frac{241}{12} n^{4} + 24 n^{3} + \frac{191}{12} n^{2} + \frac{179}{30} n + 1 & 180 & 224 \\ 1\binom{n}{0} + 74\binom{n}{1} + 698\binom{n}{2} + 2072\binom{n}{3} + 2410\binom{n}{4} + 964\binom{n}{5} & \frac{241}{30} & 964 \end{matrix} \end{matrix}

\begin{matrix}11.8 & (4,4,4,4,3,3) \\ [figure] & \begin{matrix}8 n^{5} + 20 n^{4} + 24 n^{3} + 16 n^{2} + 6 n + 1 & 90 & 225 \\ 1\binom{n}{0} + 74\binom{n}{1} + 696\binom{n}{2} + 2064\binom{n}{3} + 2400\binom{n}{4} + 960\binom{n}{5} & 8 & 960 \end{matrix} \end{matrix}

\begin{matrix}12.1 & (5,5,5,3,3,3) \\ [figure] & \begin{matrix}\frac{39}{5} n^{5} + \frac{39}{2} n^{4} + 24 n^{3} + \frac{33}{2} n^{2} + \frac{31}{5} n + 1 & 20 & 324 \\ 1\binom{n}{0} + 74\binom{n}{1} + 684\binom{n}{2} + 2016\binom{n}{3} + 2340\binom{n}{4} + 936\binom{n}{5} & \frac{39}{5} & 936 \end{matrix} \end{matrix}

40 G. LABELLE, P. LEROUX AND M. G. DUCHARME

\begin{matrix}12.2 & (5,5,4,4,4,2) \\ [figure] & \begin{matrix}8 n^{5} + 20 n^{4} + \frac{74}{3} n^{3} + 17 n^{2} + \frac{19}{3} n + 1 & 60 & 300 \\ 1\binom{n}{0} + 76\binom{n}{1} + 702\binom{n}{2} + 2068\binom{n}{3} + 2400\binom{n}{4} + 960\binom{n}{5} & 8 & 960 \end{matrix} \end{matrix}

\begin{matrix}12.3 & (5,5,4,4,3,3) \\ [figure] & \begin{matrix}\frac{229}{30} n^{5} + \frac{229}{12} n^{4} + \frac{70}{3} n^{3} + \frac{191}{12} n^{2} + \frac{181}{30} n + 1 & 180 & 336 \\ 1\binom{n}{0} + 72\binom{n}{1} + 668\binom{n}{2} + 1972\binom{n}{3} + 2290\binom{n}{4} + 916\binom{n}{5} & \frac{229}{30} & 916 \end{matrix} \end{matrix}

\begin{matrix}12.4 & (5,4,4,4,4,3) \\ [figure] & \begin{matrix}\frac{37}{5} n^{5} + \frac{37}{2} n^{4} + \frac{68}{3} n^{3} + \frac{31}{2} n^{2} + \frac{89}{15} n + 1 & 180 & 360 \\ 1\binom{n}{0} + 70\binom{n}{1} + 648\binom{n}{2} + 1912\binom{n}{3} + 2220\binom{n}{4} + 888\binom{n}{5} & \frac{37}{5} & 888 \end{matrix} \end{matrix}

\begin{matrix}12.5 & (4,4,4,4,4,4) \\ [figure] & \begin{matrix}\frac{36}{5} n^{5} + 18 n^{4} + 22 n^{3} + 15 n^{2} + \frac{29}{5} n + 1 & 15 & 384 \\ 1\binom{n}{0} + 68\binom{n}{1} + 630\binom{n}{2} + 1860\binom{n}{3} + 2160\binom{n}{4} + 864\binom{n}{5} & \frac{36}{5} & 864 \end{matrix} \end{matrix}

\begin{matrix}13.1 & (5,5,5,4,4,3) \\ [figure] & \begin{matrix}7 n^{5} + \frac{35}{2} n^{4} + 22 n^{3} + \frac{31}{2} n^{2} + 6 n + 1 & 60 & 540 \\ 1\binom{n}{0} + 68\binom{n}{1} + 618\binom{n}{2} + 1812\binom{n}{3} + 2100\binom{n}{4} + 840\binom{n}{5} & 7 & 840 \end{matrix} \end{matrix}

\begin{matrix}13.2 & (5,5,4,4,4,4) \\ [figure] & \begin{matrix}\frac{34}{5} n^{5} + 17 n^{4} + \frac{64}{3} n^{3} + 15 n^{2} + \frac{88}{15} n + 1 & 45 & 576 \\ 1\binom{n}{0} + 66\binom{n}{1} + 600\binom{n}{2} + 1760\binom{n}{3} + 2040\binom{n}{4} + 816\binom{n}{5} & \frac{34}{5} & 816 \end{matrix} \end{matrix}

\begin{matrix}14.1 & (5,5,5,5,4,4) \\ [figure] & \begin{matrix}\frac{32}{5} n^{5} + 16 n^{4} + \frac{63}{3} n^{3} + 15 n^{2} + \frac{89}{15} n + 1 & 15 & 864 \\ 1\binom{n}{0} + 64\binom{n}{1} + 570\binom{n}{2} + 1660\binom{n}{3} + 1920\binom{n}{4} + 768\binom{n}{5} & \frac{32}{5} & 768 \end{matrix} \end{matrix}

\begin{matrix}15.1 & (5,5,5,5,5,5) \\ [figure] & \begin{matrix}6 n^{5} + 15 n^{4} + 20 n^{3} + 15 n^{2} + 6 n + 1 & 1 & 1296 \\ 1\binom{n}{0} + 62\binom{n}{1} + 540\binom{n}{2} + 1560\binom{n}{3} + 1800\binom{n}{4} + 720\binom{n}{5} & 6 & 720 \end{matrix} \end{matrix}