Séminaire Lotharingien de Combinatoire 61A (2009), Article B61Ae

SOME VARIANTS OF THE EXPONENTIAL FORMULA, WITH APPLICATION TO THE MULTIVARIATE TUTTE

POLYNOMIAL (ALIAS POTTS MODEL)

Alexander D. Scott

Mathematical Institute, University of Oxford 24–29 St. Giles, Oxford OX1 3LB, England.

                    E-mail: scott@maths.ox.ac.uk

Alan D. Sokal^{†}

Department of Physics, New York University 4 Washington Place, New York, NY 10003 USA.

                        E-mail: sokal@nyu.edu

Dedicated to the memory of Pierre Leroux

Abstract. We prove some variants of the exponential formula and apply them to the multivariate Tutte polynomials (also known as Potts-model partition functions) of graphs. We also prove some further identities for the multivariate Tutte polynomial, which generalize an identity for counting connected graphs found by Riordan, Nijenhuis, Wilf and Kreweras and in more general form by Leroux and Gessel, and an identity for the inversion enumerator of trees found by Mallows, Riordan and Kreweras. Finally, we prove a generalization of Möbius inversion on the partition lattice.

1. Introduction

Let {c_{n}}_{n=1}^{∞} be a sequence of coefficients, and let

C(x) = ∑_{n=1}^{∞} c_{n} \frac{x^{n}}{n!}  (1.1)

be the corresponding exponential generating function, considered as a formal power series in the indeterminate x. Now let q be another (commuting) indeterminate^{1}, and

2000 Mathematics Subject Classification. 05A19 (Primary); 05A15, 05A18, 05C15, 05C30, 05C99, 06A07, 82B20 (Secondary).

Key words and phrases. Exponential formula, generating function, sequence of binomial type, convolution family, graph, connected component, Tutte polynomial, Potts model, complete graph, inversion enumerator for trees, Abel’s binomial identity, Chu–Vandermonde convolution, Rothe’s identity, Möbius inversion, partition lattice.

† Also at Department of Mathematics, University College London, London WC1E 6BT, England. 1Let us stress that this q has nothing to do with the q of q-series; rather, it is connected with the

q of the q-state Potts model [44, 68, 69] and of the multivariate Tutte polynomial [57].

define

A_{q}(x) = exp[qC(x)] = ∑_{n=0}^{∞} a_{n}(q) \frac{x^{n}}{n!} ,  (1.2)

so that A_{q}(x) = A(x)^{q} [we write A(x) = A_{1}(x)]. It is easy to see that:

(a) Each coefficient a_{n}(q) is a polynomial in q, of degree at most n; indeed we have the explicit formula^{2}

a_{n}(q) = ∑_{ℓ=0}^{n} \frac{q^{ℓ}}{ℓ!} ∑_{\begin{matrix}n_{1}, …, n_{ℓ} ≥ 1 \\ ∑ n_{j} = n \end{matrix}} \binom{n}{n_{1}, …, n_{ℓ}} ∏_{j=1}^{ℓ} c_{n_{j}} .  (1.3)

(b) a_{0}(q) = 1.

(c) For n ≠ 0, the polynomial a_{n}(q) has zero constant term, so that we can write a_{n}(q) = qâ_{n}(q) where â_{n}(q) is a polynomial of degree at most n − 1; moreover we have â_{n}(0) = c_{n}.

For some purposes it is convenient to introduce the modified generating function

Â_{q}(x) = \frac{A_{q}(x) − 1}{q} = \frac{exp[qC(x)] − 1}{q} = ∑_{n=1}^{∞} â_{n}(q) \frac{x^{n}}{n!} .  (1.4)

The coefficients {a_{n}(q)}_{n=0}^{∞} furthermore satisfy the following identities [23]:^{3}

∑_{k=0}^{n} \binom{n}{k} a_{k}(q_{1}) a_{n−k}(q_{2}) = a_{n}(q_{1} + q_{2})  (1.5)

∑_{k=1}^{n} \binom{n}{k} k â_{k}(q_{1}) a_{n−k}(q_{2}) = n â_{n}(q_{1} + q_{2}) for n ≥ 1  (1.6)

Indeed, (1.5) follows from writing the trivial identity

A_{q_{1}}(x)A_{q_{2}}(x) = A_{q_{1}+q_{2}}(x)  (1.7)

and extracting the coefficient of x^{n}, while (1.6) follows analogously from

A_{q_{2}}(x) [x\frac{d}{dx} \frac{A_{q_{1}}(x) − 1}{q_{1}}] = x\frac{d}{dx} \frac{A_{q_{1}+q_{2}}(x) − 1}{q_{1} + q_{2}}  (1.8)

[23, eq. (4.3)], which is an easy consequence of (1.2). Specializing (1.6) to q_{1} = 0, or alternatively applying x\frac{d}{dx} directly to (1.2), we obtain the well-known recursion relation [67, Theorem 3.10.1]

a_{n}(q) = q ∑_{k=1}^{n} \binom{n − 1}{k − 1} c_{k} a_{n−k}(q) for n ≥ 1 ,  (1.9)

2This formula holds also for n = 0 because the integer 0 has exactly one ordered partition (n_{1}, …, n_{ℓ}) into zero or more strictly positive parts: namely, we have ℓ = 0 parts, and the multinomial coefficient and the empty product both equal 1, correctly giving a_{0}(q) = 1.

3See Gould [23] for fascinating comments on the history of identities equivalent to (1.6) [or to (1.10) below], which apparently go back to Euler (1748), Rothe (1793), Hindenburg (1796), von Ettingshausen (1826) and Hanstead (1881), among others.

which allows the {a_{n}(q)} to be calculated given the {c_{n}}, or vice versa. More generally, we can form the linear combination n×(1.5)−(q_{1} +q_{2})×(1.6) to obtain the recursion relation^{4}

a_{n}(q_{2}) = ∑_{k=1}^{n} [\binom{n − 1}{k − 1}(q_{1} + q_{2}) − \binom{n}{k}q_{1}] â_{k}(q_{1}) a_{n−k}(q_{2})  (1.10a)

= ∑_{k=1}^{n} [\binom{n − 1}{k − 1}q_{2} − \binom{n − 1}{k}q_{1}] â_{k}(q_{1}) a_{n−k}(q_{2})  (1.10b)

for n ≥ 1, which allows the {a_{n}(q_{2})} to be calculated given the {â_{n}(q_{1})} for any fixed q_{1}, and which reduces to (1.9) when q_{1} = 0. We do not know whether there exist useful analogues of (1.5)/(1.6) with higher powers of k on the left-hand side.

Combinatorially, all these identities are versions of the exponential formula [5,13,14, 60,64,67], which relates the weights c_{n} of “connected” objects to the weights a_{n}(q) of “all” objects, when the weight of an object is defined to be the product of the weights of its “connected components” times a factor q for each connected component.^{5} This idea can be formalized in the following combinatorial model: Let Π_{n} be the set of partitions of [n] ≡ {1, …, n} into (zero or more) nonempty blocks; give a partition

π = {π_{1}, …, π_{ℓ}} a weight w(π) = q^{ℓ} ∏_{i=1}^{ℓ} c_{|π_{i}|}, where {c_{k}}_{k=1}^{∞} are arbitrary coefficients^{6};

and let a_{n}(q) = ∑_{π∈Π_{n}} w(π). Then (1.3) is immediate: the multinomial coefficient

counts the ordered partitions of [n] into blocks of sizes n_{1}, …, n_{ℓ}, and the 1/ℓ! converts this to unordered partitions. As for (1.5)/(1.6), we first observe that a_{n}(q_{1} + q_{2}) can be computed by allowing each block to be colored either “1” (with weight q_{1}) or “2” (with weight q_{2}). Identity (1.5) follows by defining S ⊆ [n] to be the set of elements colored “1”, and setting k = |S|. Analogously, â_{n}(q_{1}+q_{2}) can be computed by coloring and weighting blocks as before, except that the block containing one specified element i ∈ [n] (say, i = 1) must be colored “1” and it receives weight 1 instead of weight q_{1}. Defining again S ⊆ [n] to be the set of elements colored “1”, and setting k = |S|, we obtain (1.6) in the form^{7}

4See [23, eq. (1.3)] or [59, Exercise 1.39, pp. 50 and 62] for the case q_{1} = 1, which is of course trivially equivalent to the general case of q_{1} ≠ 0.

5In the theory of combinatorial species [5], the exponential formula is merely a special case of the more general concept of composition (or substitution) of species F ∘ G [5, Section 1.4], which is defined so that the exponential generating function of F ∘ G is the composition of the exponential generating functions of F and G. When F is taken to be the species E of sets (ensembles in French)

and H is some species for which there exists a reasonable notion of connectedness, then, letting H^{c} be the subspecies of connected H-structures, we have the isomorphism of species H = E ∘ H^{c}; since the exponential generating function of E is exp, this immediately implies the exponential formula H(x) = exp(H^{c}(x)). This result also generalizes to weighted and multi-sort species. See [34] for results closely related to those of the present paper, formulated in the language of species.

6The coefficients c_{k} may in turn be generating functions for some additional structure on the set [k] — for instance, a graph, a digraph, a hypergraph, etc. — under the condition that this structure is “connected”.

â_{n}(q_{1} + q_{2}) = ∑_{k=1}^{n} \binom{n − 1}{k − 1} â_{k}(q_{1}) a_{n−k}(q_{2}) for n ≥ 1 .  (1.11)

Sequences of polynomials {a_{n}(q)} satisfying (1.2) [or equivalently satisfying (1.5) and not identically zero] have been termed sequences of binomial type by Rota and collaborators [12, 16, 39, 48, 49, 51] and studied by means of the umbral calculus [18, 49, 52].^{8} The corresponding sequences {a_{n}(q)/n!} have been termed sequences of binomial type by Labelle [32] and convolution families by Knuth [30] and Zeng [70]; these authors used elementary formal-power-series methods closely resembling those used here. A purely combinatorial approach to sequences of binomial type, employing the theory of species, has been developed by Labelle [33] (see also [5, Section 3.1]).

Further identities, generalizing (1.5)/(1.6), can be obtained by a powerful transformation suggested by Knuth [30]. Start with any formal power series A(x) with constant term 1; set A_{q}(x) = A(x)^{q} and define polynomials {a_{n}(q)} by (1.2). Now let t be a parameter, and define a formal power series A(x; t) by the implicit equation

A(x; t) = A(xA(x; t)^{t}) .  (1.12)

Since A(x; 0) = A(x), we can view the family {A(x; t)}_{t∈ℝ} as a special class of “perturbations” of A(x). Now define polynomials {a_{n}(q; t)} by the obvious formula

A(x; t)^{q} = ∑_{n=0}^{∞} a_{n}(q; t) \frac{x^{n}}{n!} .  (1.13)

For each t, these polynomials form a family of the type (1.2) and thus satisfy the identities (1.5)/(1.6). On the other hand, a straightforward calculation using the Lagrange inversion formula [60] yields the remarkable relation^{9}

a_{n}(q; t) = \frac{q}{q + nt} a_{n}(q + nt) = q â_{n}(q + nt) ,  (1.14)

or even more simply

â_{n}(q; t) = â_{n}(q + nt) .  (1.15)

[In particular, a_{n}(q; t) and â_{n}(q; t) are polynomials jointly in q and t, so we can treat t as an indeterminate if we wish.] It follows that, for any family {a_{n}(q)} of type (1.2), we have the following identities generalizing (1.5)/(1.6):^{10}

7See also [45, Theorem 2.9]; and see [5, p. 188, Exercise 3.1.20(a)] for the special case q_{1} = 1.

8It is not hard to see by induction that if {a_{n}(q)} satisfies (1.5) [or even the special case of (1.5) with q_{1} = q_{2}] and is not identically zero, then deg a_{n} ≤ n with a_{0} = 1 and a_{n}(0) = 0 for n ≥ 1; moreover, with a little extra work it can be shown that A_{q}(x) is necessarily of the form (1.2):

see [16, Theorem 4.1] [30, 70] [60, Exercise 5.37, pp. 87–88 and 131–132].

Let us also remark that Rota et al. [39,51] and many subsequent authors [12,16,48,49], in defining “sequence of binomial type”, impose the additional condition that deg a_{n} = n exactly (i.e., c_{1} ≠ 0); but since this condition is irrelevant for our purposes, we prefer not to impose it.

9See [60, Exercises 5.37(e) and 5.58, pp. 87–88, 99, 131–133 and 148], where the argument is attributed to Eric Rains and Ira Gessel. Please note also that if we write f(x) = x/A(x)^{t} and g(x) = xA(x; t)^{t}, then f and g are compositional inverses (as observed in [30, 32] for t = 1).

∑_{k=0}^{n} \binom{n}{k} q_{1}â_{k}(q_{1} + kt) q_{2}â_{n−k}(q_{2} + (n − k)t) = (q_{1} + q_{2})â_{n}(q_{1} + q_{2} + nt) (1.16)

∑_{k=1}^{n} \binom{n}{k} k â_{k}(q_{1} + kt) q_{2}â_{n−k}(q_{2} + (n − k)t) = n â_{n}(q_{1} + q_{2} + nt) for n ≥ 1

(1.17)

where we understand that qâ_{0}(q) = 1. Multiplying (1.17) by t and summing it with (1.16), we obtain the alternate form

∑_{k=0}^{n} \binom{n}{k} a_{k}(q_{1} + kt) q_{2}â_{n−k}(q_{2} + (n − k)t) = a_{n}(q_{1} + q_{2} + nt) .  (1.18)

If in (1.18) we interchange k ↔ n − k and q_{1} ↔ q_{2} and then replace q_{2} by q_{2} − nt, we obtain the slightly simpler form

∑_{k=0}^{n} \binom{n}{k} q_{1}â_{k}(q_{1} + kt) a_{n−k}(q_{2} − kt) = a_{n}(q_{1} + q_{2}) .  (1.19)

A combinatorial proof and interpretation of (1.16)/(1.18) in terms of the theory of species has been given by Labelle [33].^{11} We call (1.16)–(1.19) Abel-type extensions of (1.5)/(1.6) because in the simplest case A(x) = e^{x}, a_{n}(q) = q^{n} they reduce to Abel’s celebrated extensions of the binomial theorem (also discovered simultaneously by Cauchy) [28,46,61].

These Abel-type formulae can alternatively be derived as immediate consequences of the Pfaff–Cauchy derivative identities (generalizations of Leibniz’s rule for the nth derivative of the product of two functions) recently presented by Johnson [28]. Indeed, setting v = A(x)^{q_{1}}, w = A(x)^{q_{2}}, ϕ = A(x)^{t} in [28, eq. (1.1)] yields (1.19), while making the same substitution in [28, eq. (1.4)] yields (1.16).

Some classical examples of families {a_{n}(q)} and the corresponding identities (1.5)/ (1.6) and (1.16)–(1.19) are listed in Table 1.

In this note we begin by proving some easy generalizations of the foregoing formulae to the case in which the integer index n is replaced by a multi-index n over a finite ground set V. We then show some applications of the latter formulae to the multivariate Tutte polynomial [57] of a graph G = (V, E). Finally, we derive some further identities for the multivariate Tutte polynomial, which generalize an identity for counting connected graphs found by Riordan, Nijenhuis, Wilf and Kreweras [31,40,47] and in more general form by Leroux [37] and Gessel [17] and an identity for the inversion enumerator of trees found by Mallows, Riordan and Kreweras [31, 38]. In the appendix we prove an apparently new generalization of Möbius inversion on the partition lattice.

10Already Rota et al. [51, p. 711, Proposition 4] and Reiner [45, Theorem 2.10] noticed that, for any t, the family {a_{n}(q; t)} defined by (1.14) is of type (1.2). But they do not seem to have noticed the relation (1.12), which to our knowledge goes back to Knuth [30].

11See also [5, p. 189, Exercise 3.1.22] for a brief summary.

A(x)  a_{n}(q)  (1.5)/(1.6)  (1.16)–(1.19)

e^{x} q^{n}

binomial theorem

Abel–Cauchy binomial identities

\begin{matrix}1 + x \\ (1 − x)^{−1} \\ (1 + αx)^{β} \end{matrix}

\begin{matrix}q\underline{n} \\ q\overline{n} \\ α^{n}(βq)\underline{n} \end{matrix} \}

Chu–Vandermonde convolution Rothe’s generalized Chu–Vandermonde convolution

exp(e^{x} − 1) B_{n}(q) = ∑_{k=0}^{n} \left\{{n \atop k}\right\} q^{k}

(Bell polynomial [11])

exp[−x/(1 − x)] L_{n}^{(−1)}(q) = ∑_{k=0}^{n} \frac{n!}{k!} \binom{n−1}{n−k} (−q)^{k}

(Laguerre polynomial [1])

Table 1. Some classical identities that are special cases of (1.5)/(1.6) and (1.16)–(1.19). See [21–24,28,46,61] for more information concerning Abel–Cauchy and Chu–Vandermonde–Rothe identities. The identity (1.5) is well known for the Bell [11, p. 136, eq. 3n] and Laguerre [2, p. 192, eq. 41] [36, p. 96, Problem 20] polynomials. We do not know any references for (1.6) or (1.16)–(1.19) in these cases.

We stress that many (though not all) of the formulae derived in this paper are already known. But we think that our approach provides a unified perspective that may be of interest.

2. Variants of the exponential formula

Let V be a finite ground set; we shall use multi-indices n = (n_{i})_{i∈V} ∈ ℕ^{V} and commuting indeterminates x = (x_{i})_{i∈V}. We write |n| = ∑_{i∈V} n_{i} and x^{n} = ∏_{i∈V} x_{i}^{n_{i}}. We use the notation n! = ∏_{i∈V} n_{i}! and analogously for binomial and multinomial coefficients. Finally, we denote by 0 (respectively 1) the multi-index with all entries 0 (respectively 1); and for any subset W ⊆ V, we denote by 1_{W} the multi-index taking the value 1 on W and 0 on V \ W.

Let R be a commutative ring containing the rationals as a subring; we shall use polynomials and formal power series whose coefficients lie in R. (In applications, R will usually be either the rationals, reals or complex numbers, or a ring of polynomials or formal power series over one of these fields.) One possible approach is to treat the coefficients c = (c_{n})_{n∈ℕ^{V} \{0}} as indeterminates, and to take R to be the polynomial ring ℚ[c]; this approach has the advantage of exhibiting the polynomial dependence on the coefficients c_{n}. But we need not commit ourselves to any specific choice of the ring R; all of our identities will be valid in complete generality.

So let {c_{n}}_{n∈ℕ^{V}} be a sequence of coefficients in the ring R, with c_{0} = 0; and let

C(x) = ∑_{n} c_{n} \frac{x^{n}}{n!}  (2.1)

be the corresponding exponential generating function, considered as a formal power series in the indeterminates x. Now let q be another (commuting) indeterminate, and define

A_{q}(x) = exp[qC(x)] = ∑_{n} a_{n}(q) \frac{x^{n}}{n!} .  (2.2)

Using the Taylor series for exp, we deduce immediately that

(a) Each coefficient a_{n}(q) is a polynomial in q, of degree at most |n|; indeed we have the explicit formula^{12}

a_{n}(q) = ∑_{ℓ=0}^{|n|} \frac{q^{ℓ}}{ℓ!} ∑_{\begin{matrix}n_{1},...,n_{ℓ}≠0 \\ ∑ n_{j}=n \end{matrix}} \binom{n}{n_{1}, …, n_{ℓ}} ∏_{j=1}^{ℓ} c_{n_{j}} .  (2.3)

(b) a_{0}(q) = 1.

(c) For n ≠ 0, the polynomial a_{n}(q) has zero constant term, so that we can write a_{n}(q) = qâ_{n}(q) where â_{n}(q) is a polynomial of degree at most |n|−1; moreover we have â_{n}(0) = c_{n}.

Conversely, it is not hard to see that if (c_{n})_{n∈ℕ^{V} \{0}} is any sequence and we define (a_{n}(q))_{n∈ℕ^{V}} by (2.3), then the latter family satisfies (2.2).

Using qC(x) = log A_{q}(x) together with the Taylor series for log(1 + z), we obtain the inverse formula

qc_{n} = ∑_{ℓ=1}^{|n|} \frac{(−1)^{ℓ−1}}{ℓ} ∑_{\begin{matrix}n_{1},...,n_{ℓ}≠0 \\ ∑ n_{j}=n \end{matrix}} \binom{n}{n_{1}, …, n_{ℓ}} ∏_{j=1}^{ℓ} a_{n_{j}}(q)  (2.4)

or equivalently

c_{n} = ∑_{ℓ=1}^{|n|} \frac{(−q)^{ℓ−1}}{ℓ} ∑_{\begin{matrix}n_{1},...,n_{ℓ}≠0 \\ ∑ n_{j}=n \end{matrix}} \binom{n}{n_{1}, …, n_{ℓ}} ∏_{j=1}^{ℓ} â_{n_{j}}(q) .  (2.5)

It is a nontrivial fact that the right-hand side of (2.5) is independent of q.

Now let r be another indeterminate, and let us use the identity A_{rq}(x) = A_{q}(x)^{r} together with the Taylor series

(1 + z)^{r} ≡ exp[r log(1 + z)] = ∑_{ℓ=0}^{∞} \frac{r\underline{ℓ}}{ℓ!} z^{ℓ}  (2.6)

12This formula holds also for n = 0 because the multi-index 0 has exactly one ordered partition (n_{1}, …, n_{ℓ}) into zero or more nonvanishing parts: namely, we have ℓ = 0 parts, and the multinomial coefficient and the empty product both equal 1, correctly giving a_{0}(q) = 1. This same observation applies to all subsequent formulae of a similar type, such as (2.7) ff.

where r\underline{ℓ} = r(r − 1) ⋯ (r − ℓ + 1) denotes the falling factorial. (If we like, we can alternatively use the notation \binom{r}{ℓ} = r\underline{ℓ}/ℓ!, which is a well-defined polynomial in the indeterminate r.) We obtain

a_{n}(rq) = ∑_{ℓ=0}^{|n|} \frac{r\underline{ℓ}}{ℓ!} ∑_{\begin{matrix}n_{1},...,n_{ℓ}≠0 \\ ∑ n_{j}=n \end{matrix}} \binom{n}{n_{1}, …, n_{ℓ}} ∏_{j=1}^{ℓ} a_{n_{j}}(q) .  (2.7)

In view of the identity (−r)\underline{ℓ} = (−1)^{ℓ}r\overline{ℓ} where r\overline{ℓ} = r(r +1) ⋯ (r +ℓ−1) = (r +ℓ−1)\underline{ℓ} denotes the rising factorial, we also have

a_{n}(−rq) = ∑_{ℓ=0}^{|n|} \frac{(−1)^{ℓ}r\overline{ℓ}}{ℓ!} ∑_{\begin{matrix}n_{1},...,n_{ℓ}≠0 \\ ∑ n_{j}=n \end{matrix}} \binom{n}{n_{1}, …, n_{ℓ}} ∏_{j=1}^{ℓ} a_{n_{j}}(q) .  (2.8)

Since both sides of the identities (2.7)/(2.8) are polynomials in r, we can specialize these identities to r integer or rational, or more generally to r being any element of the ring R. If r is a positive integer, the sum in (2.7) can obviously be restricted to ℓ ≤ r. Slightly (but not much) less trivially, if r is a positive integer, then by using

\frac{r\overline{ℓ}}{ℓ!} = \frac{(r + ℓ − 1)!}{ℓ! (r − 1)!} = \frac{(ℓ + 1)\overline{r−1}}{(r − 1)!}  (2.9)

we can rewrite (2.8) as

a_{n}(−rq) = ∑_{ℓ=0}^{|n|}(−1)^{ℓ} \frac{(ℓ + 1)\overline{r−1}}{(r − 1)!} ∑_{\begin{matrix}n_{1},...,n_{ℓ}≠0 \\ ∑ n_{j}=n \end{matrix}} \binom{n}{n_{1}, …, n_{ℓ}} ∏_{j=1}^{ℓ} a_{n_{j}}(q) ,  (2.10)

in which the coefficient (ℓ + 1)\overline{r−1}/(r − 1)! is a polynomial of degree r − 1 in ℓ. In particular, for r = 1 we have

a_{n}(−q) = ∑_{ℓ=0}^{|n|}(−1)^{ℓ} ∑_{\begin{matrix}n_{1},...,n_{ℓ}≠0 \\ ∑ n_{j}=n \end{matrix}} \binom{n}{n_{1}, …, n_{ℓ}} ∏_{j=1}^{ℓ} a_{n_{j}}(q) .  (2.11)

By formally setting r = q_{2}/q_{1} (this is justifiable if we work in a ring of formal Laurent series in the indeterminate q_{1}), we obtain the identity

a_{n}(q_{2}) = ∑_{ℓ=0}^{|n|} \frac{1}{ℓ!} ( ∏_{j=0}^{ℓ−1}(q_{2} − jq_{1}) ) ∑_{\begin{matrix}n_{1},...,n_{ℓ}≠0 \\ ∑ n_{j}=n \end{matrix}} \binom{n}{n_{1}, …, n_{ℓ}} ∏_{j=1}^{ℓ} â_{n_{j}}(q_{1}) ,  (2.12)

which is nice because both sides are manifestly polynomials in the indeterminates q_{1} and q_{2}. Alternatively, for n ≠ 0 we can pull out the j = 0 factor and write

â_{n}(q_{2}) = ∑_{ℓ=1}^{|n|} \frac{1}{ℓ!} ( ∏_{j=1}^{ℓ−1}(q_{2} − jq_{1}) ) ∑_{\begin{matrix}n_{1},...,n_{ℓ}≠0 \\ ∑ n_{j}=n \end{matrix}} \binom{n}{n_{1}, …, n_{ℓ}} ∏_{j=1}^{ℓ} â_{n_{j}}(q_{1}) .  (2.13)

Conversely, it is not hard to see that if q_{1} is any element of the ring R and (â_{n}(q_{1}))_{n∈ℕ^{V}} is any sequence, and we define (a_{n}(q))_{n∈ℕ^{V}} by (2.12), then the latter family satisfies (2.2).

The following special cases of (2.12)/(2.13) are of particular interest:

(a) For q_{1} = 0, the identity (2.12) reduces to (2.3).

(b) For q_{2} = 0, we obtain the inverse formula (2.4)/(2.5).

(c) For q_{2} = −q_{1}, we obtain the closely related formula (2.11).

It is easy to show that the coefficients {a_{n}(q)}_{n∈ℕ^{V}} satisfy the identities

∑_{k} \binom{n}{k} a_{k}(q_{1}) a_{n−k}(q_{2}) = a_{n}(q_{1} + q_{2})  (2.14)

∑_{k≠0} \binom{n}{k} k_{i} â_{k}(q_{1}) a_{n−k}(q_{2}) = n_{i} â_{n}(q_{1} + q_{2}) for n ≠ 0  (2.15)

Indeed, (2.14) follows by expanding out the identity A_{q_{1}}(x)A_{q_{2}}(x) = A_{q_{1}+q_{2}}(x) and extracting the coefficient of x^{n}, while (2.15) follows analogously from

A_{q_{2}}(x) [x_{i} \frac{∂}{∂x_{i}} \frac{A_{q_{1}}(x) − 1}{q_{1}}] = x_{i} \frac{∂}{∂x_{i}} \frac{A_{q_{1}+q_{2}}(x) − 1}{q_{1} + q_{2}} ,  (2.16)

which is an easy consequence of (2.2). In particular, specializing (2.15) to q_{1} = 0, we obtain the recursion relation

a_{n}(q) = q ∑_{k≥δ_{i}} \binom{n − δ_{i}}{k − δ_{i}} c_{k} a_{n−k}(q) whenever n_{i} ≥ 1 ,  (2.17)

which allows the {a_{n}(q)} to be calculated given the {c_{n}}, or vice versa. [Here δ_{i} is the vector with entry 1 at element i and 0 elsewhere.] More generally, we can form the linear combination n_{i} × (2.14) − (q_{1} + q_{2}) × (2.15) to obtain the recursion relation

a_{n}(q_{2}) = ∑_{k≠0} [\binom{n − δ_{i}}{k − δ_{i}}(q_{1} + q_{2}) − \binom{n}{k}q_{1}] â_{k}(q_{1}) a_{n−k}(q_{2}) whenever n_{i} ≥ 1 ,

(2.18)

which allows the {a_{n}(q_{2})} to be calculated given the {â_{n}(q_{1})} for any fixed q_{1}, and which reduces to (2.17) when q_{1} = 0.

We do not know whether there exist useful analogues of (2.14)/(2.15) with higher powers of k on the left-hand side.

Finally, we can deduce the Abel-type extensions of (2.14)/(2.15):

∑_{k} \binom{n}{k} q_{1}â_{k}(q_{1} + k · t) q_{2}â_{n−k}(q_{2} + (n − k) · t) = (q_{1} + q_{2})â_{n}(q_{1} + q_{2} + n · t)

(2.19)

∑_{k≠0} \binom{n}{k} k_{i} â_{k}(q_{1} + k · t) q_{2}â_{n−k}(q_{2} + (n − k) · t) = n_{i} â_{n}(q_{1} + q_{2} + n · t)

for n ≠ 0 (2.20)

where t = (t_{i})_{i∈V} are commuting indeterminates and we understand qâ_{0}(q) = 1. These formulae can be proved by repeated use of the Lagrange inversion formula, once in each variable. For details we refer to the paper of Zeng [70, pp. 225–226]. For further information on classical specializations of (2.19)/(2.20), see [42,43,58,61,70].

Remark. We wonder whether (2.19)/(2.20) might have an extension to identities involving a not-necessarily-diagonal matrix T = (t_{ij})_{i,j∈V} of indeterminates, based on considering the implicit equation

e^{C(x;T)} = A(e^{C(x;T)T} x) ,  (2.21)

which generalizes (1.12). If true, this could be a powerful extension. See Strehl [61] for possibly related work in which a matrix of indeterminates is employed.

3. Application to the multivariate Tutte polynomial

In this section we apply the formulae of Section 2 to deduce some identities for multivariate Tutte polynomials.

3.1. Definitions and basic properties. Let G = (V, E) be a finite undirected graph with vertex set V ≠ ∅ and edge set E; loops and multiple edges are allowed unless explicitly stated otherwise. Then the multivariate Tutte polynomial [57] of G is, by definition, the polynomial

Z_{G}(q, v) = ∑_{A⊆E} q^{k(A)} ∏_{e∈A} v_{e} ,  (3.1)

where q and v = (v_{e})_{e∈E} are commuting indeterminates, and k(A) denotes the number of connected components in the subgraph (V, A). It is also convenient to pull out one factor of q by defining

Ẑ_{G}(q, v) = ∑_{A⊆E} q^{k(A)−1} ∏_{e∈A} v_{e} ;  (3.2)

this is still a polynomial since k(A) ≥ 1 for all A. Finally, let us make the convention that if G = ∅ (the graph with empty vertex set and empty edge set), then Z_{∅} = 1 and Ẑ_{∅} is undefined.

If we specialize to v_{e} = v for all edges e, we obtain a two-variable polynomial Z_{G}(q, v) that is essentially equivalent to the classical Tutte polynomial [57, Section 2.5].

Note that at q = 1 we have the trivial formula

Z_{G}(1, v) = Ẑ_{G}(1, v) = ∏_{e∈E}(1 + v_{e}) .  (3.3)

More interestingly, at q = 0 we have the specialization

Ẑ_{G}(0, v) = C_{G}(v) ≡ ∑_{\begin{matrix}A ⊆ E \\ k(A) = 1 \end{matrix}} ∏_{e∈A} v_{e} ,  (3.4)

i.e., the generating polynomial of connected spanning subgraphs of G.

In statistical physics, Z_{G}(q, v) is known as the partition function of the q-state Potts model [44, 68, 69] in the Fortuin–Kasteleyn representation [15, 26, 29]. This arises by virtue of the following identity [15,29]:

Theorem 3.1 (Fortuin–Kasteleyn representation of the Potts model [15, 29]). For integer q ≥ 1, we have

Z_{G}(q, v) = ∑_{σ: V →[q]} ∏_{e=ij∈E} [1 + v_{e}δ(σ(i), σ(j))]  (3.5)

where δ denotes the Kronecker delta.

Proof. On the right-hand side of (3.5), expand out the product over e ∈ E, and let A ⊆ E be the set of edges for which the term v_{e}δ(σ(i), σ(j)) is taken. Now perform the sum over maps σ: V → [q]: in each connected component of the subgraph (V, A) the “color” σ(i) must be constant, and there are no other constraints. Therefore, the right-hand side equals

∑_{A⊆E} q^{k(A)} ∏_{e∈A} v_{e} ,  (3.6)

as was to be proved. □

Specializing to v_{e} = −1 for all edges e, we obtain the Birkhoff–Whitney [4, 66] expansion for the chromatic polynomial of G:

Corollary 3.2. For integer q ≥ 1, the number of proper q-colorings of G is P_{G}(q) ≡ Z_{G}(q, −1).

3.2. Some generating functions. For the remainder of this section, let us assume that G is a loopless graph. For notational simplicity it is convenient to assume also that G has no multiple edges; the trivial changes to allow multiple edges can be left to the reader.

For any multi-index n ∈ ℕ^{V}, let us define G[n] to be the graph obtained from G by expanding each vertex i to an independent set consisting of n_{i} vertices. That is, the vertices of G[n] are pairs (i, α) with i ∈ V and α ∈ [n_{i}], and the edges of G[n] are all pairs ⟨(i, α), (j, β)⟩ with ij ∈ E, α ∈ [n_{i}] and β ∈ [n_{j}]. Given a set of weights v = (v_{e})_{e∈E} associated to the edges of G, we assign the weight v_{ij} to each edge ⟨(i, α), (j, β)⟩ in G[n].

In a similar way, let us define G′[n] to be the graph obtained from G by expanding each vertex i to a clique consisting of n_{i} vertices. That is, the vertex set of G′[n] is the same as that of G[n], and the edges of G′[n] consist of those of G[n] together with all pairs ⟨(i, α), (i, β)⟩ with i ∈ V, α, β ∈ [n_{i}] and α ≠ β. Given a set of weights v = (v_{e})_{e∈E} associated to the edges of G and another set of weights w = (w_{i})_{i∈V} associated to the vertices of G, we assign the weight v_{ij} to each edge ⟨(i, α), (j, β)⟩ (i ≠ j) in G′[n] and the weight w_{i} to each edge ⟨(i, α), (i, β)⟩ in G′[n].

Note in particular that if n = 1_{W} for some subset W ⊆ V, then G[n] = G′[n] = G[W], the induced subgraph of G on W.

The following “master formula” generates the multivariate Tutte polynomials (with weights as assigned above) of all the graphs G[n] and G′[n]:

Theorem 3.3. Let G = (V, E) be a simple graph, and let v = (v_{e})_{e∈E} and w = (w_{i})_{i∈V} be indeterminates. We then have the following exponential generating functions:

∑_{n} Z_{G[n]}(q, v) \frac{x^{n}}{n!} = (∑_{n} ( ∏_{ij∈E}(1 + v_{ij})^{n_{i}n_{j}}) \frac{x^{n}}{n!} )_{q}  (3.7)

∑_{n} Z_{G′[n]}(q, v, w) \frac{x^{n}}{n!} = (∑_{n} ( ∏_{ij∈E}(1 + v_{ij})^{n_{i}n_{j}}) (∏_{i∈V}(1 + w_{i})^{n_{i}(n_{i}−1)/2}) \frac{x^{n}}{n!} )_{q}

(3.8)

where all sums run over n ∈ ℕ^{V}.

We remark that the expression in large parentheses on the right-hand side of (3.7) [respectively (3.8)] is the grand partition function for a lattice gas on the graph G [respectively on the graph G^{∘} obtained from G by adjoining a loop at each vertex] in which arbitrary nonnegative integer occupation numbers n = (n_{i})_{i∈V} are allowed, with fugacities x on the vertices and two-particle Boltzmann weights 1 + v_{ij} on edges ij [and two-particle Boltzmann weights 1 + w_{i} on the loops]. See e.g. [53, 54] for definitions concerning lattice gases.

When G = K_{1} (the graph with one vertex and no edges), (3.8) reduces to the wellknown [6, 17, 19, 63, 65] exponential generating function for the Tutte polynomials of the complete graphs K_{n}:^{13}

∑_{n=0}^{∞} Z_{n}(q, v) \frac{x^{n}}{n!} = (∑_{n=0}^{∞}(1 + v)^{n(n−1)/2} \frac{x^{n}}{n!} )^{q} .  (3.9)

When G = K_{2}, (3.7) reduces to the exponential generating function for the Tutte polynomials of the complete bipartite graphs K_{n_{1},n_{2}},

∑_{n_{1},n_{2}=0}^{∞} Z_{n_{1},n_{2}}(q, v) \frac{x^{n_{1}}}{n_{1}!} \frac{y^{n_{2}}}{n_{2}!} = ( ∑_{n_{1},n_{2}=0}^{∞}(1 + v)^{n_{1}n_{2}} \frac{x^{n_{1}}}{n_{1}!} \frac{y^{n_{2}}}{n_{2}!} )^{q} ,  (3.10)

which in turn specializes for v = −1 to the well-known [60, Exercise 5.6, pp. 73 and 107–108] exponential generating function for the chromatic polynomials of the complete bipartite graphs^{14},

∑_{n_{1},n_{2}=0}^{∞} P_{K_{n_{1},n_{2}}}(q) \frac{x^{n_{1}}}{n_{1}!} \frac{y^{n_{2}}}{n_{2}!} = (e^{x} + e^{y} − 1)^{q} .  (3.11)

More generally, when G = K_{r}, (3.7) gives the exponential generating function for the Tutte polynomials of the complete r-partite graphs K_{n_{1},...,n_{r}}.

Note also that if we only want to know Z_{G[n]}(q, v) for n ≤ 1 — that is, we want to know Z_{G[W]}(q, v) for subsets W ⊆ V — then it suffices to get correct the terms n ≤ 1 on the right-hand side of (3.7); all the other terms can be dropped or altered arbitrarily. It follows that

13Unfortunately, this formula is usually written in terms of the classical Tutte polynomial T_{G}(x, y), which is related to Z_{G}(q, v) by a change of variables [57, Section 2.5] that obscures the very different roles played by q and v.

14(3.11) can alternatively be derived from the explicit expression [62] for P_{K_{n_{1},n_{2}}} (q) by using a well-known Stirling-number identity [25, eq. (7.49)] together with the binomial formula.

Z_{G[W]}(q, v) = [x^{1_{W}}] (∑_{n≤1} ( ∏_{ij∈E}(1 + v_{ij})^{n_{i}n_{j}}) \frac{x^{n}}{n!} )^{q} .  (3.12)

Note that the expression in large parentheses is now the grand partition function for a lattice gas with hard-core self-repulsion, i.e., at most one atom can occupy each site. In the special case v = −1, this becomes

P_{G[W]}(q) = [x^{1_{W}}] I_{G}(x)^{q} ,  (3.13)

where I_{G}(x) is the multivariate generating polynomial for independent sets of vertices in G. The formula (3.13) was found previously by Lass [35, Proposition 3.1].

Since the formula (3.7) for G[n] is just a specialization of the formula (3.8) for G′[n], obtained by taking w = 0, it suffices to prove the latter.

First Proof of Theorem 3.3. Since the coefficient of x^{n} on each side of (3.8) is a polynomial in q, it suffices to prove the identity for infinitely many values of q in the ring R; in particular, it suffices to prove it for all positive integers q. By Theorem 3.1, for integer q ≥ 1 we have

Z_{G′[n]}(q, v, w) = ∑_{σ: V (G′[n])→[q]} ∏_{rs∈E(G′[n])} [1 + v_{rs}δ(σ(r), σ(s))]  (3.14a)

= ∑_{σ: V (G′[n])→[q]} ( ∏_{ij∈E} ∏_{\begin{matrix}α ∈ [n_{i}] \\ β ∈ [n_{j}] \end{matrix}} [1 + v_{ij}δ(σ(i, α), σ(j, β))])

× ( ∏_{i∈V} ∏_{\begin{matrix}α, β ∈ [n_{i}] \\ α < β \end{matrix}} [1 + w_{i}δ(σ(i, α), σ(i, β))]) (3.14b)

Now, because of the symmetries in the construction of G′[n], the summand in (3.14b) depends only on the numbers {n_{i,τ}}_{i∈V, τ∈[q]} defined by

n_{i,τ} = #{α ∈ [n_{i}]: σ(i, α) = τ} ,  (3.15)

and we have

Z_{G′[n]}(q, v, w) = ∑_{\begin{matrix}\{n_{i,τ} \} \\ ∑_{τ=1}^{q} n_{i,τ} = n_{i} ∀i \end{matrix}} (∏_{i∈V} \binom{n_{i}}{n_{i,1}, …, n_{i,q}}) ( ∏_{ij∈E} ∏_{τ=1}^{q}(1 + v_{ij})^{n_{i,τ} n_{j,τ}} )

× (∏_{i∈V} ∏_{τ=1}^{q}(1 + w_{i})^{n_{i,τ} (n_{i,τ} −1)/2}) .  (3.16)

Now multiply by x^{n}/n! and sum over n; the sums over the n_{i,τ} now become unrestricted, and the sums for the different values of τ decouple; we end up with the product of q terms each of which is

∑_{n} ( ∏_{ij∈E}(1 + v_{ij})^{n_{i}n_{j}}) (∏_{i∈V}(1 + w_{i})^{n_{i}(n_{i}−1)/2}) \frac{x^{n}}{n!} .  (3.17)
□

It is instructive to give an alternate proof of Theorem 3.3 in which q is treated directly as an indeterminate:

Second Proof of Theorem 3.3. We begin by proving the special case (3.9). From the binomial formula we have

(1 + ∑_{n=1}^{∞}(1 + v)^{n(n−1)/2} \frac{x^{n}}{n!} )_{q} = 1 + ∑_{b=1}^{∞} \frac{q\underline{b}}{b!} (∑_{n=1}^{∞}(1 + v)^{n(n−1)/2} \frac{x^{n}}{n!} )^{b} (3.18a)

= 1 + ∑_{b=1}^{∞} \frac{q\underline{b}}{b!} ∑_{n_{1},...,n_{b}≥1} \frac{x^{∑ n_{j}}}{∏ n_{j}!} ∏_{j=1}^{b}(1 + v)^{n_{j}(n_{j}−1)/2} .

(3.18b)

Now write n = ∑_{j=1}^{b} n_{j}, and consider n_{1}, …, n_{b} as the block sizes in an ordered partition π = (π_{1}, …, π_{b}) of [n] into b nonempty blocks. The number of ordered

partitions with those block sizes is precisely the multinomial coefficient n!/ ∏_{j=1}^{b} n_{j}!, so

(3.18) is equal to

1 + ∑_{n=1}^{∞} \frac{x^{n}}{n!} ∑_{π∈Π′_{n}} \frac{q\underline{|π|}}{|π|!} ∏_{j=1}^{|π|}(1 + v)^{|π_{j}|(|π_{j}|−1)/2} ,  (3.19)

where Π′_{n} denotes the set of ordered partitions of [n], and |π| denotes the number of blocks in the partition π. Passing to unordered partitions absorbs the factor 1/|π|! (as these are partitions of a labelled set), and we get

1 + ∑_{n=1}^{∞} \frac{x^{n}}{n!} ∑_{π∈Π_{n}} q\underline{|π|} ∏_{j=1}^{|π|}(1 + v)^{|π_{j}|(|π_{j}|−1)/2} .  (3.20)

The factor (1 + v)^{|π_{j}|(|π_{j}|−1)/2} corresponds to a sum over (simple undirected) graphs on the vertex set π_{j}, with a weight v for each edge. We can now reinterpret (3.20) as a sum over (simple undirected) graphs H on the vertex set [n], with a weight v^{|E(H)|}, together with a sum over partitions π ∈ Π_{n} that are compatible with H in the sense that each block of π is a union of (vertex sets of) connected components of H. If H has r connected components, then these can be grouped into b nonempty blocks in \left\{{r \atop b}\right\} ways (where \left\{{r \atop b}\right\} is a Stirling number of the second kind); and it is well known [25, eq. (6.10)] that

∑_{b=1}^{r} \left\{{r \atop b}\right\} q\underline{b} = q^{r} .  (3.21)

Therefore, each graph H gets a weight q^{k(H)}v^{|E(H)|}, and the sum over graphs gives Z_{n}(q, v). This proves (3.9).

The more general formulae (3.7)/(3.8) are derived by a variant of this proof in which sums over integers n ∈ ℕ \ {0} are replaced by sums over multi-indices n ∈ ℕ^{V} \ {0}. In the one-dimensional case, we were considering partitions of [n], a collection of n distinct objects of a single type. We are now working with multi-indices in ℕ^{V}, and so we will be partitioning collections of objects of |V | different types. We begin with some notation. Given n = (n_{i})_{i∈V} ∈ ℕ^{V}, we write [n] for the set of ordered pairs {(i, α): i ∈ V and α ∈ [n_{i}]}. Thus |[n]| = ∑_{i∈V} n_{i}. We shall think of the subset [n]_{i} := {(i, α): α ∈ [n_{i}]} as a copy of [n_{i}] with type i; thus, [n] is a collection of |n| objects, with n_{i} objects of type i for each i ∈ V. Note that G′[n] is simply the complete graph on the vertex set [n]. Now, given a partition π = (π_{1}, …, π_{k}) of [n] (with all π_{j} nonempty), we write |π| = k. The block sizes B(π_{j}) are elements of ℕ^{V} \ {0} defined by

B(π_{j}) = (π_{j} ∩ [n]_{i})_{i∈V} .  (3.22)

Thus B(π_{j}) lists the number of objects of each type contained in the jth block of π. Now let us define the weight

W (n) := ( ∏_{ii′∈E}(1 + v_{ii′})^{n_{i}n_{i′}}) (∏_{i∈V}(1 + w_{i})^{n_{i}(n_{i}−1)/2}) .  (3.23)

The right-hand side of (3.8) is then

(1 + ∑_{n≠0} W (n)\frac{x^{n}}{n!} )^{q} = 1 + ∑_{b≥1} \frac{q\underline{b}}{b!} (∑_{n≠0} W (n)\frac{x^{n}}{n!} )^{b}  (3.24a)

= 1 + ∑_{b≥1} \frac{q\underline{b}}{b!} ∑_{n_{1},...,n_{b}≠0} \frac{x^{∑ n_{j}}}{∏ n_{j}!} ∏_{j=1}^{b} W (n_{j}) . (3.24b)

Now let n = ∑_{j=1}^{b} n_{j}, and consider n_{1}, …, n_{b} as the block sizes in an ordered partition π of [n] into b nonempty blocks. The number of ordered partitions with those block

sizes is the (multidimensional) multinomial coefficient n!/ ∏_{j=1}^{b} n_{j}!, so (3.24) is equal to

1 + ∑_{n≠0} \frac{x^{n}}{n!} ∑_{π} \frac{q\underline{|π|}}{|π|!} ∏_{j=1}^{|π|} W (B(π_{j})) ,  (3.25)

where the second sum is over ordered partitions of [n]. Passing to unordered partitions, this becomes

1 + ∑_{n≠0} \frac{x^{n}}{n!} ∑_{π}q\underline{|π|} ∏_{j=1}^{|π|} W (B(π_{j})) .  (3.26)

The factor W (B(π_{j})) corresponds to a sum over graphs with vertex set π_{j}, such that edges within [n]_{i} have weight w_{i} and edges between [n]_{i} and [n]_{i′} have weight v_{ii′}. As before, we can reinterpret (3.26) as a sum over graphs H with vertex set [n], with these same edge weights. The final step of the argument — summing over partitions π that are compatible with H — is identical to that in the one-dimensional case: it makes no difference whether the vertex set is [n] or [n]. We therefore see that each graph H gets weight q^{k(H)} times the product of edge weights, and we are done. □

3.3. Consequences for Z_{G}(q, v). In view of Theorem 3.3, we can apply all the results of Section 2 with the identifications

a_{n}(q) = Z_{G′[n]}(q, v, w)  (3.27a)
â_{n}(q) = Ẑ_{G′[n]}(q, v, w)  (3.27b)
c_{n} = C_{G′[n]}(v, w)  (3.27c)

a_{n}(1) = ( ∏_{ij∈E}(1 + v_{ij})^{n_{i}n_{j}}) (∏_{i∈V}(1 + w_{i})^{n_{i}(n_{i}−1)/2})  (3.27d)

We refrain from writing out all the formulae, which are obtained by substituting (3.27a–d) into (2.3), (2.4)/(2.5), (2.7)–(2.13), (2.14), (2.15), (2.17), (2.18), (2.19) and (2.20). Let us simply show a few important results that arise from the partition formula (2.7)/(2.12) and from the convolution formula (2.14)–(2.15).

3.3.1. Partition formulae. By specializing (2.7)/(2.12) to n = 1, we can obtain a partition formula that expresses the multivariate Tutte polynomial of G at q = q_{2} in terms of the multivariate Tutte polynomials of induced subgraphs of G at q = q_{1}, for arbitrary choices of q_{1} and q_{2}:

Proposition 3.4. Let G = (V, E) be a finite loopless graph. Then

Z_{G}(q_{2}, v) = ∑_{π∈Π(V)}(q_{2}/q_{1})\underline{|π|} ∏_{B∈π} Z_{G[B]}(q_{1}, v) ,  (3.28)

where the sum runs over (unordered) partitions π of the vertex set V, the product runs over blocks B of π, and G[B] denotes the induced subgraph of G on the vertex set B.^{15} Equivalently we can write

Z_{G}(q_{2}, v) = ∑_{π∈Π(V)} ( ∏_{j=0}^{|π|−1}(q_{2} − jq_{1}) ) ∏_{B∈π} Ẑ_{G[B]}(q_{1}, v)  (3.29)

or

Ẑ_{G}(q_{2}, v) = ∑_{π∈Π(V)} ( ∏_{j=1}^{|π|−1}(q_{2} − jq_{1}) ) ∏_{B∈π} Ẑ_{G[B]}(q_{1}, v) .  (3.30)

Proof. Specializing (2.7) [or equivalently (2.12)] to n = 1, we obtain a sum over ordered partitions π = (π_{1}, …, π_{ℓ}) of V into ℓ nonempty blocks. Passing from ordered to unordered partitions, we get a factor ℓ! that cancels the 1/ℓ! in (2.7)/(2.12). □

Proposition 3.4 is very powerful because we are free to choose q_{1} as we please; then Z_{G}(q_{2}, v) can be written in terms of Z_{G[B]}(q_{1}, v). The two most important special cases are q_{1} = 0 and q_{1} = 1.^{16}

15Readers who dislike dividing by indeterminates can reinterpret this formula by writing r = q_{2}/q_{1} and hence q_{2} = rq_{1}, as in (2.7).

16The case q_{1} = −1 is also of interest, as it is related to acyclic orientations. See Lass [35] for some interesting material that may be relevant in the present context.

Case q_{1} = 0. Taking the limit q_{1} → 0 in (3.28), or equivalently just setting q_{1} = 0 in (3.29), we obtain

Z_{G}(q, v) = ∑_{π∈Π(V)} q^{|π|} ∏_{B∈π} C_{G[B]}(v) .  (3.31)

[This formula can alternatively be derived from (2.3) by the same reasoning as used in proving Proposition 3.4.] Of course, (3.31) also has an obvious direct combinatorial proof, based on the definition (3.1): first we classify subsets A ⊆ E according to the partition π of the vertex set V that is induced by the connected components of the subgraph (V, A); then we sum over ways of connecting up each component.

Case q_{1} = 1. This special case is slightly less obvious, and it is worth stating it explicitly:

Corollary 3.5. Let G = (V, E) be a finite loopless graph. Then

Z_{G}(q, v) = ∑_{π∈Π(V)} q\underline{|π|} ∏_{B∈π} ∏_{e∈E(G[B])}(1 + v_{e})  (3.32)

where the sum runs over (unordered) partitions π of the vertex set V, the outermost product runs over blocks B of π, and the innermost product runs over edges in the induced subgraph G[B]. In particular,

C_{G}(v) = ∑_{π∈Π(V)}(−1)^{|π|−1} (|π| − 1)! ∏_{B∈π} ∏_{e∈E(G[B])}(1 + v_{e})  (3.33)

Z_{G}(−1, v) = ∑_{π∈Π(V)}(−1)^{|π|} |π|! ∏_{B∈π} ∏_{e∈E(G[B])}(1 + v_{e})  (3.34)

where |π| denotes the number of blocks in π.

Specializing (3.32)–(3.34) to v_{e} = −1 for all edges e, we have:

Corollary 3.6. Let G = (V, E) be a finite loopless graph with |V | = n. Then:

P_{G}(q) = ∑_{k=1}^{n} q\underline{k} Q_{G}(k)  (3.35)

P′_{G}(0) = C_{G}(−1) = ∑_{k=1}^{n}(−1)^{k−1} (k − 1)! Q_{G}(k)  (3.36)

P_{G}(−1) = ∑_{k=1}^{n}(−1)^{k} k! Q_{G}(k)  (3.37)

where Q_{G}(k) denotes the number of partitions of V into k nonempty independent subsets.

Of course, (3.35) is well known and has a trivial direct proof by counting proper q-colorings; and (3.36)/(3.37) are immediate corollaries of (3.35).

Let us conclude by giving two direct combinatorial proofs of the fundamental Proposition 3.4: one using the subgraph representation (3.1), and the other using the coloring representation (3.5).

Second Proof of Proposition 3.4. Use the partition formula (3.31) [which itself had a simple direct combinatorial proof] to expand Z_{G}(q_{2}, v) on the left-hand side of (3.28) and to expand each Z_{G[B]}(q_{1}, v) on the right-hand side. We can then interpret the double sum on the right-hand side as a sum over partitions π of V, with weight q_{1} for each block, together with a sum over ways of grouping these blocks into nonempty groups, with a weight (q_{2}/q_{1})\underline{k} if we have k groups. Using the identity

∑_{k=1}^{n} \left\{{n \atop k}\right\} (q_{2}/q_{1})\underline{k} = (q_{2}/q_{1})^{n}  (3.38)

where n = |π|, we get exactly the expression on the left-hand side. □

It will not escape the reader’s notice that the argument using (3.38) is identical to the one given earlier using (3.21).

Third Proof of Proposition 3.4. Since both sides of (3.28) are polynomials in q_{1} and q_{2}, it suffices to prove the identity for all pairs of positive integers q_{1}, q_{2} such that r = q_{2}/q_{1} is also an integer. We shall do this using Theorem 3.1. Consider a (notnecessarily-proper) coloring σ: V → [q_{2}]. Fix a bijection [q_{2}] ≃ [q_{1}] × [r] and write σ = (τ, ψ) where τ: V → [q_{1}] and ψ: V → [r]. We then trivially have

Z_{G}(q_{2}, v) = ∑_{σ: V →[q_{2}]} ∏_{e=ij∈E} [1 + v_{e}δ(σ(i), σ(j))]  (3.39a)

= ∑_{ψ: V →[r]} ∑_{τ: V →[q_{1}]} ∏_{e=ij∈E} [1 + v_{e}δ(τ(i), τ(j))δ(ψ(i), ψ(j))] . (3.39b)

The map ψ induces a partition π_{ψ} of V into its nonempty color classes, and the remaining sum over τ gives (by Theorem 3.1 again) ∏_{B∈π_{ψ}} Z_{G[B]}(q_{1}, v). On the other hand, each partition π of V arises in this way from r\underline{|π|} different colorings ψ, since we have r choices to color the lexicographically first block of π, r − 1 choices for the lexicographically second block, and so forth. This proves (3.28). □

Important note: The formulae in this subsection — notably (3.33) together with the q = 1 case of (3.31) — are strongly reminiscent of Möbius inversion on the lattice of partitions Π(V). This is not an accident. In fact, the formula (3.30) is a special case of a “q_{1}–q_{2} generalization” of Möbius inversion that we present in Appendix A. We are grateful to an anonymous referee for drawing our attention to the connection of these formulae with Möbius inversion and for challenging us to find the underlying general principle.

3.3.2. Convolution formulae. In a similar way we can obtain convolution formulae for the multivariate Tutte polynomial by specializing (2.14)–(2.15):

Proposition 3.7. Let G = (V, E) be a finite loopless graph. Then

Z_{G}(q_{1} + q_{2}, v) = ∑_{W ⊆V} Z_{G[W]}(q_{1}, v) Z_{G[V \W]}(q_{2}, v) .  (3.40)

Moreover, for each i ∈ V we have

Ẑ_{G}(q_{1} + q_{2}, v) = ∑_{\begin{matrix}W ⊆ V \\ W ∋ i \end{matrix}} Ẑ_{G[W]}(q_{1}, v) Z_{G[V \W]}(q_{2}, v)  (3.41)

and in particular

Z_{G}(q, v) = ∑_{\begin{matrix}W ⊆ V \\ W ∋ i \end{matrix}} qC_{G[W]}(v) Z_{G[V \W]}(q, v) .  (3.42)

We also have

|V | Z_{G}(q_{2}, v) = ∑_{∅≠W ⊆V}[(q_{1} + q_{2})|W | − q_{1}|V |] Ẑ_{G[W]}(q_{1}, v) Z_{G[V \W]}(q_{2}, v) .

(3.43)

Proof. (3.40) and (3.41) are just (2.14) and (2.15), respectively, specialized to n = 1. Further specializing the latter to q_{1} = 0, we obtain (3.42). Finally, (3.43) is obtained by subtracting (q_{1} + q_{2}) × (3.41) from (3.40) and summing over i ∈ V. □

For completeness, let us give a simple direct proof of (3.41). [(3.40) is similar but easier, and is left as an exercise for the reader.]

Alternate Proof of Proposition 3.7. From the definition (3.2) we have

Ẑ_{G}(q_{1} + q_{2}, v) = ∑_{A⊆E}(q_{1} + q_{2})^{k(A)−1} ∏_{e∈A} v_{e} .  (3.44)

The factor (q_{1} + q_{2})^{k(A)−1} can be handled by choosing, for each connected component of (V, A) other than the component containing the distinguished vertex i, to color it either “1” or “2”, with a corresponding factor q_{1} or q_{2}, and summing over all such choices. Now define W ⊆ V to be the vertex set corresponding to the union of the components colored “1” together with the component containing i. By construction, W is compatible with A in the sense that A has no edges connecting W to V \ W. Moreover, every W ∋ i compatible with A is obtained exactly once by some choice of colors “1” and “2”. On the other hand, the right-hand side of (3.41) is given precisely by such a sum over compatible pairs (W, A) [the on Ẑ_{G[W]}(q_{1}, v) accounts for the fact that the component containing i carries no color and hence no factor q_{1}]. □

We do not know whether the Abel-type extensions (2.19)/(2.20), when applied to the multivariate Tutte polynomial, are of any interest.

3.4. Specialization to the complete graphs. Let us now take G to be the complete graph K_{n}, with all the edge weights v_{e} set equal to the same value v. We write Z_{n}(q, v), Ẑ_{n}(q, v) and C_{n}(v) for the corresponding polynomials.

3.4.1. Partition formulae. Specializing (3.28), we obtain the general identity

Z_{n}(q_{2}, v) = ∑_{π∈Π_{n}}(q_{2}/q_{1})\underline{|π|} ∏_{i=1}^{|π|} Z_{|π_{i}|}(q_{1}, v) ,  (3.45)

where the sum runs over (unordered) partitions π of [n], say π = {π_{1}, …, π_{ℓ}}, and |π| denotes the number of blocks in π (i.e., |π| = ℓ). Special cases of (3.45) arise at particular values of q_{1}:

Case q_{1} = 0. Specializing (3.31), we obtain the trivial identity

Z_{n}(q, v) = ∑_{π∈Π_{n}} q^{|π|} ∏_{i=1}^{|π|} C_{|π_{i}|}(v) .  (3.46)

Case q_{1} = 1. Specializing (3.32)–(3.34), we obtain the less trivial relations

Z_{n}(q, v) = ∑_{π∈Π_{n}} q\underline{|π|} (1 + v)^{n(n−1)/2−∥π∥}  (3.47)

C_{n}(v) = ∑_{π∈Π_{n}}(−1)^{|π|−1} (|π| − 1)! (1 + v)^{n(n−1)/2−∥π∥}  (3.48)

Z_{n}(−1, v) = ∑_{π∈Π_{n}}(−1)^{|π|} |π|! (1 + v)^{n(n−1)/2−∥π∥}  (3.49)

where

∥π∥ = ∑_{1≤i<j≤ℓ} |π_{i}| |π_{j}| = \frac{1}{2} (n^{2} − ∑_{i=1}^{ℓ} |π_{i}|^{2})  (3.50)

denotes the number of “cross-edges” in π, i.e., the number of edges in the complete ℓ-partite graph with vertex classes π_{1}, …, π_{ℓ}. Equivalently,

\frac{n(n − 1)}{2} − ∥π∥ = ∑_{i=1}^{ℓ} \frac{|π_{i}|(|π_{i}| − 1)}{2}  (3.51)

is the number of “internal edges” in π. The formulae (3.47)–(3.49) will play an important role in our study of the large-n asymptotics of C_{n}(v) and Z_{n}(q, v) at complex v [55].

3.4.2. Convolution formulae. Specializing (3.40)–(3.43) and exploiting the symmetries of the complete graph, we obtain

Z_{n}(q_{1} + q_{2}, v) = ∑_{k=0}^{n} \binom{n}{k} Z_{k}(q_{1}, v) Z_{n−k}(q_{2}, v)  (3.52)

Ẑ_{n}(q_{1} + q_{2}, v) = ∑_{k=1}^{n} \binom{n − 1}{k − 1} Ẑ_{k}(q_{1}, v) Z_{n−k}(q_{2}, v) for n ≥ 1  (3.53)

Z_{n}(q, v) = ∑_{k=1}^{n} \binom{n − 1}{k − 1} qC_{k}(v) Z_{n−k}(q, v) for n ≥ 1  (3.54)

Z_{n}(q_{2}, v) = ∑_{k=1}^{n} [\binom{n − 1}{k − 1}(q_{1} + q_{2}) − \binom{n}{k}q_{1}] Ẑ_{k}(q_{1}, v) Z_{n−k}(q_{2}, v) for n ≥ 1

(3.55)

On the other hand, these are just the one-dimensional identities (1.5), (1.6), (1.9) and (1.10) applied to the family a_{n}(q) = Z_{n}(q, v), which is indeed of the required form (1.2) by virtue of the generating-function formula (3.9).

The formula (3.54) can be used to compute the Z_{n}(q, v) inductively given the C_{k}(v). On the other hand, if we specialize (3.54) to q = 1 and use (3.3), we obtain the identity

(1 + v)^{n(n−1)/2} = ∑_{k=1}^{n} \binom{n − 1}{k − 1} C_{k}(v) (1 + v)^{(n−k)(n−k−1)/2} for n ≥ 1 (3.56)

or equivalently

C_{n}(v) = (1 + v)^{n(n−1)/2} − ∑_{k=1}^{n−1} \binom{n − 1}{k − 1} C_{k}(v) (1 + v)^{(n−k)(n−k−1)/2} for n ≥ 1 ,

(3.57)

which can be used to compute the C_{n}(v) inductively ab initio. We call (3.56)/(3.57) the “linear” identity for C_{n}(v). It goes back at least to Leroux [37, eq. (3.3)] and is probably much older; it can be proven by an easy direct argument based on considering the size k of the connected component containing a fixed vertex. [The same argument proves (3.54).]

Alternatively, if we specialize (3.55) to q_{1} = 1 and use (3.3), we obtain

Z_{n}(q, v) = ∑_{k=1}^{n} [\binom{n − 1}{k − 1}(1 + q) − \binom{n}{k}] (1 + v)^{k(k−1)/2} Z_{n−k}(q, v) for n ≥ 1 ,

(3.58)

which allows us to go directly from from Z_{n}(1, v) = (1+v)^{n(n−1)/2} to Z_{n}(q, v) without passing through C_{n}(v). We can also rewrite (3.58) as

Ẑ_{n}(q, v) = (1 + v)^{n(n−1)/2}

+ ∑_{k=1}^{n−1} [\binom{n − 1}{k}q − \binom{n − 1}{k − 1}] (1 + v)^{(n−k)(n−k−1)/2} Ẑ_{k}(q, v)

for n ≥ 1 , (3.59)

which manifestly generalizes (3.57) and reduces to it when q = 0.

3.5. A generalization. Let a = {a_{n}}_{n=0}^{∞} be an arbitrary sequence of coefficients belonging to the ring R, satisfying a_{0} = 1, and define the family of polynomials

Z_{n}(q; a) = ∑_{π∈Π_{n}} q\underline{|π|} ∏_{i=1}^{|π|} a_{|π_{i}|}  (3.60)

with the convention Z_{0} = 1. Note that Z_{n}(1; a) = a_{n}. This definition generalizes (3.47)/(3.51), and if we specialize to a_{n} = (1 + v)^{n(n−1)/2} we obtain Z_{n}(q, v).

A simple counting argument shows that

Z_{n}(q; a) = ∑_{b=0}^{n} \frac{q\underline{b}}{b!} ∑_{\begin{matrix}n_{1}, …, n_{b} ≥ 1 \\ ∑ n_{i} = n \end{matrix}} \binom{n}{n_{1}, …, n_{b}} ∏_{i=1}^{b} a_{n_{i}} .  (3.61)

Using this to compute the exponential generating function of the {Z_{n}(q; a)}, we find, after a short calculation using the binomial series, that

∑_{n=0}^{∞} \frac{x^{n}}{n!} Z_{n}(q; a) = (∑_{n=0}^{∞} \frac{x^{n}}{n!} a_{n})^{q} .  (3.62)

In other words, the family {Z_{n}(q; a)} is of the form {a_{n}(q)} defined in (1.2), with a_{n}(1) = a_{n}. But this should hardly be surprising, as (3.61) is simply the onedimensional case of (2.12) with q_{2} = q and q_{1} = 1. We have thus come full circle.

Likewise, the recursion

Z_{n}(q; a) = q ∑_{k=1}^{n} \binom{n − 1}{k − 1} a_{k} Z_{n−k}(q − 1; a)  (3.63)

can be proven from (3.60) by an easy direct argument based on considering the size k of the block of π containing some fixed element of [n]. But this identity is nothing other than (1.11) specialized to q_{1} = 1 and q_{2} = q − 1.

3.6. A related problem. Suppose we try a definition analogous to (3.60), but with ordinary powers q^{|π|} in place of falling factorials q\underline{|π|}. That is, let c = \{c_{n}\}_{n=1}^{∞} be an arbitrary sequence of coefficients belonging to the ring R, and define the family of polynomials

Y_{n}(q; c) = ∑_{π∈Π_{n}} q^{|π|} ∏_{i=1}^{|π|} c_{|π_{i}|}  (3.64)

with the convention Y_{0} = 1. Of course, the factor q^{|π|} is superfluous, because we can simply multiply each c_{n} by q, but it is convenient to keep it explicit. This definition generalizes (3.46), and if we specialize to c_{n} = C_{n}(v) we obtain Z_{n}(q, v).

A simple counting argument shows that

Y_{n}(q; c) = ∑_{b=0}^{n} \frac{q^{b}}{b!} ∑_{\begin{matrix}n_{1}, …, n_{b} ≥ 1 \\ ∑ n_{i} = n \end{matrix}} \binom{n}{n_{1}, …, n_{b}} ∏_{i=1}^{b} c_{n_{i}} .  (3.65)

Using this to compute the exponential generating function of the {Y_{n}(q; c)}, we find, after a short calculation using the exponential series, that

∑_{n=0}^{∞} \frac{x^{n}}{n!} Y_{n}(q; c) = exp(q ∑_{n=1}^{∞} \frac{x^{n}}{n!} c_{n}) .  (3.66)

In other words, the family {Y_{n}(q; c)} is again of the form {a_{n}(q)} defined in (1.2). But this should hardly be surprising, as (3.65) is simply the one-dimensional case of (2.3) [i.e., (1.3).] We have again come full circle.

Likewise, the recursion

Y_{n}(q; c) = q ∑_{k=1}^{n} \binom{n − 1}{k − 1} c_{k} Y_{n−k}(q; c) ,  (3.67)

which can be proven from (3.64) by considering the size k of the block of π containing some fixed element of [n], is nothing other than (1.9).

4. Nonlinear identity for the multivariate Tutte polynomial

4.1. General identity. In the preceding section we proved the identities (3.41) and (3.42) for the multivariate Tutte polynomial Z_{G}(q, v), which are based on choosing a single distinguished vertex i. We shall now prove a different identity that is based on choosing a pair of distinguished vertices i, j. Unlike the identities discussed in the preceding section, this one relies on the graphical structure of Z_{G}(q, v) and does not appear to generalize to arbitrary families {a_{n}(q)} of the type (1.2).

So let G = (V, E) be a finite undirected graph with |V | ≥ 2, and let i, j ∈ V with i ≠ j. We then have the following identity:

Theorem 4.1. Let G = (V, E) be a finite graph, and let i, j ∈ V with i ≠ j. Then

Z_{G}(q, v) = ∑_{\begin{matrix}W ⊆ V \\ W ∋ i, W ∌ j \end{matrix}} [q − 1 + ∏_{e∈E(W,j)}(1 + v_{e})] C_{G[W]}(v) Z_{G[V \W]}(q, v) (4.1)

where E(W, j) denotes the set of all edges with one endpoint in W and the other endpoint at j. In particular,

C_{G}(v) = ∑_{\begin{matrix}W ⊆ V \\ W ∋ i, W ∌ j \end{matrix}} [ ∏_{e∈E(W,j)}(1 + v_{e}) − 1] C_{G[W]}(v) C_{G[V \W]}(v) .  (4.2)

We do not know whether there exists a generalization of (4.1) involving q_{1} and q_{2} (rather than just q_{1} = 0).

The proof of Theorem 4.1 is based on looking at the connected component of i in the induced subgraph where j is deleted:

Proof. Start from the definition Z_{G}(q, v) = ∑_{A⊆E} q^{k(A)} ∏_{e∈A} v_{e}. Let G′ = (V, A) and

G′′ = G′ \j, and let W be the vertex set of the connected component of G′′ containing i. Let us now sum over all A ⊆ E that give rise in this way to a specified set W ⊆ V, and let us split this sum into two parts according as A does or does not contain at least one edge from j to W. If A does not contain such an edge, then W is a connected component of G′, giving rise to a factor q, and we get qC_{G[W]}(v) Z_{G[V \W]}(q, v). On the other hand, if A contains at least one such edge, then W forms part of the connected component of j (∈ V \W) in G′; hence there is no factor q, but there is a factor v_{e} for each edge e in the (nonempty) subset A ∩ E(W, j). Summing over all such nonempty subsets of E(W, j), we get

[ ∏_{e∈E(W,j)}(1 + v_{e}) − 1] C_{G[W]}(v) Z_{G[V \W]}(q, v) .  (4.3)

Putting everything together gives (4.1). Specialization to q = 0 yields (4.2). □

There is also a variant of (4.1) in which the right-hand side is completely expanded out. For notational simplicity we shall assume that G has no loop at the distinguished vertex j. (In the general case one must multiply by a factor 1 + v_{e} for each loop e at j.)

Proposition 4.2. Let G = (V, E) be a finite graph, let j ∈ V, and suppose that G has no loop at j. Then

Ẑ_{G}(q, v) = ∑_{π∈Π(V \{j})} ∏_{B∈π} [q − 1 + ∏_{e∈E(B,j)}(1 + v_{e})] C_{G[B]}(v)  (4.4)

where the sum runs over (unordered) partitions π of V \ {j}, and the product runs over blocks B of π. In particular,

C_{G}(v) = ∑_{π∈Π(V \{j})} ∏_{B∈π} [ ∏_{e∈E(B,j)}(1 + v_{e}) − 1] C_{G[B]}(v)  (4.5)

Proof. In (3.2), consider a term A ⊆ E, and let G′ = (V, A) and G′′ = G′ \ j. Let π be the partition of V \ {j} into vertex sets of connected components of G′′. We can recover G′ from G′′ by adjoining, for each block B of π, zero or more edges from the set E(B, j). If we adjoin zero edges, we get an extra factor q because B becomes the vertex set of a connected component of G′ that is distinct from the component containing j; if we adjoin one or more edges, we get no such factor. This proves (4.4). Specialization to q = 0 yields (4.5). □

When v_{e} = v for all edges e, the formulae (4.4) and (4.5) can be found in Gessel [17, Theorems 13 and 10]. The special case of (4.5) in which v_{e} = −1 for all e was also found by Borgs [8] and used recently by him [9, Lemma 3.2] to bound the complex zeros of chromatic polynomials (a variant of the proof in [56]). Indeed, we were led to formulate (4.4)/(4.5) by meditating on Borgs’ special case, oblivious to the fact that they had already been essentially found by Gessel!

Finally, let us use (4.2) to prove an interesting inequality concerning the polynomials C_{G}(v). Let

c(A) = |A| − |V | + k(A)  (4.6)

be the cyclomatic number of the subgraph (V, A), and let us define the generalized connected sum

C_{G}(v, λ) = ∑_{\begin{matrix}A ⊆ E \\ k(A) = 1 \end{matrix}} λ^{c(A)} ∏_{e∈A} v_{e}  (4.7a)

= λ^{−(|V |−1)} C_{G}(λv) .  (4.7b)

Of course, (4.7b) shows that C_{G}(v, λ) contains no more information than C_{G}(v); it is simply a convenient way of scaling all the variables v_{e} simultaneously while removing a factor λ^{|V |−1}. In particular, C_{G}(v, λ) interpolates between the spanning-tree sum (λ = 0) and the connected-spanning-subgraph sum (λ = 1). We then have the following result [56, Remark 2 in Section 4.1] [53, Proposition 2.5]:

Proposition 4.3. Let G = (V, E) be a finite graph (V ≠ ∅) equipped with real edge weights v = (v_{e})_{e∈E} satisfying −1 ≤ v_{e} ≤ 0 for all e ∈ E. Then

(−1)^{ℓ+|V |−1} \frac{∂^{ℓ}}{∂λ^{ℓ}} C_{G}(v, λ) ≥ 0  (4.8)

on 0 ≤ λ ≤ 1, for all integers ℓ ≥ 0.

This inequality was proven in [53,56] using a “partitionability” method going back to Penrose [41].^{17} Here we prove it using the recursion (4.2):

Proof of Proposition 4.3. By induction on |V |. When |V | = 1, G necessarily consists of zero or more loops attached to the sole vertex, so

C_{G}(v, λ) = ∏_{e∈E}(1 + λv_{e}) .  (4.9)

Using v_{e} ≤ 0 and 1 + λv_{e} ≥ 0, it is easy to see that (4.8) holds.

Now assume that |V | ≥ 2. Replacing v by λv in (4.2) and using (4.7b), we obtain

C_{G}(v, λ) = ∑_{\begin{matrix}W ⊆ V \\ W ∋ i, W ∌ j \end{matrix}} λ^{−1}[ ∏_{e∈E(W,j)}(1 + v_{e}) − 1] C_{G[W]}(v, λ) C_{G[V \W]}(v, λ)

(4.10a)

= ∑_{\begin{matrix}W ⊆ V \\ W ∋ i, W ∌ j \end{matrix}} ( ∑_{∅≠B⊆E(W,j)}λ^{|B|−1} ∏_{e∈B} v_{e}) C_{G[W]}(v, λ) C_{G[V \W]}(v, λ) .

(4.10b)

Now apply ∂^{ℓ}/∂λ^{ℓ} to both sides: on the right-hand side we will have terms in which ℓ_{1} derivatives act on ∑ λ^{|B|−1} ∏ v_{e}, ℓ_{2} act on C_{G[W]}(v, λ), and ℓ_{3} act on C_{G[V \W]}(v, λ), where ℓ_{1} + ℓ_{2} + ℓ_{3} = ℓ. The induction hypothesis is applicable because 1 ≤ |W | ≤ |V | − 1. So it suffices to check that

(−1)^{ℓ_{1}−1} \frac{∂^{ℓ_{1}}}{∂λ^{ℓ_{1}}} ( ∑_{∅≠B⊆E(W,j)}λ^{|B|−1} ∏_{e∈B} v_{e}) ≥ 0 .  (4.11)

To prove this, let us order the elements of E(W, j), i.e., consider E(W, j) ≃ [m] where m = |E(W, j)|. Then, by singling out the smallest element in each set B, we can write

∑_{∅≠B⊆[m]}λ^{|B|−1} ∏_{e∈B} v_{e} = ∑_{i=1}^{m} v_{i} ∏_{j=i+1}^{m}(1 + λv_{j}) .  (4.12)

We have v_{i} ≤ 0; each ∂/∂λ brings down some factor v_{j} ≤ 0; and the undifferentiated factors satisfy 1 + λv_{j} ≥ 0. So (4.11) holds. □

It is worth remarking that (4.11) is nothing other than Proposition 4.3 specialized to the graph K_{2}^{(m)} consisting of two vertices connected by m parallel edges. Moreover, the identity (4.12) is nothing other than (one version of) the partitionability identity for K_{2}^{(m)}.

17For the partitionability method (which applies to matroids as well as graphs), see also [7, 19] and the other references mentioned in [53, Section 2.2].

4.2. Specialization to the complete graphs. Specializing (4.1) to the complete graph K_{n} with equal weights v, we obtain

Z_{n}(q, v) = ∑_{k=1}^{n−1} \binom{n − 2}{k − 1} [q + (1 + v)^{k} − 1] C_{k}(v) Z_{n−k}(q, v) for n ≥ 2 (4.13)

(see [17, eq. (5)] for an equivalent formula). Specializing this to q = 0, we obtain

C_{n}(v) = ∑_{k=1}^{n−1} \binom{n − 2}{k − 1} [(1 + v)^{k} − 1] C_{k}(v) C_{n−k}(v) for n ≥ 2 ,  (4.14)

a result apparently first proven by Leroux [37, eq. (3.5)] (see also [17, eq. (2)]).^{18} And specializing this latter formula to v = 1, we obtain the identity of Riordan, Nijenhuis, Wilf and Kreweras [31, 40, 47] for counting connected graphs. We call (4.14) the “nonlinear” identity for C_{n}(v).

On the other hand, specializing (4.13) to q = 1, dividing both sides by (1 + v)^{n−1} and relabelling n → n + 1, we recover the “linear” identity (3.56).

The formula (4.14) has also been derived in a different context. Let T be a tree with vertex set [n], rooted at the vertex 1. An inversion of T is an ordered pair (j, k) of vertices such that j > k > 1 and k is a descendant of j (i.e., the path from 1 to k passes through j). We define the inversion enumerator for trees [20, 31, 38] (see also [10,17,19]) to be the polynomial

I_{n}(y) = ∑_{trees T on [n]} y^{inv(T)}  (4.15)

where inv(T) denotes the number of inversions in T. This polynomial turns out to be related to C_{n}(v) by the beautiful formula [3,20,31,38]

C_{n}(v) = v^{n−1}I_{n}(1 + v) .  (4.16)

Now, Mallows, Riordan and Kreweras [31,38] show that I_{n}(y) satisfies the recursion

I_{n}(y) = ∑_{k=1}^{n−1} \binom{n − 2}{k − 1} (∑_{j=0}^{k−1} y^{j}) I_{k}(y) I_{n−k}(y) for n ≥ 2 .  (4.17)

But using (4.16), it is easily seen that (4.17) is equivalent to (4.14).

Let us remark, finally, that even without using (4.15), it follows immediately from the recursion (4.17) [together with the initial condition I_{1}(y) = 1] that the polynomials I_{n}(y) ≡ C_{n}(y − 1)/(y − 1)^{n−1} have nonnegative (indeed, strictly positive) integer coefficients. On the other hand, the nonnegativity of the derivatives of I_{n}(y) at y = 0 is also a special case of Proposition 4.3.

Appendix A. A generalization of Möbius inversion on the partition lattice

In this appendix we present an apparently new generalization of Möbius inversion on the lattice of partitions of a finite set, which is inspired by the formulae in Section 3.3.1 and in particular by (3.30), and more generally by (2.13). We refer to [59, Chapter 3] for basic facts about posets and Möbius inversion.

18See also [5, p. 306, Exercise 4.2.2] for a proof of (4.14) in species language.

To begin with, let P be a finite poset. Then the zeta function ζ on P is the function ζ: P × P → ℤ defined by

ζ(x, y) = \begin{cases}1 & if x ≤ y \\ 0 & if x ≰ y \end{cases}  (A.1)

(We think of ζ as a matrix whose rows and columns are indexed by P.) The Möbius function μ on P is the two-sided matrix inverse of ζ, i.e., it satisfies ζμ = μζ = I. It can be computed by the recursion

μ(x, y) = \begin{cases}1 & if x = y \\ − ∑_{x≤z<y} μ(x, z) & if x < y \\ 0 & if x ≰ y \end{cases}  (A.2)

Now let S be a finite set, and let P be the lattice Π(S) of partitions of S, ordered by refinement. It is well known [59, p. 128] that the Möbius function of Π(S) is given by

μ(σ, π) = \begin{cases}∏_{i=1}^{k}(−1)^{λ_{i}−1}(λ_{i} − 1)! & if σ ≤ π = \{B_{1}, …, B_{k}\} and B_{i} is partitioned into λ_{i} blocks in σ \\ 0 & if σ ≰ π \end{cases} (A.3)

We generalize this as follows: let q_{1} and q_{2} be indeterminates, and define

μ_{q_{1},q_{2}}(σ, π) = \begin{cases}∏_{i=1}^{k} ∏_{j=1}^{λ_{i}−1}(q_{2} − jq_{1}) & if σ ≤ π = \{B_{1}, …, B_{k}\} and B_{i} is partitioned into λ_{i} blocks in σ \\ 0 & if σ ≰ π \end{cases} (A.4)

Let us observe for future reference that

∏_{j=1}^{m−1}(q_{2} − jq_{1}) = q_{1}^{m}q_{2}^{−1}(q_{2}/q_{1})\underline{m} = q_{1}^{m−1}(q_{2}/q_{1} − 1)\underline{m−1} .  (A.5)

Then we have in particular

μ_{0,1} = ζ  (A.6a)
μ_{1,0} = μ  (A.6b)
μ_{q,q} = I for all q  (A.6c)

We shall prove the following generalization of Möbius inversion:

Theorem A.1. Let S be a finite set, and define the matrices μ_{q_{1},q_{2}} on Π(S) by (A.4). Then

μ_{q_{1},q_{2}} μ_{q_{2},q_{3}} = μ_{q_{1},q_{3}}  (matrix multiplication)  (A.7)

We interpret (A.7) as an identity in the polynomial ring ℤ[q_{1}, q_{2}, q_{3}], but of course it also holds when q_{1}, q_{2}, q_{3} are specialized to specific integer values (or more generally to specific values in a commutative ring R). In particular, Möbius inversion corresponds to the special cases (q_{1}, q_{2}, q_{3}) = (0, 1, 0) and (1, 0, 1).

The proof of Theorem A.1 will be based on the following lemma, which we think is of some interest in its own right. It is probably not new, but we have been unable to find any reference.

Lemma A.2. Let m be a positive integer, and let r and s be indeterminates. Then

∑_{ω∈Π_{m}} r\underline{|ω|} (∏_{B∈ω} s\underline{|B|}) = (rs)\underline{m}  (A.8)

as an identity in the polynomial ring ℤ[r, s].

Let us remark that if one divides (A.8) by s^{m} and takes s → ∞ (or equivalently just extracts the coefficient of s^{m}), one obtains the well-known formula (3.21)/(3.38); while if one sets r = q/ϵ, s = ϵq and takes ϵ → 0, then one obtains the formula

∑_{π∈Π_{m}} μ(ˆ0, π) q^{|π|} = q\underline{m}  (A.9)

due to Rota [50, Section 9] [59, pp. 128, 162, 187] (here ˆ0 denotes the partition in which every element is a singleton).

Proof of Lemma A.2. It suffices to prove (A.8) for positive integers r, s. Then the right-hand side counts the proper colorings of the complete graph K_{m} with rs colors. But so does the left-hand side, if we use the color set [r] × [s] and define ω to be the partition of [m] in which two vertices are placed in the same block if and only if they receive a color with the same first index. □

Second Proof of Lemma A.2 (suggested independently by Christian Krattenthaler and Richard Stanley). We use the isomorphism of weighted species

Partitions = Sets ∘ NonemptySets ,  (A.10)

where a Set of cardinality b is given a weight r\underline{b}, a NonemptySet of cardinality k is given a weight s\underline{k}, and a partition ω is weighted as on the left-hand side of (A.8).^{19} The corresponding exponential generating functions are

F (x) = ∑_{b=0}^{∞} \frac{x^{b}}{b!} r\underline{b} = (1 + x)^{r}  (A.11)

G(x) = ∑_{k=1}^{∞} \frac{x^{k}}{k!} s\underline{k} = (1 + x)^{s} − 1  (A.12)

and hence

(F ∘ G)(x) = (1 + x)^{rs} = ∑_{m=0}^{∞} \frac{x^{m}}{m!} (rs)\underline{m} ,  (A.13)

which proves (A.8) for all m ≥ 0. □

19See [5, pp. 44, 86] for this isomorphism with a different weighting. For the reader unfamiliar with the theory of combinatorial species [5], it suffices to observe that a partition of a finite set S is simply a set of nonempty subsets of S that disjointly cover S; one can then invoke [60, Theorem 5.1.4] to complete the proof.

Proof of Theorem A.1. Let σ ≤ π = {B_{1}, …, B_{k}} where B_{i} is partitioned into λ_{i} blocks in σ, and let us compute

(μ_{q_{1},q_{2}} μ_{q_{2},q_{3}})(σ, π) = ∑_{σ≤τ≤π} μ_{q_{1},q_{2}}(σ, τ) μ_{q_{2},q_{3}}(τ, π) .  (A.14)

The partition τ is specified by saying, for each i ∈ [k], how the corresponding λ_{i} blocks of σ get grouped in τ. The sum (A.14) will then factorize over i, with the ith factor given by

∑_{\begin{matrix}ω ∈ Π_{λ_{i}} \\ ω = \{B̂_{1}, …, B̂_{μ_{i}}\} \end{matrix}}(∏_{α=1}^{μ_{i}} ∏_{j=1}^{|B̂_{α}|−1}(q_{2} − jq_{1})) ∏_{k=1}^{μ_{i}−1}(q_{3} − kq_{2})

= ∑_{\begin{matrix}ω ∈ Π_{λ_{i}} \\ ω = \{B̂_{1}, …, B̂_{μ_{i}}\} \end{matrix}}(∏_{α=1}^{μ_{i}} q_{1}^{|B̂_{α}|}q_{2}^{−1}(q_{2}/q_{1})\underline{|B̂_{α}|}) q_{2}^{μ_{i}}q_{3}^{−1}(q_{3}/q_{2})\underline{μ_{i}}

= q_{1}^{λ_{i}}q_{3}^{−1} ∑_{\begin{matrix}ω ∈ Π_{λ_{i}} \\ ω = \{B̂_{1}, …, B̂_{μ_{i}}\} \end{matrix}}(∏_{α=1}^{μ_{i}}(q_{2}/q_{1})\underline{|B̂_{α}|}) (q_{3}/q_{2})\underline{μ_{i}}

= q_{1}^{λ_{i}}q_{3}^{−1}(q_{3}/q_{1})\underline{λ_{i}}  (A.15)

by Lemma A.2. □

Second Proof of Theorem A.1 (suggested by Richard Stanley). We prove (A.7) for S = [n] simultaneously for all n ≥ 1, using the interpretation of convolution of multiplicative functions on Π = (Π_{1}, Π_{2}, …) in terms of composition of exponential generating functions [60, pp. 7–8]. We first observe that μ_{q_{1},q_{2}} is a multiplicative function on Π, with underlying numerical function

f_{q_{1},q_{2}}(m) = ∏_{j=1}^{m−1}(q_{2} − jq_{1}) = q_{1}^{m}q_{2}^{−1}(q_{2}/q_{1})\underline{m}  (A.16)

and corresponding exponential generating function

F_{q_{1},q_{2}}(x) = ∑_{m=1}^{∞} f_{q_{1},q_{2}}(m) \frac{x^{m}}{m!} = q_{2}^{−1}[(1 + q_{1}x)^{q_{2}/q_{1}} − 1] .  (A.17)

It is easy to check that

F_{q_{2},q_{3}}(F_{q_{1},q_{2}}(x)) = F_{q_{1},q_{3}}(x) .  (A.18)

By [60, Theorem 5.1.11], the identities (A.7) for all n ≥ 1 are an immediate consequence.^{20} □ Remark. If we define the diagonal matrix D_{r} by

20Using [60, Theorem 5.1.11] with the coefficient field K taken to be (say) ℝ, this argument proves (A.7) for q_{1}, q_{2}, q_{3} ∈ ℝ \ {0}, which is more than enough to imply it as a polynomial identity.

Alternatively, we can use [60, Theorem 5.1.11] with K taken to be (say) the field ℝ(q_{1}, q_{2}, q_{3}) of rational functions in the indeterminates q_{1}, q_{2}, q_{3}, which yields (A.7) directly as a polynomial identity.

D_{r}(σ, π) = \begin{cases}r^{|σ|} & if σ = π \\ 0 & if σ ≠ π \end{cases}  (A.19)

then an easy calculation shows that

D_{r} μ_{q_{1},q_{2}} D_{r}^{−1} = μ_{rq_{1},rq_{2}} .  (A.20)

This is why many things involving μ_{q_{1},q_{2}} depend only on the ratio q_{2}/q_{1} [cf. (3.28)].

We can apply Theorem A.1 as follows: Let R be a commutative ring, and fix a function f: Π(S) → R and an element q_{0} ∈ R (it could be an indeterminate if desired). Now introduce a new indeterminate q, and define F_{q}: Π(S) → R[q] by

F_{q} = f μ_{q_{0},q}  (A.21)

or in more detail

F_{q}(π) = ∑_{σ∈Π(S)} f(σ) μ_{q_{0},q}(σ, π) .  (A.22)

By construction we have imposed the “initial condition”

F_{q_{0}} = f  (A.23)

(here F_{q_{0}} means of course that the indeterminate q is replaced by the value q_{0} ∈ R). Most importantly, Theorem A.1 implies that the q-dependence of F_{q} is “coherent” in the sense that

F_{q_{1}} μ_{q_{1},q_{2}} = F_{q_{2}} .  (A.24)

The formula (3.30) is now the special case of (A.24) in which we take S = V,

F_{q}(π) = ∏_{B∈π} Ẑ_{G[B]}(q, v) ,  (A.25)

and we evaluate (A.24) at π = ˆ1 (the partition in which all of V belongs to a single block). More generally, in place of Ẑ_{G[B]}(q, v) we can use â_{1_{B}}(q) where {â_{n}(q)} is any family arising as in Section 2; we then obtain (2.13) specialized to n = 1.^{21}

The formulae in this appendix seem to be special for the partition lattice. Still, it may not be totally absurd to ask: Might there exist “q_{1}–q_{2} generalizations” of Möbius inversion for some other posets? Maybe even for some natural class of posets?

Acknowledgments

We are grateful to Pierre Leroux for an extremely careful reading of the manuscript and for many suggestions, both substantive and bibliographic. In particular, it is thanks to him that our attention was drawn to [5, Section 3.1] and notably to [5, p. 189, Exercise 3.1.22], from which we learned about the Abel-type extensions (1.16)– (1.19).

We finished the first version of this paper, by unhappy circumstance, on the same day that we learned that Pierre had been struck with a grave illness, to which he succumbed two weeks later. We dedicate this work to his memory.

21Note also that, in these formulae, we use â_{n}(q) [or c_{n}] only for 0 ≤ n ≤ 1.

Finally, we are grateful to an anonymous referee for pointing out the connection of the formulae of Section 3.3.1 with Möbius inversion — which led us to discover the results reported in the Appendix — and to Christian Krattenthaler and Richard Stanley for comments on these results.

This research was supported in part by U.S. National Science Foundation grant PHY–0424082, by U.K. Engineering and Physical Sciences Research Council grant GR/S26323/01, and by a Leverhulme Visiting Professorship.

References

[1] G.E. Andrews, R. Askey and R. Roy, Special Functions (Cambridge University Press, Cambridge–New York, 1999), Section 6.2.

[2] W. Magnus, F. Oberhettinger, and F.G. Tricomi, Higher Transcendental Functions, vol. 2 (McGraw-Hill, New York, 1953).

[3] J.S. Beissinger, On external activity and inversions in trees, J. Combin. Theory B 33, 87–92 (1982).

[4] G.D. Birkhoff, A determinant formula for the number of ways of coloring a map, Ann. Math. 14, 42–46 (1912).

[5] F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures (Cambridge University Press, Cambridge–New York, 1998).

[6] N. Biggs, Algebraic Graph Theory, 2nd ed. (Cambridge University Press, Cambridge–New York, 1993), p. 103, item 13e.

[7] A. Björner, The homology and shellability of matroids and geometric lattices, in N. White (editor), Matroid Applications (Encyclopedia of Mathematics and its Applications #40), Chapter 7, pp. 226–283 (Cambridge University Press, Cambridge, 1992).

[8] C. Borgs, Polymer systems, Pirogov–Sinai theory and conductance bounds. Lecture notes, Microsoft Research, October 2000, unpublished, cited in [9, p. 68].

[9] C. Borgs, Absence of zeros for the chromatic polynomial of bounded degree graphs, Combin. Probab. Comput. 15, 63–74 (2006).

[10] C. Chauve, P. Duchon and S. Dulucq, Une généralisation des résultats de Kreweras sur le polynôme énumérateur des inversions dans les arborescences, Ann. Sci. Math. Québec 24, 129–144 (2000).

[11] L. Comtet, Advanced Combinatorics: The Art of Finite and Infinite Expansions (D. Reidel, Dordrecht–Boston, 1974), Section 3.3.

[12] J.P. Fillmore and S.G. Williamson, A linear algebra setting for the Rota–Mullin theory of polynomials of binomial type, Linear and Multilinear Algebra 1, 67–80 (1973).

[13] D. Foata, La série génératrice exponentielle dans les problèmes d’énumération (Presses de l’Université de Montréal, Montréal, 1974).

[14] D. Foata and M.-P. Schützenberger, Théorie géométrique des polynômes eulériens, Lecture Notes in Mathematics #138 (Springer-Verlag, Berlin–New York, 1970), Chapitre III.

[15] C.M. Fortuin and P.W. Kasteleyn, On the random-cluster model. I. Introduction and relation to other models, Physica 57, 536–564 (1972).

[16] A.M. Garsia, An exposé of the Mullin–Rota theory of polynomials of binomial type, Linear and Multilinear Algebra 1, 47–65 (1973).

[17] I.M. Gessel, Enumerative applications of a decomposition for graphs and digraphs, Discrete Math. 139, 257–271 (1995).

[18] I.M. Gessel, Applications of the classical umbral calculus, Algebra Univers. 49, 397–434 (2003).

[19] I.M. Gessel and B.E. Sagan, The Tutte polynomial of a graph, depth-first search, and simplicial complex partitions, Electron. J. Combin. 3, no. 2, #R9 (1996).

[20] I. Gessel and D.-L. Wang, Depth-first search as a combinatorial correspondence, J. Combin. Theory A 26, 308–313 (1979).

[21] H.W. Gould, Some generalizations of Vandermonde’s convolution, Amer. Math. Monthly 63, 84–91 (1956).

[22] H.W. Gould, Final analysis of Vandermonde’s convolution, Amer. Math. Monthly 64, 409–415 (1957).

[23] H.W. Gould, Coefficient identities for powers of Taylor and Dirichlet series, Amer. Math. Monthly 81, 3–14 (1974).

[24] H.W. Gould and J. Kaucký, Evaluation of a class of binomial coefficient summations, J. Comb. Theory 1, 233–247 (1966); erratum, J. Comb. Theory A 12, 309–310 (1972).

[25] R.L. Graham, D.E. Knuth and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2nd ed. (Addison-Wesley, Reading, Mass., 1994).

[26] G. Grimmett, The Random-Cluster Model (Springer-Verlag, New York, 2006).

[27] F. Harary and E.M. Palmer, Graphical Enumeration (Academic Press, New York, 1973).

[28] W.P. Johnson, The Pfaff/Cauchy derivative identities and Hurwitz type extensions, Ramanujan J. 13, 167–201 (2007).

[29] P.W. Kasteleyn and C.M. Fortuin, Phase transitions in lattice systems with random local properties, J. Phys. Soc. Japan 26 (Suppl.), 11–14 (1969).

[30] D.E. Knuth, Convolution polynomials, Mathematica J. 2, 67–78 (1992);

    arχiv:math.CA/9207221.

[31] G. Kreweras, Une famille de polynômes ayant plusieurs propriétés énumeratives, Period. Math. Hungar. 11, 309–320 (1980).

[32] G. Labelle, Sur l’inversion et l’itération continue des séries formelles, Europ. J. Combin. 1, 113–138 (1980).

[33] G. Labelle, Une nouvelle démonstration combinatoire des formules d’inversion de Lagrange, Adv. Math. 42, 217–247 (1981).

[34] G. Labelle and P. Leroux, An extension of the exponential formula in enumerative combinatorics, Electron. J. Combin. 3, no. 2, #R12 (1996).

[35] B. Lass, Orientations acycliques et le polynôme chromatique, European J. Combin. 22, 1101– 1123 (2001).

[36] N.N. Lebedev, Special Functions and Their Applications (Prentice-Hall, Englewood Cliffs, N.J., 1965).

[37] P. Leroux, Methoden der Anzahlbestimmung für einige Klassen von Graphen [Methods of enumeration for some classes of graphs], Bayreuth. Math. Schr. 26, 1–36 (1988).

[38] C.L. Mallows and J. Riordan, The inversion enumerator for labeled trees, Bull. Amer. Math. Soc. 74, 92–94 (1968).

[39] R. Mullin and G.-C. Rota, On the foundations of combinatorial theory. III. Theory of binomial enumeration, in Graph Theory and its Applications, edited by Bernard Harris (Academic Press, New York, 1970), pp. 167–213.

[40] A. Nijenhuis and H.S. Wilf, The enumeration of connected graphs and linked diagrams, J. Combin. Theory A 27, 356–359 (1979).

[41] O. Penrose, Convergence of fugacity expansions for classical systems, in T.A. Bak (editor), Statistical Mechanics: Foundations and Applications, pp. 101–109 (Benjamin, New York– Amsterdam, 1967).

[42] J. Pitman, Random mappings, forests, and subsets associated with Abel–Cayley–Hurwitz multinomial expansions, Sém. Lothar. Combin. 46, article B46h (2001).

[43] J. Pitman, Forest volume decompositions and Abel–Cayley–Hurwitz multinomial expansions, J. Combin. Theory A 98, 175–191 (2002).

[44] R.B. Potts, Some generalized order-disorder transformations, Proc. Cambridge Philos. Soc. 48, 106–109 (1952).

[45] D.L. Reiner, Multivariate sequences of binomial type, Stud. Appl. Math. 57, 119–133 (1977).

[46] J. Riordan, Combinatorial Identities (Wiley, New York, 1968), especially Sections 1.5 and 1.6.

[47] J. Riordan, unpublished, cited in [27, p. 8] and [40, pp. 356–357].

[48] S.M. Roman and G.-C. Rota, The umbral calculus, Adv. Math. 27, 95–188 (1978).

[49] S.M. Roman, The Umbral Calculus (Academic Press, New York, 1984).

[50] G.-C. Rota, On the foundations of combinatorial theory. I. Theory of Möbius functions, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2, 340–368 (1964).

[51] G.-C. Rota, D. Kahaner and A. Odlyzko, On the foundations of combinatorial theory. VIII. Finite operator calculus, J. Math. Anal. Appl. 42, 684–760 (1973). [Reprinted in G.-C. Rota, Finite Operator Calculus (Academic Press, New York–London, 1975), Chapter 2.]

[52] G.-C. Rota and B.D. Taylor, The classical umbral calculus, SIAM J. Math. Anal. 25, 694–711 (1994).

[53] A.D. Scott and A.D. Sokal, The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma, J. Stat. Phys. 118, 1151–1261 (2005); arχiv:cond-mat/0309352.

[54] A.D. Scott and A.D. Sokal, On dependency graphs and the lattice gas, Combin. Probab. Comput. 15, 253–279 (2006).

[55] A.D. Scott and A.D. Sokal, Asymptotic behavior at complex parameter for the Tutte polynomials (alias Potts-model partition functions) of the complete graphs K_{n}, in preparation.

[56] A.D. Sokal, Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions, Combin. Probab. Comput. 10, 41–77 (2001); arχiv:cond-mat/9904146.

[57] A.D. Sokal, The multivariate Tutte polynomial (alias Potts model) for graphs and matroids, in Surveys in Combinatorics, 2005 , edited by Bridget S. Webb (Cambridge University Press, Cambridge–New York, 2005), pp. 173–226; arχiv:math.CO/0503607.

[58] A.J. Stam, Two identities in the theory of polynomials of binomial type, J. Math. Anal. Appl. 122, 439–443 (1987).

[59] R.P. Stanley, Enumerative Combinatorics, vol. 1 (Wadsworth & Brooks/Cole, Monterey, California, 1986). Reprinted by Cambridge University Press, 1997.

[60] R.P. Stanley, Enumerative Combinatorics, vol. 2 (Cambridge University Press, Cambridge– New York, 1999).

[61] V. Strehl, Identities of Rothe–Abel–Schläfli–Hurwitz-type, Discrete Math. 99, 321–340 (1992).

[62] J.R. Swenson, The chromatic polynomial of a complete bipartite graph, Amer. Math. Monthly 80, 797–798 (1973).

[63] W.T. Tutte, On dichromatic polynominals, J. Combin. Theory 2, 301–320 (1967).

[64] G.E. Uhlenbeck and G.W. Ford, The theory of linear graphs with applications to the theory of the virial development of the properties of gases, in J. de Boer and G.E. Uhlenbeck (editors), Studies in Statistical Mechanics, vol. I, pp. 119–211 (North-Holland, Amsterdam, 1962).

[65] D.J.A. Welsh and C. Merino, The Potts model and the Tutte polynomial, J. Math. Phys. 41, 1127–1152 (2000).

[66] H. Whitney, A logical expansion in mathematics, Bull. Amer. Math. Soc. 38, 572–579 (1932).

[67] H.S. Wilf, generatingfunctionology, 2nd ed. (Academic Press, San Diego–London, 1994), Chapter 3.

[68] F.Y. Wu, The Potts model, Rev. Mod. Phys. 54, 235–268 (1982); erratum 55, 315 (1983).

[69] F.Y. Wu, Potts model of magnetism (invited), J. Appl. Phys. 55, 2421–2425 (1984).

[70] J. Zeng, Multinomial convolution polynomials, Discrete Math. 160, 219–228 (1996).