% expidentities_v2.tex % Version 1: ADSokal 22 Mar 05, updated 15 Jan 06, finished 24 Feb 08 % Dedication to Pierre added 10 Mar 08 % Version 2: ADSokal started 27 Jan 09, finished 4 Feb 09 \documentclass[12pt,reqno]{amsart} \usepackage{amsfonts,amssymb,amsmath,subeqnarray} %\usepackage{amsfonts,amssymb,amsmath,subeqnarray,eqsection,indent} \usepackage{bm} %% For bold math symbols \usepackage{cite} %% To amalgamate citations %%\usepackage{drafthead} %% REMEMBER TO COMMENT THIS OUT!!!!! \numberwithin{equation}{section} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{definition}[theorem]{Definition} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem*{remark}{Remark} \newtheorem{example}[theorem]{Example} \renewcommand{\theenumi}{\alph{enumi}} \renewcommand{\labelenumi}{(\theenumi)} \def\eop{\hbox{\kern1pt\vrule height6pt width4pt depth1pt\kern1pt}\medskip} \def\prf{\par\noindent{\bf Proof.\enspace}\rm} %\def\rmk{\par\medskip\noindent{\bf Remark\enspace}\rm} \newcommand{\be}{\begin{equation}} \newcommand{\ee}{\end{equation}} \newcommand{\<}{\langle} \renewcommand{\>}{\rangle} \newcommand{\widebar}{\overline} \def\reff#1{(\protect\ref{#1})} \def\spose#1{\hbox to 0pt{#1\hss}} \def\ltapprox{\mathrel{\spose{\lower 3pt\hbox{$\mathchar"218$}} \raise 2.0pt\hbox{$\mathchar"13C$}}} \def\gtapprox{\mathrel{\spose{\lower 3pt\hbox{$\mathchar"218$}} \raise 2.0pt\hbox{$\mathchar"13E$}}} \def\textprime{${}^\prime$} %\def\proof{\par\medskip\noindent{\sc Proof.\ }} %\def\firstproof{\par\medskip\noindent{\sc First Proof.\ }} %\def\secondproof{\par\medskip\noindent{\sc Second Proof.\ }} %\def\thirdproof{\par\medskip\noindent{\sc Third Proof.\ }} %\def\qed{\hbox{\hskip 6pt\vrule width6pt height7pt depth1pt \hskip1pt}\bigskip} %\def\qed{ $\square$ \bigskip} %\def\proofof#1{\bigskip\noindent{\sc Proof of #1.\ }} %\def\firstproofof#1{\bigskip\noindent{\sc First Proof of #1.\ }} %\def\secondproofof#1{\bigskip\noindent{\sc Second Proof of #1.\ }} %\def\thirdproofof#1{\bigskip\noindent{\sc Third Proof of #1.\ }} %\def\altproofof#1{\bigskip\noindent{\sc Alternate Proof of #1.\ }} \def\half{ {\frac {1 } { 2}} } \def\third{ {\frac {1 } { 3}} } \def\twothird{ {\frac {2 } { 3}} } \def\smfrac#1#2{\textstyle{\frac {#1} { #2}}} \def\smhalf{ \smfrac{1}{2} } \newcommand{\real}{\mathop{\rm Re}\nolimits} \renewcommand{\Re}{\mathop{\rm Re}\nolimits} \newcommand{\imag}{\mathop{\rm Im}\nolimits} \renewcommand{\Im}{\mathop{\rm Im}\nolimits} \newcommand{\sgn}{\mathop{\rm sgn}\nolimits} \newcommand{\tr}{\mathop{\rm tr}\nolimits} \newcommand{\supp}{\mathop{\rm supp}\nolimits} \def\hboxscript#1{ {\hbox{\scriptsize\em #1}} } \renewcommand{\emptyset}{\varnothing} \newcommand{\restrict}{\upharpoonright} \renewcommand{\implies}{\;\Longrightarrow\;} \newcommand{\scra}{{\mathcal{A}}} \newcommand{\scrb}{{\mathcal{B}}} \newcommand{\scrc}{{\mathcal{C}}} \newcommand{\scrf}{{\mathcal{F}}} \newcommand{\scrg}{{\mathcal{G}}} \newcommand{\scrh}{{\mathcal{H}}} \newcommand{\scrk}{{\mathcal{K}}} \newcommand{\scrl}{{\mathcal{L}}} \newcommand{\scro}{{\mathcal{O}}} \newcommand{\scrp}{{\mathcal{P}}} \newcommand{\scrr}{{\mathcal{R}}} \newcommand{\scrs}{{\mathcal{S}}} \newcommand{\scrt}{{\mathcal{T}}} \newcommand{\scrv}{{\mathcal{V}}} \newcommand{\scrw}{{\mathcal{W}}} \newcommand{\scrz}{{\mathcal{Z}}} \newcommand{\ahat}{{\widehat{a}}} \newcommand{\Zhat}{{\widehat{Z}}} \renewcommand{\k}{{\mathbf{k}}} \newcommand{\n}{{\mathbf{n}}} \newcommand{\ttt}{{\mathbf{t}}} \newcommand{\vv}{{\mathbf{v}}} \newcommand{\bv}{{\mathbf{v}}} \newcommand{\w}{{\mathbf{w}}} \newcommand{\x}{{\mathbf{x}}} \newcommand{\cc}{{\mathbf{c}}} \newcommand{\zero}{{\mathbf{0}}} \newcommand{\one}{{\mathbf{1}}} \newcommand{\bdelta}{{\boldsymbol{\delta}}} \newcommand{\bpi}{{\bm{\pi}}} \newcommand{\B}{{\rm\bm{B}}} \newcommand{\C}{{\mathbb C}} \newcommand{\Z}{{\mathbb Z}} \newcommand{\N}{{\mathbb N}} \newcommand{\Q}{{\mathbb Q}} \newcommand{\R}{{\mathbb R}} \newcommand{\RR}{{\mathbb R}} % % Variants of \binom (defined using the AMS "genfrac" command) % \newcommand{\stirlingsubset}[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}} % Array for subscripts \newenvironment{sarray}{ \textfont0=\scriptfont0 \scriptfont0=\scriptscriptfont0 \textfont1=\scriptfont1 \scriptfont1=\scriptscriptfont1 \textfont2=\scriptfont2 \scriptfont2=\scriptscriptfont2 \textfont3=\scriptfont3 \scriptfont3=\scriptscriptfont3 \renewcommand{\arraystretch}{0.7} \begin{array}{l}}{\end{array}} \newenvironment{scarray}{ \textfont0=\scriptfont0 \scriptfont0=\scriptscriptfont0 \textfont1=\scriptfont1 \scriptfont1=\scriptscriptfont1 \textfont2=\scriptfont2 \scriptfont2=\scriptscriptfont2 \textfont3=\scriptfont3 \scriptfont3=\scriptscriptfont3 \renewcommand{\arraystretch}{0.7} \begin{array}{c}}{\end{array}} \oddsidemargin 0.25in \evensidemargin 0.25in \textwidth 6.0in \topmargin -0.2in \headsep 0.2in \textheight 9.0in \footnotesep 14pt \floatsep 28pt plus 2pt minus 4pt % Nominal is double what is in art12.sty \textfloatsep 40pt plus 2pt minus 4pt \intextsep 28pt plus 4pt minus 4pt \def\doublespace{ \renewcommand{\baselinestretch}{1.7} \large\normalsize } \def\singlespace{ \renewcommand{\baselinestretch}{1} \large\normalsize } % The \large\normalsize forces the new \baselineskip to take effect. \begin{document} \newbox\Adr \setbox\Adr\vbox{ \centerline{\sc Alexander D.~Scott} \vskip12pt \centerline{Mathematical Institute, University of Oxford} \centerline{24--29 St.~Giles, Oxford OX1 3LB, England.} \centerline{E-mail: {\tt\footnotesize scott@maths.ox.ac.uk}} \vskip22pt \centerline{\sc Alan D.~Sokal$^\dagger$} \vskip12pt \centerline{Department of Physics, New York University} \centerline{4 Washington Place, New York, NY 10003 USA.} \centerline{E-mail: {\tt\footnotesize sokal@nyu.edu}} } \title[Some variants of the exponential formula] {Some variants of the exponential formula, \\ with application to the multivariate Tutte polynomial (alias Potts model)} \author[Alexander D. Scott and Alan D. Sokal]{\box\Adr} %\author{ % \\[-5mm] % {\small Alexander D.~Scott} \\[-2mm] % {\small\it Mathematical Institute} \\[-2mm] % {\small\it University of Oxford} \\[-2mm] % {\small\it 24--29 St.~Giles}\/ \\[-2mm] % {\small\it Oxford OX1 3LB, England} \\[-2mm] % {\small\tt scott@maths.ox.ac.uk} \\[5mm] % {\small Alan D.~Sokal\thanks{Also at Department of Mathematics, % University College London, London WC1E 6BT, England.}} \\[-2mm] % {\small\it Department of Physics} \\[-2mm] % {\small\it New York University} \\[-2mm] % {\small\it 4 Washington Place} \\[-2mm] % {\small\it New York, NY 10003 USA} \\[-2mm] % {\small\tt sokal@nyu.edu} \\[-2mm] % {\protect\makebox[5in]{\quad}} % To force authors' names to be written % vertically, one above another. % (\author seems to put them side-by-side % if there is room.) %\date{\today????????????} %% REMEMBER TO PUT FINAL DATE HERE!!!!! %\date{February 24, 2008 \\[1mm] revised February 4, 2009 \\[1cm] \date{} \dedicatory{Dedicated to the memory of Pierre Leroux} %\thispagestyle{empty} % Suppress page number on front page. \thanks{$^\dagger$ Also at Department of Mathematics, University College London, London WC1E 6BT, England.} \keywords {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\"obius inversion, partition lattice.} \subjclass [2000]{05A19 (Primary); 05A15, 05A18, 05C15, 05C30, 05C99, 06A07, 82B20 (Secondary).} \begin{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\"obius inversion on the partition lattice. \end{abstract} \maketitle %First page headline in LaTeX for S\'eminaire Lotharingien de Combinatoire %--first part \thispagestyle{myheadings} \font\rms=cmr8 \font\its=cmti8 \font\bfs=cmbx8 \markright{\its S\'eminaire Lotharingien de Combinatoire \bfs 61A \rms (2009), Article~B61Ae\hfill} \def\thepage{} \section{Introduction} \label{sec1} Let $\{c_n\}_{n=1}^\infty$ be a sequence of coefficients, and let \begin{equation} C(x) \;=\; \sum_{n=1}^\infty c_n \, {\frac {x^n } { n!}} \label{eq1.1} \end{equation} be the corresponding exponential generating function, considered as a formal power series in the indeterminate $x$. Now let $q$ be another (commuting) indeterminate\footnote{ Let 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 \cite{Potts_52,Wu_82,Wu_84} and of the multivariate Tutte polynomial \cite{Sokal_bcc2005}. }, and define \begin{equation} A_q(x) \;=\; \exp[q C(x)] \;=\; \sum_{n=0}^\infty a_n(q) \, {\frac {x^n } { n!}} \;, \label{eq1.2} \end{equation} so that $A_q(x) = A(x)^q$ [we write $A(x) = A_1(x)$]. It is easy to see that: \begin{itemize} \item[(a)] Each coefficient $a_n(q)$ is a polynomial in $q$, of degree at most $n$; indeed we have the explicit formula\footnote{ This formula holds also for $n=0$ because the integer 0 has exactly one ordered partition $(n_1,\ldots,n_\ell)$ into zero or more strictly positive parts: namely, we have $\ell=0$ parts, and the multinomial coefficient and the empty product both equal 1, correctly giving $a_0(q) = 1$. } \begin{equation} a_n(q) \;=\; \sum_{\ell=0}^n {\frac {q^\ell } { \ell!}} \sum_{\begin{scarray} n_1,\ldots,n_\ell \ge 1 \\ \sum n_j = n \end{scarray} } {\binom {n } { n_1,\ldots,n_\ell}} \prod_{j=1}^\ell c_{n_j} \;. \label{eq.partition.an.cn} \end{equation} \item[(b)] $a_0(q)=1$. \item[(c)] For $n \neq 0$, the polynomial $a_n(q)$ has zero constant term, so that we can write $a_n(q) = q \ahat_n(q)$ where $\ahat_n(q)$ is a polynomial of degree at most $n-1$; moreover we have $\ahat_n(0) = c_n$. \end{itemize} %First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire %--restoring the headers and pagenumbering \pagenumbering{arabic} \addtocounter{page}{1} \markboth{\SMALL ALEXANDER D. SCOTT AND ALAN D. SOKAL}{\SMALL SOME VARIANTS OF THE EXPONENTIAL FORMULA} % % For some purposes it is convenient to introduce the modified generating function \begin{equation} \widehat{A}_q(x) \;=\; {\frac {A_q(x) \,-\, 1 } { q}} \;=\; {\frac {\exp[q C(x)] \,-\, 1 } { q}} \;=\; \sum_{n=1}^\infty \ahat_n(q) \, {\frac {x^n } { n!}} \;. \label{eq1.2.hat} \end{equation} The coefficients $\{a_n(q)\}_{n=0}^\infty$ furthermore satisfy the following identities \cite{Gould_74}:\footnote{ See Gould \cite{Gould_74} for fascinating comments on the history of identities equivalent to \reff{eq.id2} [or to \reff{eq.recursion.anq1.anq2} below], which apparently go back to Euler (1748), Rothe (1793), Hindenburg (1796), von Ettingshausen (1826) and Hanstead (1881), among others. } \begin{eqnarray} \sum_{k=0}^n {\binom {n } { k}} \, a_k(q_1) \, a_{n-k}(q_2) & = & a_n(q_1 + q_2) \label{eq.id1} \\[2mm] \sum_{k=1}^n {\binom {n } { k}} \, k \, \ahat_k(q_1) \, a_{n-k}(q_2) & = & n \, \ahat_n(q_1 + q_2) \qquad\hbox{for } n \ge 1 \qquad \label{eq.id2} \end{eqnarray} Indeed, \reff{eq.id1} follows from writing the trivial identity \begin{equation} A_{q_1}(x) A_{q_2}(x) \;=\; A_{q_1+q_2}(x) \end{equation} and extracting the coefficient of $x^n$, while \reff{eq.id2} follows analogously from \begin{equation} A_{q_2}(x) \left[ x {\frac {d } { dx}} \, {\frac {A_{q_1}(x) \,-\, 1 } { q_1}} \right] \;\:=\;\: x {\frac {d } { dx}} \, {\frac {A_{q_1+q_2}(x) \,-\, 1 } { q_1 + q_2}} \end{equation} \hspace*{-2mm} \cite[eq.~(4.3)]{Gould_74}, which is an easy consequence of \reff{eq1.2}. Specializing \reff{eq.id2} to $q_1 = 0$, or alternatively applying %% $x \, d/dx$ $x {\frac {\displaystyle d } { \displaystyle dx_{\vphantom{1}}}}$ directly to \reff{eq1.2}, we obtain the well-known recursion relation \cite[Theorem~3.10.1]{Wilf_94} \begin{equation} a_n(q) \;=\; q \sum_{k=1}^n {\binom {n-1 } { k-1}} \, c_k \, a_{n-k}(q) \qquad\hbox{for } n \ge 1 \;, \label{eq.recursion.an.cn} \end{equation} 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 \times \hbox{\reff{eq.id1}} - (q_1+q_2) \times \hbox{\reff{eq.id2}}$ to obtain the recursion relation\footnote{ See \cite[eq.~(1.3)]{Gould_74} or \cite[Exercise~1.39, pp.~50 and 62]{Stanley_86} for the case $q_1 = 1$, which is of course trivially equivalent to the general case of $q_1 \neq 0$. } \begin{subeqnarray} a_n(q_2) & = & \sum_{k=1}^n \left[ {\binom {n-1 } { k-1}} (q_1+q_2) \,-\, {\binom {n } { k}} q_1 \right] \ahat_k(q_1) \, a_{n-k}(q_2) \\[2mm] & = & \sum_{k=1}^n \left[ {\binom {n-1 } { k-1}} q_2 \,-\, {\binom {n-1 } { k}} q_1 \right] \ahat_k(q_1) \, a_{n-k}(q_2) \label{eq.recursion.anq1.anq2} \end{subeqnarray} for $n \ge 1$, which allows the $\{a_n(q_2)\}$ to be calculated given the $\{\ahat_n(q_1)\}$ for any fixed $q_1$, and which reduces to \reff{eq.recursion.an.cn} when $q_1 = 0$. We do not know whether there exist useful analogues of \reff{eq.id1}/\reff{eq.id2} with higher powers of $k$ on the left-hand side. Combinatorially, all these identities are versions of the {\em exponential formula}\/ \cite{Uhlenbeck_62,Foata_70,Foata_74,Wilf_94,Bergeron_98,Stanley_99}, 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.\footnote{ In the {\em theory of combinatorial species}\/ \cite{Bergeron_98}, the exponential formula is merely a special case of the more general concept of {\em composition}\/ (or {\em substitution}\/) {\em of species}\/ $F \circ G$ \cite[Section~1.4]{Bergeron_98}, which is defined so that the exponential generating function of $F \circ G$ is the composition of the exponential generating functions of $F$ and $G$. When $F$ is taken to be the species $E$ of sets ({\em 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 \circ 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 \cite{Labelle_96} for results closely related to those of the present paper, formulated in the language of species. } %% [cf.\ \reff{eq.partition.an.cn}]. This idea can be formalized in the following combinatorial model: Let $\Pi_n$ be the set of partitions of $[n] \equiv \{1,\ldots,n\}$ into (zero or more) nonempty blocks; give a partition $\pi = \{\pi_1,\ldots,\pi_\ell\}$ a weight $w(\pi) = q^\ell \prod\limits_{i=1}^\ell c_{|\pi_i|}$, where $\{c_k\}_{k=1}^\infty$ are arbitrary coefficients\footnote{ The 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''. }; and let $a_n(q) = \sum\limits_{\pi \in \Pi_n} w(\pi)$. Then \reff{eq.partition.an.cn} is immediate: the multinomial coefficient counts the {\em ordered}\/ partitions of $[n]$ into blocks of sizes $n_1,\ldots,n_\ell$, and the $1/\ell!$ converts this to {\em unordered}\/ partitions. As for \reff{eq.id1}/\reff{eq.id2}, 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 \reff{eq.id1} follows by defining $S \subseteq [n]$ to be the set of elements colored ``1'', and setting $k = |S|$. Analogously, $\ahat_n(q_1+q_2)$ can be computed by coloring and weighting blocks as before, except that the block containing one specified element $i \in [n]$ (say, $i=1$) must be colored ``1'' and it receives weight 1 instead of weight $q_1$. Defining again $S \subseteq [n]$ to be the set of elements colored ``1'', and setting $k = |S|$, we obtain \reff{eq.id2} in the form\footnote{ See also \cite[Theorem~2.9]{Reiner_77}; and see \cite[p.~188, Exercise~3.1.20(a)]{Bergeron_98} for the special case $q_1 = 1$. %% {\bf Can \reff{eq.id2} or \reff{eq.id2.bis} be found anywhere %% in the papers of Rota and collaborators??? %% I haven't found it thus far!} } \begin{equation} \ahat_n(q_1 + q_2) \;=\; \sum_{k=1}^n {\binom {n-1 } { k-1}} \, \ahat_k(q_1) \, a_{n-k}(q_2) \qquad\hbox{for } n \ge 1 \;. \label{eq.id2.bis} \end{equation} % {\bf We should search the literature and find where these are known % in the one-dimensional case. In particular, are the $q_1$--$q_2$ % versions of the ``partition identities'' % [i.e.\ \reff{eq.partition2bis.q1.q2}/\reff{eq.partition2bis.q1hat.q2}] % known even in the one-dimensional case??? % We could ask Wilf or Stanley or Leroux.} Sequences of polynomials $\{a_n(q)\}$ satisfying \reff{eq1.2} [or equivalently satisfying \reff{eq.id1} and not identically zero] have been termed {\em sequences of binomial type}\/ by Rota and collaborators \cite{Mullin_70,Rota_73,Garsia_73,Fillmore_73,Roman_78,Roman_84} and studied by means of the umbral calculus \cite{Roman_84,Rota_94,Gessel_03}.\footnote{ It is not hard to see by induction that if $\{a_n(q)\}$ satisfies \reff{eq.id1} [or even the special case of \reff{eq.id1} with $q_1 = q_2$] and is not identically zero, then $\deg a_n \le n$ with $a_0 = 1$ and $a_n(0) = 0$ for $n \ge 1$; moreover, with a little extra work it can be shown that $A_q(x)$ is necessarily of the form \reff{eq1.2}: see \cite[Theorem~4.1]{Garsia_73} \cite{Knuth_92,Zeng_96} \cite[Exercise~5.37, pp.~87--88 and 131--132]{Stanley_99}. Let us also remark that Rota {\em et al.}\/ \cite{Mullin_70,Rota_73} and many subsequent authors \cite{Garsia_73,Fillmore_73,Roman_78,Roman_84}, in defining ``sequence of binomial type'', impose the additional condition that $\deg a_n = n$ exactly (i.e., $c_1 \neq 0$); but since this condition is irrelevant for our purposes, we prefer not to impose it. } The corresponding sequences $\{a_n(q)/n!\}$ have been termed sequences of binomial type by Labelle \cite{Labelle_80} and {\em convolution families}\/ by Knuth \cite{Knuth_92} and Zeng \cite{Zeng_96}; 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 \cite{Labelle_81} (see also \cite[Section~3.1]{Bergeron_98}). Further identities, generalizing \reff{eq.id1}/\reff{eq.id2}, can be obtained by a powerful transformation suggested by Knuth \cite{Knuth_92}. 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 \reff{eq1.2}. Now let $t$ be a parameter, and define a formal power series $A(x;t)$ by the implicit equation \begin{equation} A(x;t) \;=\; A\bigl( x A(x;t)^t \bigr) \;. \label{eq.Axt.knuth} \end{equation} Since $A(x;0) = A(x)$, we can view the family $\{A(x;t)\}_{t \in \R}$ as a special class of ``perturbations'' of $A(x)$. Now define polynomials $\{a_n(q;t)\}$ by the obvious formula \begin{equation} A(x;t)^q \;=\; \sum_{n=0}^\infty a_n(q;t) \, {\frac {x^n } { n!}} \;. \label{eq1.2.t} \end{equation} For each $t$, these polynomials form a family of the type \reff{eq1.2} and thus satisfy the identities \reff{eq.id1}/\reff{eq.id2}. On the other hand, a straightforward calculation using the Lagrange inversion formula \cite{Stanley_99} yields the remarkable relation\footnote{ See \cite[Exercises~5.37(e) and 5.58, pp.~87--88, 99, 131--133 and 148]{Stanley_99}, 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) = x A(x;t)^t$, then $f$ and $g$ are compositional inverses (as observed in \cite{Labelle_80,Knuth_92} for $t=1$). } \begin{equation} a_n(q;t) \;=\; {\frac {q } { q+nt}} \: a_n(q+nt) \;=\; q \, \ahat_n(q+nt) \;, \label{eq.anqt} \end{equation} or even more simply \begin{equation} \ahat_n(q;t) \;=\; \ahat_n(q+nt) \;. \end{equation} [In particular, $a_n(q;t)$ and $\ahat_n(q;t)$ are {\em polynomials}\/ jointly in $q$ and $t$, so we can treat $t$ as an indeterminate if we wish.] % {\bf Note that $c_n(t) \equiv \ahat_n(0;t) = \ahat(nt) = \sum \ldots$ --- % can we find a combinatorial interpretation of the $t$-perturbed system??? % Note also that the map $U_t \colon\, \R[[x]] \to \R[[x]]$ % taking $A(x) \mapsto A(x;t)$ is a one-parameter group --- % generalize??? Find the differential equation for this % one-parameter group!!! In the general case, the parameter $t$ % can be any element of the coefficient ring $R$ % (which includes the case of being an indeterminate).} It follows that, for any family $\{a_n(q)\}$ of type \reff{eq1.2}, we have the following identities generalizing \reff{eq.id1}/\reff{eq.id2}:\footnote{ Already Rota {\em et al.}\/ \cite[p.~711, Proposition~4]{Rota_73} and Reiner \cite[Theorem~2.10]{Reiner_77} noticed that, for any $t$, the family $\{a_n(q;t)\}$ defined by \reff{eq.anqt} is of type \reff{eq1.2}. %% {\bf Also Mullin--Rota \cite{Mullin_70}???} I DON'T SEE IT ANYWHERE. But they do not seem to have noticed the relation \reff{eq.Axt.knuth}, which to our knowledge goes back to Knuth \cite{Knuth_92}. %% {\bf Is that correct????? Check them carefully!!!} } \begin{eqnarray} \sum_{k=0}^n {\binom {n } { k}} \, q_1 \ahat_k(q_1+kt) \, q_2 \ahat_{n-k}(q_2+(n-k)t) & = & (q_1+q_2) \ahat_n(q_1 + q_2+nt) \label{eq.id1.t} \\[2mm] \sum_{k=1}^n {\binom {n } { k}} \, k \, \ahat_k(q_1+kt) \, q_2 \ahat_{n-k}(q_2+(n-k)t) & = & n \, \ahat_n(q_1 + q_2+nt) \qquad\hbox{for } n \ge 1 \nonumber \\[-4mm] \label{eq.id2.t} \end{eqnarray} where we understand that $q \ahat_0(q) = 1$. Multiplying \reff{eq.id2.t} by $t$ and summing it with \reff{eq.id1.t}, we obtain the alternate form \begin{equation} \sum_{k=0}^n {\binom {n } { k}} \, a_k(q_1+kt) \, q_2 \ahat_{n-k}(q_2+(n-k)t) \;=\; a_n(q_1 + q_2+nt) \;. \label{eq.id3.t} \end{equation} If in \reff{eq.id3.t} we interchange $k \leftrightarrow n-k$ and $q_1 \leftrightarrow q_2$ and then replace $q_2$ by $q_2 -nt$, we obtain the slightly simpler form \begin{equation} \sum_{k=0}^n {\binom {n } { k}} \, q_1 \ahat_k(q_1+kt) \, a_{n-k}(q_2-kt) \;=\; a_n(q_1 + q_2) \;. \label{eq.id4.t} \end{equation} A combinatorial proof and interpretation of \reff{eq.id1.t}/\reff{eq.id3.t} in terms of the theory of species has been given by Labelle \cite{Labelle_81}.\footnote{ See also \cite[p.~189, Exercise~3.1.22]{Bergeron_98} for a brief summary. } We call \reff{eq.id1.t}--\reff{eq.id4.t} {\em Abel-type extensions}\/ of \reff{eq.id1}/\reff{eq.id2} 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) \cite{Riordan_68,Strehl_92,Johnson_07}. These Abel-type formulae can alternatively be derived as immediate consequences of the Pfaff--Cauchy derivative identities (generalizations of Leibniz's rule for the $n$th derivative of the product of two functions) recently presented by Johnson \cite{Johnson_07}. Indeed, setting $v = A(x)^{q_1}$, $w = A(x)^{q_2}$, $\phi = A(x)^t$ in \cite[eq.~(1.1)]{Johnson_07} yields \reff{eq.id4.t}, while making the same substitution in \cite[eq.~(1.4)]{Johnson_07} yields \reff{eq.id1.t}. Some classical examples of families $\{a_n(q)\}$ and the corresponding identities \reff{eq.id1}/ \reff{eq.id2} and \reff{eq.id1.t}--\reff{eq.id4.t} are listed in Table~\ref{table1}. %% We think that this approach via families \reff{eq1.2} %% provides a unified view that illuminates the plethora of identities %% of Rothe--Pfaff--Abel--Cauchy--Schl\"afli--Hurwitz type. % {\bf For the multivariate versions, I think % \cite{Stam_87,Strehl_92,Zeng_96,Pitman_01,Pitman_02} may be relevant.} \begin{table}[t] \addtolength{\parskip}{-3mm} %% \begin{center} \hspace*{-1.2cm} \begin{tabular}{|c|c|c|c|} \hline $A(x)$ & $a_n(q)$ & \reff{eq.id1}/\reff{eq.id2} & \reff{eq.id1.t}--\reff{eq.id4.t} \\ \hline $e^x$ & $q^n$ & $\begin{array}{c} \hbox{\small binomial} \\[-1mm] \hbox{\small theorem} \end{array}$ & $\begin{array}{c} \hbox{\small Abel--Cauchy} \\[-1mm] \hbox{\small binomial} \\[-1mm] \hbox{\small identities} \end{array}$ \\[3mm] $\begin{array}{c} 1+x \\[3mm] (1-x)^{-1} \\[3mm] (1+\alpha x)^\beta \end{array}$ & $\left. \begin{array}{c} q^{\underline{n}} \\[3mm] q^{\overline{n}} \\[3mm] \alpha^n (\beta q)^{\underline{n}} \end{array} \!\right\}$ & $\begin{array}{c} \hbox{\small Chu--Vandermonde} \\[-1mm] \hbox{\small convolution} \end{array}$ & $\begin{array}{c} \hbox{\small Rothe's generalized} \\[-1mm] \hbox{\small Chu--Vandermonde} \\[-1mm] \hbox{\small convolution} \end{array}$ \\ & & & \\[-1mm] $\exp(e^x - 1)$ & $\begin{array}{c} B_n(q) \,=\, \sum\limits_{k=0}^n \stirlingsubset{n}{k} \, q^k \\[1mm] \hbox{\small (Bell polynomial \cite{Comtet_74})} \end{array}$ & %% \hbox{\small ?????????????} & %% \hbox{\small ?????????????} \\[9mm] $\exp[-x/(1-x)]$ & $\begin{array}{c} L_n^{(-1)}(q) \,=\, \sum\limits_{k=0}^n {\frac {n! } { k!}} \, {\binom {n-1 } { n-k}} \, (-q)^k \\[1mm] \hbox{\small (Laguerre polynomial \cite{Andrews_99})} \end{array}$ & %% \hbox{\small ?????????????} & %% \hbox{\small ?????????????} \\ \hline \end{tabular} \vskip10pt %%\end{center} \caption{ Some classical identities that are special cases of \reff{eq.id1}/\reff{eq.id2} and \reff{eq.id1.t}--\reff{eq.id4.t}. See \cite{Gould_56,Gould_57,Gould_66,Gould_74,Riordan_68,Strehl_92,% Johnson_07} for more information concerning Abel--Cauchy and Chu--Vandermonde--Rothe identities. The identity \reff{eq.id1} is well known for the Bell \cite[p.~136, eq.~3n]{Comtet_74} and Laguerre \cite[p.~192, eq.~41]{Bateman} \cite[p.~96, Problem~20]{Lebedev_65} polynomials. We do not know any references for \reff{eq.id2} or \reff{eq.id1.t}--\reff{eq.id4.t} in these cases. % but we would not be surprised to learn that they too are known. %% {\bf Is second Chu--Vandermonde identity just $\partial/\partial q_1$ %% of first??? I think not \ldots} % {\bf Need to search for identities for Bell polynomials % (also called Touchard polynomials) and % associated Laguerre polynomials!!!} } \label{table1} \addtolength{\parskip}{3mm} \end{table} \bigskip 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 \cite{Sokal_bcc2005} 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 \cite{Riordan_unpub,Nijenhuis_79,Kreweras_80} and in more general form by Leroux \cite{Leroux_88} and Gessel \cite{Gessel_95} and an identity for the inversion enumerator of trees found by Mallows, Riordan and Kreweras \cite{Mallows_68,Kreweras_80}. In the appendix we prove an apparently new generalization of M\"obius inversion on the partition lattice. 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. \section{Variants of the exponential formula} \label{sec2} Let $V$ be a finite ground set; we shall use multi-indices $\n = (n_i)_{i \in V} \in \N^V$ %% (where $\N = \{0,1,2,\ldots\}$) and commuting indeterminates $\x = (x_i)_{i \in V}$. We write $|\n| = \sum_{i \in V} n_i$ and $\x^\n = \prod_{i \in V} x_i^{n_i}$. We use the notation $\n! = \prod_{i \in V} n_i!$ and analogously for binomial and multinomial coefficients. Finally, we denote by $\zero$ (respectively\ $\one$) the multi-index with all entries 0 (respectively\ 1); and for any subset $W \subseteq V$, we denote by $\one_W$ the multi-index taking the value 1 on $W$ and 0 on $V \setminus 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 $\cc = (c_\n)_{\n \in \N^V \setminus \{\zero\}}$ as indeterminates, and to take $R$ to be the polynomial ring $\Q[\cc]$; 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 \in \N^V}$ be a sequence of coefficients in the ring $R$, with $c_\zero = 0$; and let \begin{equation} C(\x) \;=\; \sum_{\n} c_\n \, {\frac {\x^\n } { \n!}} \end{equation} 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 \begin{equation} A_q(\x) \;=\; \exp[q C(\x)] \;=\; \sum_{\n} a_\n(q) \, {\frac {\x^\n } { \n!}} \;. \label{def.Aq.multidim} \end{equation} Using the Taylor series for $\exp$, we deduce immediately that \begin{itemize} \item[(a)] Each coefficient $a_\n(q)$ is a polynomial in $q$, of degree at most $|\n|$; indeed we have the explicit formula\footnote{ This formula holds also for $\n = \zero$ because the multi-index $\zero$ has exactly one ordered partition $(\n_1,\ldots,\n_\ell)$ into zero or more nonvanishing parts: namely, we have $\ell=0$ parts, and the multinomial coefficient and the empty product both equal 1, correctly giving $a_\zero(q) = 1$. This same observation applies to all subsequent formulae of a similar type, such as \reff{eq.partition2.rq.q} ff. } \begin{equation} a_\n(q) \;=\; \sum_{\ell=0}^{|\n|} {\frac {q^\ell } { \ell!}} \sum_{\substack{ \n_1,\ldots,\n_\ell \neq \zero \\[0.7mm] \sum \n_j = \n } } {\binom {\n } { \n_1,\ldots,\n_\ell}} \prod_{j=1}^\ell c_{\n_j} \;. \label{eq.partition2.an.cn} \end{equation} \item[(b)] $a_\zero(q) = 1$. \item[(c)] For $\n \neq \zero$, the polynomial $a_\n(q)$ has zero constant term, so that we can write $a_\n(q) = q \ahat_\n(q)$ where $\ahat_\n(q)$ is a polynomial of degree at most $|\n|-1$; moreover we have $\ahat_\n(0) = c_\n$. \end{itemize} Conversely, it is not hard to see that if $(c_\n)_{\n \in \N^V \setminus \{\zero\}}$ is any sequence and we define $(a_\n(q))_{\n \in \N^V}$ by \reff{eq.partition2.an.cn}, then the latter family satisfies \reff{def.Aq.multidim}. Using $q C(\x) = \log A_q(\x)$ together with the Taylor series for $\log(1+z)$, we obtain the inverse formula \begin{equation} q c_\n \;=\; \sum_{\ell=1}^{|\n|} {\frac {(-1)^{\ell-1} } { \ell}} \sum_{\substack{ \n_1,\ldots,\n_\ell \neq \zero \\[0.7mm] \sum \n_j = \n } } {\binom {\n } { \n_1,\ldots,\n_\ell}} \prod_{j=1}^\ell a_{\n_j}(q) \label{eq.partition2.inverse.1} \end{equation} or equivalently \begin{equation} c_\n \;=\; \sum_{\ell=1}^{|\n|} {\frac {(-q)^{\ell-1} } { \ell}} \sum_{\substack{ \n_1,\ldots,\n_\ell \neq \zero \\[0.7mm] \sum \n_j = \n } } {\binom {\n } { \n_1,\ldots,\n_\ell}} \prod_{j=1}^\ell \ahat_{\n_j}(q) \;. \label{eq.partition2.inverse.2} \end{equation} % {\bf Note that the RHS is independent of $q$, % so we can write the identity saying that it is equal at $q_1$ and $q_2$. % What does this say??? Is it related to \reff{eq.id1}/\reff{eq.id2}???} It is a nontrivial fact that the right-hand side of \reff{eq.partition2.inverse.2} 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 \begin{equation} (1+z)^r \;\equiv\; \exp[r \log(1+z)] \;=\; \sum_{\ell=0}^\infty {\frac {r^{\underline{\ell}} } { \ell!}} \, z^\ell \label{eq.Taylor.power_r} \end{equation} where $r^{\underline{\ell}} = r (r-1) \cdots (r-\ell+1)$ denotes the falling factorial. (If we like, we can alternatively use the notation ${\binom {r } { \ell}} = r^{\underline{\ell}}/\ell!$, which is a well-defined polynomial in the indeterminate $r$.) We obtain \begin{equation} a_\n(rq) \;=\; \sum_{\ell=0}^{|\n|} {\frac {r^{\underline{\ell}} } { \ell!}} \sum_{\substack{ \n_1,\ldots,\n_\ell \neq \zero \\[0.7mm] \sum \n_j = \n } } {\binom {\n } { \n_1,\ldots,\n_\ell}} \prod_{j=1}^\ell a_{\n_j}(q) \;. \label{eq.partition2.rq.q} \end{equation} In view of the identity $(-r)^{\underline{\ell}} = (-1)^\ell r^{\overline{\ell}}$ where $r^{\overline{\ell}} = r (r+1) \cdots (r+\ell-1) = (r+\ell-1)^{\underline{\ell}}$ denotes the rising factorial, we also have \begin{equation} a_\n(-rq) \;=\; \sum_{\ell=0}^{|\n|} {\frac {(-1)^\ell r^{\overline{\ell}} } { \ell!}} \sum_{\substack{ \n_1,\ldots,\n_\ell \neq \zero \\[0.7mm] \sum \n_j = \n } } {\binom {\n } { \n_1,\ldots,\n_\ell}} \prod_{j=1}^\ell a_{\n_j}(q) \;. \label{eq.partition2.minusrq.q} \end{equation} Since both sides of the identities \reff{eq.partition2.rq.q}/\reff{eq.partition2.minusrq.q} 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 \reff{eq.partition2.rq.q} can obviously be restricted to $\ell \le r$. Slightly (but not much) less trivially, if $r$ is a positive integer, then by using \begin{equation} {\frac {r^{\overline{\ell}} } { \ell!}} \;=\; {\frac {(r+\ell-1)! } { \ell! \, (r-1)!}} \;=\; {\frac {(\ell+1)^{\overline{r-1}} } { (r-1)!}} \end{equation} we can rewrite \reff{eq.partition2.minusrq.q} as \begin{equation} a_\n(-rq) \;=\; \sum_{\ell=0}^{|\n|} (-1)^\ell {\frac {(\ell+1)^{\overline{r-1}} } { (r-1)!}} \sum_{\substack{ \n_1,\ldots,\n_\ell \neq \zero \\[0.7mm] \sum \n_j = \n } } {\binom {\n } { \n_1,\ldots,\n_\ell}} \prod_{j=1}^\ell a_{\n_j}(q) \;, \label{eq.partition2.minusrq.q.bis} \end{equation} in which the coefficient $(\ell+1)^{\overline{r-1}} / (r-1)!$ is a polynomial of degree $r-1$ in $\ell$. In particular, for $r=1$ we have \begin{equation} a_\n(-q) \;=\; \sum_{\ell=0}^{|\n|} (-1)^{\ell} \sum_{\substack{ \n_1,\ldots,\n_\ell \neq \zero \\[0.7mm] \sum \n_j = \n } } {\binom {\n } { \n_1,\ldots,\n_\ell}} \prod_{j=1}^\ell a_{\n_j}(q) \;. \label{eq.partition2bis.minusq} \end{equation} % Starting from the identity $A_{q_2}(\x) = A_{q_1}(\x)^{q_2/q_1}$ % and using the Taylor series for $(1+z)^{q_2/q_1}$, we obtain % \begin{equation} % a_\n(q_2) \;=\; % \sum_{\ell=0}^{|\n|} {\frac {(q_2/q_1)^{\underline{\ell}} } { \ell!}} % \sum_{\begin{scarray} % \n_1,\ldots,\n_\ell \neq \zero \\ % \sum \n_j = \n % \end{scarray} % } % {\binom {\n } { \n_1,\ldots,\n_\ell}} % \prod_{j=1}^\ell a_{\n_j}(q_1) % \label{eq.partition2.q1.q2} % \end{equation} % {\bf Don't use index $i$ for these partitions and also for elements of $V$ % --- use some other letter for one or the other!!! % Change also in Introduction.} % where $x^{\underline{\ell}} = x (x-1) \cdots (x-\ell+1)$ % denotes the falling factorial. % % % \begin{quote} % \small % {\bf But it's not so nice to write $q_2/q_1$ if $q_1$ is an indeterminate; % what is the algebraic status of these formulae??? % What is the cleanest way to state and prove them? % One possibility is to write $q_2 = r q_1$ where $r$ is another % indeterminate; since everything is a polynomial in $r$, % we can always specialize to $r$ integer or rational, % or more generally to $r$ being any element of the ring $R$. This gives} % Here ${\binom {r } { \ell}} = r^{\underline{\ell}}/\ell!$ is % a well-defined polynomial even if $r$ is an indeterminate. % And we can also use the identity % ${\binom {r } { \ell}} = (-1)^\ell {\binom {-r+\ell-1 } { \ell}}$ % to handle $r$ negative. % \end{quote} % % 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 \begin{equation} a_\n(q_2) \;=\; \sum_{\ell=0}^{|\n|} {\frac {1 } { \ell!}} \, \Biggl( \, \prod_{j=0}^{\ell-1} (q_2 - jq_1) \, \Biggr) \sum_{\substack{ \n_1,\ldots,\n_\ell \neq \zero \\[0.7mm] \sum \n_j = \n } } {\binom {\n } { \n_1,\ldots,\n_\ell}} \prod_{j=1}^\ell \ahat_{\n_j}(q_1) \;, \label{eq.partition2bis.q1.q2} \end{equation} which is nice because both sides are manifestly polynomials in the indeterminates $q_1$ and $q_2$. Alternatively, for $\n \neq \zero$ we can pull out the $j=0$ factor and write \begin{equation} \ahat_\n(q_2) \;=\; \sum_{\ell=1}^{|\n|} {\frac {1 } { \ell!}} \, \Biggl( \, \prod_{j=1}^{\ell-1} (q_2 - jq_1) \, \Biggr) \sum_{\substack{ \n_1,\ldots,\n_\ell \neq \zero \\[0.7mm] \sum \n_j = \n } } {\binom {\n } { \n_1,\ldots,\n_\ell}} \prod_{j=1}^\ell \ahat_{\n_j}(q_1) \;. \label{eq.partition2bis.q1hat.q2} \end{equation} Conversely, it is not hard to see that if $q_1$ is any element of the ring $R$ %% {\bf Is this generality for $q_1$ OK???} and $(\ahat_\n(q_1))_{\n \in \N^V}$ is any sequence, and we define $(a_\n(q))_{\n \in \N^V}$ by \reff{eq.partition2bis.q1.q2}, then the latter family satisfies \reff{def.Aq.multidim}. The following special cases of \reff{eq.partition2bis.q1.q2}/\reff{eq.partition2bis.q1hat.q2} are of particular interest: \begin{itemize} \item[(a)] For $q_1=0$, the identity \reff{eq.partition2bis.q1.q2} reduces to \reff{eq.partition2.an.cn}. \item[(b)] For $q_2=0$, we obtain the inverse formula \reff{eq.partition2.inverse.1}/\reff{eq.partition2.inverse.2}. \item[(c)] For $q_2 = -q_1$, we obtain the closely related formula \reff{eq.partition2bis.minusq}. \end{itemize} %% Are there any combinatorial reciprocity formulae relating %% positive $k$ to negative $k$??? It is easy to show that the coefficients $\{a_\n(q)\}_{\n \in \N^V}$ satisfy the identities \begin{eqnarray} \sum_{\k} {\binom {\n } { \k}} \, a_\k(q_1) \, a_{\n-\k}(q_2) & = & a_\n(q_1 + q_2) \label{eq.id1.multidim} \\[2mm] \sum_{\k \neq \zero} {\binom {\n } { \k}} \, k_i \, \ahat_\k(q_1) \, a_{\n-\k}(q_2) & = & n_i \, \ahat_\n(q_1 + q_2) \qquad\hbox{for } \n \neq \zero \qquad \label{eq.id2.multidim} \end{eqnarray} Indeed, \reff{eq.id1.multidim} 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 \reff{eq.id2.multidim} follows analogously from \begin{equation} A_{q_2}(\x) \left[ x_i {\frac {\partial } { \partial x_i}} \, {\frac {A_{q_1}(\x) \,-\, 1 } { q_1}} \right] \;\:=\;\: x_i {\frac {\partial } { \partial x_i}} \, {\frac {A_{q_1+q_2}(\x) \,-\, 1 } { q_1 + q_2}} \;, \end{equation} which is an easy consequence of \reff{def.Aq.multidim}. In particular, specializing \reff{eq.id2.multidim} to $q_1 = 0$, we obtain the recursion relation \begin{equation} a_\n(q) \;=\; q \sum_{\k \ge \bdelta_i} {\binom {\n-\bdelta_i } { \k-\bdelta_i}} \, c_\k \, a_{\n-\k}(q) \qquad\hbox{whenever } n_i \ge 1 \;, \qquad \label{eq.recursion.an.cn.multidim} \end{equation} which allows the $\{a_\n(q)\}$ to be calculated given the $\{c_\n\}$, or vice versa. [Here $\bdelta_i$ is the vector with entry 1 at element $i$ and 0 elsewhere.] More generally, we can form the linear combination $n_i \times \hbox{\reff{eq.id1.multidim}} - (q_1+q_2) \times \hbox{\reff{eq.id2.multidim}}$ to obtain the recursion relation \begin{equation} a_\n(q_2) \;=\; \sum_{\k \neq \zero} \left[ {\binom {\n-\bdelta_i } { \k-\bdelta_i}} (q_1+q_2) \,-\, {\binom {\n } { \k}} q_1 \right] \ahat_\k(q_1) \, a_{\n-\k}(q_2) \qquad\hbox{whenever } n_i \ge 1 \;, \label{eq.recursion.anq1.anq2.multidim} \end{equation} which allows the $\{a_\n(q_2)\}$ to be calculated given the $\{\ahat_\n(q_1)\}$ for any fixed $q_1$, and which reduces to \reff{eq.recursion.an.cn.multidim} when $q_1 = 0$. We do not know whether there exist useful analogues of \reff{eq.id1.multidim}/\reff{eq.id2.multidim} with higher powers of $\k$ on the left-hand side. Finally, we can deduce the Abel-type extensions of \reff{eq.id1.multidim}/\reff{eq.id2.multidim}: \begin{eqnarray} \sum_{\k} {\binom {\n } { \k}} \, q_1 \ahat_\k(q_1+ \k\cdot\ttt) \, q_2 \ahat_{\n-\k}(q_2+(\n-\k)\cdot\ttt) & = & (q_1+q_2) \ahat_\n(q_1 + q_2+\n\cdot\ttt) \nonumber \\[-4mm] \label{eq.id1.t.multidim} \\[2mm] \sum_{\k \neq \zero} {\binom {\n } { \k}} \, k_i \, \ahat_\k(q_1+\k\cdot\ttt) \, q_2 \ahat_{\n-\k}(q_2+(\n-\k)\cdot\ttt) & = & n_i \, \ahat_\n(q_1 + q_2+\n\cdot\ttt)\nonumber\\[-4mm] & &\kern3cm \quad\hbox{for } \n \neq \zero \nonumber \\ \label{eq.id2.t.multidim} \end{eqnarray} where $\ttt = (t_i)_{i \in V}$ are commuting indeterminates and we understand $q \ahat_\zero(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 \cite[pp.~225--226]{Zeng_96}. For further information on classical specializations of \reff{eq.id1.t.multidim}/\reff{eq.id2.t.multidim}, see \cite{Stam_87,Strehl_92,Zeng_96,Pitman_01,Pitman_02}. \begin{remark} We wonder whether \reff{eq.id1.t.multidim}/\reff{eq.id2.t.multidim} might have an extension to identities involving a not-necessarily-diagonal {\em matrix}\/ $T = (t_{ij})_{i,j \in V}$ of indeterminates, based on considering the implicit equation \begin{equation} e^{C({\bf x};T)} = A\bigl( e^{C({\bf x};T) T} {\bf x} \bigr) \;, \end{equation} which generalizes \reff{eq.Axt.knuth}. If true, this could be a powerful extension. See Strehl \cite{Strehl_92} for possibly related work in which a matrix of indeterminates is employed. \end{remark} \section{Application to the multivariate Tutte polynomial} \label{sec3} In this section we apply the formulae of Section~\ref{sec2} to deduce some identities for multivariate Tutte polynomials. \subsection{Definitions and basic properties} Let $G = (V,E)$ be a finite undirected graph with vertex set $V \neq \emptyset$ and edge set $E$; loops and multiple edges are allowed unless explicitly stated otherwise. Then the {\em multivariate Tutte polynomial}\/ \cite{Sokal_bcc2005} of $G$ is, by definition, the polynomial \begin{equation} Z_G(q, \bv) \;=\; \sum_{A \subseteq E} q^{k(A)} \prod_{e \in A} v_e \;, \label{def.ZG} \end{equation} where $q$ and $\bv = (v_e)_{e \in 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 \begin{equation} \Zhat_G(q, \bv) \;=\; \sum_{A \subseteq E} q^{k(A)-1} \prod_{e \in A} v_e \;; \label{def.ZhatG} \end{equation} this is still a polynomial since $k(A) \ge 1$ for all $A$. Finally, let us make the convention that if $G=\emptyset$ (the graph with empty vertex set and empty edge set), then $Z_\emptyset = 1$ and $\Zhat_\emptyset$ 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 \cite[Section~2.5]{Sokal_bcc2005}. Note that at $q=1$ we have the trivial formula \begin{equation} Z_G(1, \bv) \;=\; \Zhat_G(1, \bv) \;=\; \prod_{e \in E} (1+v_e) \;. \label{ZG.q=1} \end{equation} More interestingly, at $q=0$ we have the specialization \begin{equation} \Zhat_G(0, \bv) \;=\; C_G(\bv) \;\equiv\; \!\! \sum\limits_{\begin{scarray} A \subseteq E \\ k(A) = 1 \end{scarray}} \prod_{e \in A} v_e \;, \end{equation} i.e., the generating polynomial of connected spanning subgraphs of $G$. In statistical physics, $Z_G(q,\bv)$ is known as the partition function of the $q$-state Potts model \cite{Potts_52,Wu_82,Wu_84} in the Fortuin--Kasteleyn representation \cite{Kasteleyn_69,Fortuin_72,Grimmett_book_to_appear}. This arises by virtue of the following identity \cite{Kasteleyn_69,Fortuin_72}: \begin{theorem}[Fortuin--Kasteleyn representation of the Potts model \protect\cite{Kasteleyn_69,Fortuin_72}] \label{thm.FK} %%\hfill\break %%\vspace*{-0.4cm} %%\par\noindent For integer $q \ge 1$, we have \begin{equation} Z_G(q, \bv) \;=\; \sum_{ \sigma \colon\, V \to [q]} \; \prod_{e=ij \in E} \, \biggl[ 1 + v_e \delta\bigl(\sigma(i), \sigma(j)\bigr) \biggr] \label{eq.FK.identity} \end{equation} where $\delta$ denotes the Kronecker delta. \end{theorem} \begin{proof} On the right-hand side of \reff{eq.FK.identity}, expand out the product over $e \in E$, and let $A \subseteq E$ be the set of edges for which the term $v_e \delta\bigl(\sigma(i), \sigma(j)\bigr)$ is taken. Now perform the sum over maps $\sigma \colon\, V \to [q]$: in each connected component of the subgraph $(V,A)$ the ``color'' $\sigma(i)$ must be constant, and there are no other constraints. Therefore, the right-hand side equals \begin{equation} \sum_{ A \subseteq E } q^{k(A)} \prod_{e \in A} v_e \;, \end{equation} as was to be proved. \end{proof} Specializing to $v_e =-1$ for all edges $e$, we obtain the Birkhoff--Whitney \cite{Birkhoff_12,Whitney_32a} expansion for the chromatic polynomial of $G$: \begin{corollary} \label{cor.chrompoly} For integer $q \ge 1$, the number of proper $q$-colorings of $G$ is $P_G(q) \equiv Z_G(q,-1)$. \end{corollary} \subsection{Some generating functions} For the remainder of this section, let us assume that $G$ is a {\em 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 \in \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,\alpha)$ with $i \in V$ and $\alpha \in [n_i]$, and the edges of $G[\n]$ are all pairs $\< (i,\alpha), (j,\beta) \>$ with $ij \in E$, $\alpha \in [n_i]$ and $\beta \in [n_j]$. Given a set of weights $\bv = (v_e)_{e \in E}$ associated to the edges of $G$, we assign the weight $v_{ij}$ to each edge $\< (i,\alpha), (j,\beta) \>$ 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,\alpha), (i,\beta) \>$ with $i \in V$, $\alpha,\beta \in [n_i]$ and $\alpha \neq \beta$. Given a set of weights $\bv = (v_e)_{e \in E}$ associated to the edges of $G$ and another set of weights $\w = (w_i)_{i \in V}$ associated to the vertices of $G$, we assign the weight $v_{ij}$ to each edge $\< (i,\alpha), (j,\beta) \>$ ($i \neq j$) in $G'[\n]$ and the weight $w_i$ to each edge $\< (i,\alpha), (i,\beta) \>$ in $G'[\n]$. Note in particular that if $\n = \one_W$ for some subset $W \subseteq 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]$: \begin{theorem} \label{thm.Potts_genfn} Let $G=(V,E)$ be a simple graph, and let $\bv = (v_e)_{e \in E}$ and $\w = (w_i)_{i \in V}$ be indeterminates. We then have the following exponential generating functions: \begin{eqnarray} \sum_{\n} Z_{G[\n]}(q, \bv) \, {\frac {\x^\n } { \n!}} & = & \left( \sum_{\n} \, \Bigl( \prod_{ij \in E} (1+v_{ij})^{n_i n_j} \Bigr) \, {\frac {\x^\n } { \n!}} \right) ^{\! q} \label{eq.potts.genfn_1} \\[4mm] \sum_{\n} Z_{G'[\n]}(q, \bv, \w) \, {\frac {\x^\n } { \n!}} & = & \left( \sum_{\n} \, \Bigl( \prod_{ij \in E} (1+v_{ij})^{n_i n_j} \Bigr) \, \Bigl( \prod_{i \in V} (1+w_i)^{n_i (n_i-1)/2} \Bigr) \, {\frac {\x^\n } { \n!}} \right) ^{\! q} \nonumber \\ \label{eq.potts.genfn_2} \end{eqnarray} where all sums run over $\n \in \N^V$. \end{theorem} We remark that the expression in large parentheses on the right-hand side of \reff{eq.potts.genfn_1} [respectively\ \reff{eq.potts.genfn_2}] is the grand partition function for a lattice gas on the graph $G$ [respectively\ on the graph $G^\circ$ obtained from $G$ by adjoining a loop at each vertex] in which arbitrary nonnegative integer occupation numbers $\n = (n_i)_{i \in 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.\ \cite{Scott-Sokal_lovasz,Scott-Sokal_lovasz_shortpaper} for definitions concerning lattice gases. When $G=K_1$ (the graph with one vertex and no edges), \reff{eq.potts.genfn_2} reduces to the well-known \cite{Tutte_67,Biggs_93,Gessel_95,Gessel_96,Welsh_00} exponential generating function for the Tutte polynomials of the complete graphs $K_n$:\footnote{ Unfortunately, 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 \cite[Section~2.5]{Sokal_bcc2005} that obscures the very different roles played by $q$ and $v$. } \begin{equation} \sum_{n=0}^\infty Z_n(q,v) \, {\frac {x^n } { n!}} \;=\; \left( \sum_{n=0}^\infty (1+v)^{n(n-1)/2} \, {\frac {x^n } { n!}} \right) ^{\! q} \;. \label{eq.ZKn.genfn} \end{equation} When $G=K_2$, \reff{eq.potts.genfn_1} reduces to the exponential generating function for the Tutte polynomials of the complete bipartite graphs $K_{n_1,n_2}$, \begin{equation} \sum_{n_1,n_2=0}^\infty Z_{n_1,n_2}(q,v) \, {\frac {x^{n_1} } { {n_1}!}} \, {\frac {y^{n_2} } { {n_2}!}} \;=\; \left( \sum_{n_1,n_2=0}^\infty (1+v)^{n_1 n_2} \, {\frac {x^{n_1} } { {n_1}!}} \, {\frac {y^{n_2} } { {n_2}!}} \right) ^{\! q} \;, \label{eq.ZKn1n2.genfn} \end{equation} which in turn specializes for $v=-1$ to the well-known \cite[Exercise~5.6, pp.~73 and 107--108]{Stanley_99} exponential generating function for the chromatic polynomials of the complete bipartite graphs\footnote{ %% The formulae \reff{eq.ZKn1n2.genfn} and \reff{eq.PKn1n2.genfn} %% ought to be well known, but we have not succeeded in finding them %% anywhere in the literature. \reff{eq.PKn1n2.genfn} can alternatively be derived from the explicit expression \cite{Swenson_73} for $P_{K_{n_1,n_2}}(q)$ by using a well-known Stirling-number identity \cite[eq.~(7.49)]{Graham_94} together with the binomial formula. }, \begin{equation} \sum_{n_1,n_2=0}^\infty 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 \;. \label{eq.PKn1n2.genfn} \end{equation} More generally, when $G=K_r$, \reff{eq.potts.genfn_1} gives the exponential generating function for the Tutte polynomials of the complete $r$-partite graphs $K_{n_1,\ldots,n_r}$. Note also that if we only want to know $Z_{G[\n]}(q, \bv)$ for $\n \le \one$ --- that is, we want to know $Z_{G[W]}(q, \bv)$ for subsets $W \subseteq V$ --- then it suffices to get correct the terms $\n \le \one$ on the right-hand side of \reff{eq.potts.genfn_1}; all the other terms can be dropped or altered arbitrarily. It follows that \begin{equation} Z_{G[W]}(q, \bv) \;=\; [\x^{\one_W}] \left( \sum_{\n \le \one} \, \Bigl( \prod_{ij \in E} (1+v_{ij})^{n_i n_j} \Bigr) \, {\frac {\x^\n } { \n!}} \right) ^{\! q} \;. \label{eq.potts.genfn.nle1.1} \end{equation} Note that the expression in large parentheses is now the grand partition function for a lattice gas with {\em hard-core self-repulsion}\/, i.e., at most one atom can occupy each site. In the special case $\bv = -\one$, this becomes \begin{equation} P_{G[W]}(q) \;=\; [\x^{\one_W}] \, I_G(\x)^q \;, \label{eq.potts.genfn.nle1.2} \end{equation} where $I_G(\x)$ is the multivariate generating polynomial for {\em independent sets}\/ of vertices in $G$. The formula \reff{eq.potts.genfn.nle1.2} was found previously by Lass \cite[Proposition~3.1]{Lass_01}. Since the formula \reff{eq.potts.genfn_1} for $G[\n]$ is just a specialization of the formula \reff{eq.potts.genfn_2} for $G'[\n]$, obtained by taking $\w = \zero$, it suffices to prove the latter. \begin{proof}[First Proof of Theorem~\ref{thm.Potts_genfn}] Since the coefficient of $\x^\n$ on each side of \reff{eq.potts.genfn_2} 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~\ref{thm.FK}, for integer $q \ge 1$ we have \begin{subeqnarray} Z_{G'[\n]}(q, \bv, \w) & = & \sum_{ \sigma \colon\, V(G'[\n]) \to [q]} \;\, \prod_{rs \in E(G'[\n])} \, \biggl[ 1 + v_{rs} \delta\bigl(\sigma(r), \sigma(s)\bigr) \biggr] \\[4mm] & = & \! \sum_{ \sigma \colon\, V(G'[\n]) \to [q]} \; \Biggl(\, \prod_{ij \in E} \prod_{\begin{scarray} \alpha \in [n_i] \\ \beta \in [n_j] \end{scarray}} \biggl[ 1 + v_{ij} \delta\bigl(\sigma(i,\alpha), \sigma(j,\beta)\bigr) \biggr] \Biggr) \nonumber \\ & & \qquad\qquad \times\; \Biggl(\, \prod_{i \in V} \prod_{\begin{scarray} \alpha,\beta \in [n_i] \\ \alpha < \beta \end{scarray}} \biggl[ 1 + w_i \delta\bigl(\sigma(i,\alpha), \sigma(i,\beta)\bigr) \biggr] \Biggr) \qquad \slabel{eq.ZGn} \end{subeqnarray} Now, because of the symmetries in the construction of $G'[\n]$, the summand in \reff{eq.ZGn} depends only on the numbers $\{n_{i,\tau}\}_{i \in V, \, \tau \in [q]}$ defined by \begin{equation} n_{i,\tau} \;=\; \#\{\alpha \in [n_i] \colon\; \sigma(i,\alpha) = \tau \} \;, \end{equation} and we have \begin{eqnarray} Z_{G'[\n]}(q, \bv, \w) & = & \!\!\!\! \sum_{\begin{scarray} \{n_{i,\tau}\} \\ \sum_{\tau=1}^q n_{i,\tau} = n_i \, \forall i \end{scarray}} \left( \prod_{i \in V} {\binom {n_i } { n_{i,1}, \ldots, n_{i,q}}} \right) \left( \prod_{ij \in E} \, \prod_{\tau=1}^q (1+v_{ij})^{n_{i,\tau} n_{j,\tau}} \right) \nonumber \\ & & \qquad\qquad\qquad\times\; \left( \prod_{i \in V} \, \prod_{\tau=1}^q (1+w_i)^{n_{i,\tau} (n_{i,\tau}-1)/2} \right) \;. \end{eqnarray} Now multiply by $\x^\n/\n!$ and sum over $\n$; the sums over the $n_{i,\tau}$ now become unrestricted, and the sums for the different values of $\tau$ decouple; we end up with the product of $q$ terms each of which is \begin{equation} \sum_{\n} \, \Bigl( \prod_{ij \in E} (1+v_{ij})^{n_i n_j} \Bigr) \, \Bigl( \prod_{i \in V} (1+w_i)^{n_i (n_i-1)/2} \Bigr) \, {\frac {\x^\n } { \n!}} \;. \end{equation} \end{proof} It is instructive to give an alternate proof of Theorem~\ref{thm.Potts_genfn} in which $q$ is treated directly as an indeterminate: \begin{proof}[Second Proof of Theorem~\ref{thm.Potts_genfn}] We begin by proving the special case \reff{eq.ZKn.genfn}. {}From the binomial formula we have \begin{subeqnarray} \left( 1 \,+\, \sum_{n=1}^\infty (1+v)^{n(n-1)/2} \, {\frac {x^n } { n!}} \right) ^{\! q} & = & 1 \,+\, \sum_{b=1}^\infty {\frac {q^{\underline{b}} } { b!}} \left( \sum_{n=1}^\infty (1+v)^{n(n-1)/2} \, {\frac {x^n } { n!}} \right) ^{\! b} \\[2mm] & = & 1 \,+\, \sum_{b=1}^\infty {\frac {q^{\underline{b}} } { b!}} \sum_{n_1,\ldots,n_b \ge 1} {\frac {x^{\sum n_j} } { \prod n_j!}} \, \prod_{j=1}^b (1+v)^{n_j(n_j-1)/2} \;. \nonumber \\ \label{eq.secondproof.0} \end{subeqnarray} Now write $n = \sum_{j=1}^b n_j$, and consider $n_1,\ldots,n_b$ as the block sizes in an {\em ordered}\/ partition $\pi = (\pi_1,\ldots,\pi_b)$ of $[n]$ into $b$ nonempty blocks. The number of ordered partitions with those block sizes is precisely the multinomial coefficient $n! / \prod\limits_{j=1}^b n_j!$, so \reff{eq.secondproof.0} is equal to \begin{equation} 1 \,+\, \sum_{n=1}^\infty {\frac {x^n } { n!}} \sum_{\pi \in \Pi'_n} {\frac {q^{\underline{|\pi|}} } { |\pi|!}} \prod_{j=1}^{|\pi|} (1+v)^{|\pi_j| (|\pi_j|-1)/2} \;, \end{equation} where $\Pi'_n$ denotes the set of ordered partitions of $[n]$, and $|\pi|$ denotes the number of blocks in the partition $\pi$. Passing to {\em unordered}\/ partitions absorbs the factor $1/|\pi|!$ (as these are partitions of a {\em labelled}\/ set), and we get \begin{equation} 1 \,+\, \sum_{n=1}^\infty {\frac {x^n } { n!}} \sum_{\pi \in \Pi_n} q^{\underline{|\pi|}} \prod_{j=1}^{|\pi|} (1+v)^{|\pi_j| (|\pi_j|-1)/2} \;. \label{eq.secondproof.1} \end{equation} The factor $(1+v)^{|\pi_j| (|\pi_j|-1)/2}$ corresponds to a sum over (simple undirected) graphs on the vertex set $\pi_j$, with a weight $v$ for each edge. We can now reinterpret \reff{eq.secondproof.1} 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 $\pi \in \Pi_n$ that are {\em compatible}\/ with $H$ in the sense that each block of $\pi$ 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 $\stirlingsubset{r}{b}$ ways (where $\stirlingsubset{r}{b}$ is a Stirling number of the second kind); and it is well known \cite[eq.~(6.10)]{Graham_94} that \begin{equation} \sum_{b=1}^r \stirlingsubset{r}{b} \, q^{\underline{b}} \;=\; q^r \;. \label{eq.stirlingidentity} \end{equation} 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 \reff{eq.ZKn.genfn}. The more general formulae \reff{eq.potts.genfn_1}/\reff{eq.potts.genfn_2} are derived by a variant of this proof in which sums over integers $n \in \N \setminus \{0\}$ are replaced by sums over multi-indices $\n \in \N^V \setminus \{\zero\}$. 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 $\N^V$, and so we will be partitioning collections of objects of $|V|$ different types. We begin with some notation. Given $\n=(n_i)_{i\in V}\in\N^V$, we write $[\n]$ for the set of ordered pairs $\{(i,\alpha) \colon\, i\in V \hbox{ and } \alpha\in[n_i]\}$. Thus $|[\n]|=\sum_{i\in V}n_i$. We shall think of the subset $[\n]_i:=\{ (i,\alpha) \colon\, \alpha\in[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\in V$. Note that $G'[\n]$ is simply the complete graph on the vertex set $[\n]$. Now, given a partition $\bpi=(\bpi_1,\ldots,\bpi_k)$ of $[\n]$ (with all $\bpi_j$ nonempty), we write $|\bpi|=k$. The {\em block sizes}\/ $\B(\bpi_j)$ are elements of $\N^V\setminus\{\mathbf 0\}$ defined by \begin{equation} \B(\bpi_j) \;=\; (\bpi_j\cap[\n]_i)_{i\in V} \;. \end{equation} Thus $\B(\bpi_j)$ lists the number of objects of each type contained in the $j$th block of $\bpi$. % The {\em profile}\/ $\scrb(\bpi)$ of $\bpi$ is the ordered $k$-tuple % \begin{equation} % \scrb(\bpi) \;=\; (\B(\bpi_1),\ldots,\B(\bpi_k)) \;, % \end{equation} % which gives an ordered number partition of $\n$ corresponding to $\bpi$. Now let us define the weight \begin{equation} W(\n) \;:=\; \left(\prod_{ii'\in E}(1+v_{ii'})^{n_in_{i'}}\right) \left(\prod_{i\in V}(1+w_i)^{n_i(n_i-1)/2}\right) \;. \end{equation} The right-hand side of \reff{eq.potts.genfn_2} is then \begin{subeqnarray} \left(1+\sum_{\n\ne\mathbf0} W(\n)\frac{\x^{\n}}{\n!}\right)^q & = & 1 \,+\, \sum_{b\ge1}\frac{q^{\underline b}}{b!} \left(\sum_{\n\ne\mathbf0}W(\n)\frac{\x^{\n}}{\n!}\right)^b \\ & = & 1 \,+\, \sum_{b\ge1}\frac{q^{\underline b}}{b!} \sum_{\n_1,\ldots,\n_b\ne\mathbf0} \frac{\x^{\sum\n_j}}{\prod \n_j!} \prod_{j=1}^b W(\n_j) \;. \label{insertA} \end{subeqnarray} Now let $\n=\sum_{j=1}^b\n_j$, and consider $\n_1,\ldots,\n_b$ as the block sizes in an ordered partition $\bpi$ of $[\n]$ into $b$ nonempty blocks. The number of ordered partitions with those block sizes is the (multidimensional) multinomial coefficient $\n! / \prod\limits_{j=1}^b \n_j!$, so \reff{insertA} is equal to \begin{equation} 1 \,+\, \sum_{\n\ne\mathbf0}\frac{\x^\n}{\n!} \sum_\bpi\frac{q^{\underline{|\bpi|}}}{|\bpi|!} \prod_{j=1}^{|\bpi|}W(\B(\bpi_j)) \;, \end{equation} where the second sum is over ordered partitions of $[\n]$. Passing to {\em unordered}\/ partitions, this becomes \begin{equation} \label{insertB} 1 \,+\, \sum_{\n\ne\mathbf0}\frac{\x^\n}{\n!}\sum_\bpi q^{\underline{|\bpi|}} \prod_{j=1}^{|\bpi|}W(\B(\bpi_j)) \;. \end{equation} The factor $W(\B(\bpi_j))$ corresponds to a sum over graphs with vertex set $\bpi_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 \reff{insertB} as a sum over graphs $H$ with vertex set $[\n]$, with these same edge weights. The final step of the argument --- summing over partitions $\bpi$ 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. \end{proof} \subsection{Consequences for \mbox{\boldmath$Z_G(q,v)$}} In view of Theorem~\ref{thm.Potts_genfn}, we can apply all the results of Section~\ref{sec2} with the identifications \begin{subeqnarray} a_{\n}(q) & = & Z_{G'[\n]}(q,\bv,\w) \\[2mm] \ahat_{\n}(q) & = & \Zhat_{G'[\n]}(q,\bv,\w) \\[2mm] c_{\n} & = & C_{G'[\n]}(\bv,\w) \\[2mm] a_{\n}(1) & = & \left( \prod_{ij \in E} (1+v_{ij})^{n_i n_j} \right) \left( \prod_{i \in V} (1+w_i)^{n_i (n_i-1)/2} \right) \label{eq.complete.ident} \end{subeqnarray} We refrain from writing out all the formulae, which are obtained by substituting (\ref{eq.complete.ident}a--d) into \reff{eq.partition2.an.cn}, \reff{eq.partition2.inverse.1}/\reff{eq.partition2.inverse.2}, \reff{eq.partition2.rq.q}--\reff{eq.partition2bis.q1hat.q2}, \reff{eq.id1.multidim}, \reff{eq.id2.multidim}, \reff{eq.recursion.an.cn.multidim}, \reff{eq.recursion.anq1.anq2.multidim}, \reff{eq.id1.t.multidim} and \reff{eq.id2.t.multidim}. Let us simply show a few important results that arise from the partition formula \reff{eq.partition2.rq.q}/\reff{eq.partition2bis.q1.q2} and from the convolution formula \reff{eq.id1.multidim}--\reff{eq.id2.multidim}. \subsubsection{Partition formulae} \label{subsubsec.partitions} By specializing \reff{eq.partition2.rq.q}/\reff{eq.partition2bis.q1.q2} to $\n = \one$, 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 {\em arbitrary}\/ choices of $q_1$ and $q_2$: \begin{proposition} \label{prop.ZG.partitions.q1q2} Let $G=(V,E)$ be a finite loopless graph. Then \begin{equation} Z_G(q_2, \bv) \;=\; \sum\limits_{\pi \in \Pi(V)} (q_2/q_1)^{\underline{|\pi|}} \, \prod_{B\in \pi} \, Z_{G[B]}(q_1,\bv) \;, \label{eq.prop.ZG.partitions.q1q2} \end{equation} where the sum runs over (unordered) partitions $\pi$ of the vertex set $V$, the product runs over blocks $B$ of $\pi$, and $G[B]$ denotes the induced subgraph of $G$ on the vertex set $B$.\footnote{ Readers who dislike dividing by indeterminates can reinterpret this formula by writing $r = q_2/q_1$ and hence $q_2 = rq_1$, as in \reff{eq.partition2.rq.q}. } Equivalently we can write \begin{equation} Z_G(q_2, \bv) \;=\; \sum\limits_{\pi \in \Pi(V)} \, \Biggl( \, \prod_{j=0}^{|\pi|-1} (q_2 - jq_1) \, \Biggr) \, \prod_{B\in \pi} \, \Zhat_{G[B]}(q_1,\bv) \label{eq.prop.ZG.partitions.q1q2.alt} \end{equation} or \begin{equation} \Zhat_G(q_2, \bv) \;=\; \sum\limits_{\pi \in \Pi(V)} \, \Biggl( \, \prod_{j=1}^{|\pi|-1} (q_2 - jq_1) \, \Biggr) \, \prod_{B\in \pi} \, \Zhat_{G[B]}(q_1,\bv) \;. \label{eq.prop.ZG.partitions.q1q2.alt2} \end{equation} \end{proposition} \begin{proof} Specializing \reff{eq.partition2.rq.q} [or equivalently \reff{eq.partition2bis.q1.q2}] to $\n = \one$, we obtain a sum over ordered partitions $\pi = (\pi_1,\ldots,\pi_\ell)$ of $V$ into $\ell$ nonempty blocks. Passing from ordered to unordered partitions, we get a factor $\ell!$ that cancels the $1/\ell!$ in \reff{eq.partition2.rq.q}/\reff{eq.partition2bis.q1.q2}. \end{proof} Proposition~\ref{prop.ZG.partitions.q1q2} is very powerful because we are free to choose $q_1$ as we please; then $Z_G(q_2, \bv)$ can be written in terms of $Z_{G[B]}(q_1,\bv)$. The two most important special cases are $q_1 = 0$ and $q_1 = 1$.\footnote{ The case $q_1 = -1$ is also of interest, as it is related to acyclic orientations. See Lass \cite{Lass_01} for some interesting material that may be relevant in the present context. } \medskip {\bf Case \mbox{\boldmath$q_1=0$}.} Taking the limit $q_1 \to 0$ in \reff{eq.prop.ZG.partitions.q1q2}, or equivalently just setting $q_1 = 0$ in \reff{eq.prop.ZG.partitions.q1q2.alt}, we obtain \begin{equation} Z_G(q, \bv) \;=\; \sum\limits_{\pi \in \Pi(V)} q^{|\pi|} \, \prod_{B\in \pi} \, C_{G[B]}(\bv) \;. \label{eq.prop.ZG.partitions.0} \end{equation} % where the sum runs over (unordered) partitions $\pi$ of the vertex set $V$ % and the product runs over blocks $B$ of $\pi$; % here $G[B]$ denotes the induced subgraph of $G$ on the vertex set $B$. % The identity \reff{eq.prop.ZG.partitions.0} % can be proven by specializing \reff{eq.partition2.an.cn} to $\n = \one$, % which yields a sum over ordered partitions $\pi = (\pi_1,\ldots,\pi_\ell)$ % of $V$ into $\ell$ nonempty blocks; % passing from ordered to unordered partitions % provides a factor $\ell!$ that cancels the $1/\ell!$ % in \reff{eq.partition2.an.cn}. [This formula can alternatively be derived from \reff{eq.partition2.an.cn} by the same reasoning as used in proving Proposition~\ref{prop.ZG.partitions.q1q2}.] Of course, \reff{eq.prop.ZG.partitions.0} also has an obvious direct combinatorial proof, based on the definition \reff{def.ZG}: first we classify subsets $A \subseteq E$ according to the partition $\pi$ 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. \medskip {\bf Case \mbox{\boldmath$q_1=1$}.} This special case is slightly less obvious, and it is worth stating it explicitly: \begin{corollary} \label{cor0.ZG.partitions} Let $G=(V,E)$ be a finite loopless graph. Then \begin{eqnarray} Z_G(q, \bv) & = & \sum\limits_{\pi \in \Pi(V)} q^{\underline{|\pi|}} \, \prod_{B\in \pi} \, \prod_{e \in E(G[B])} (1+v_e) \label{eq.prop.ZG.partitions.1} \end{eqnarray} where the sum runs over (unordered) partitions $\pi$ of the vertex set $V$, the outermost product runs over blocks $B$ of $\pi$, and the innermost product runs over edges in the induced subgraph $G[B]$. %% here $q^{\underline{\ell}} = q(q-1) \cdots (q-\ell+1)$ %% and $G[B]$ denotes the induced subgraph. In particular, \begin{eqnarray} C_G(\bv) & = & \sum\limits_{\pi \in \Pi(V)} (-1)^{|\pi|-1} \: (|\pi| -1)! \, \prod_{B\in \pi} \, \prod_{e \in E(G[B])} (1+v_e) \label{eq.prop.ZG.partitions.2} \\[2mm] Z_G(-1, \bv) & = & \sum\limits_{\pi \in \Pi(V)} (-1)^{|\pi|} \: |\pi|! \, \prod_{B\in \pi} \, \prod_{e \in E(G[B])} (1+v_e) \label{eq.prop.ZG.partitions.3} \end{eqnarray} where $|\pi|$ denotes the number of blocks in $\pi$. \end{corollary} % {\bf Are the proofs needed anymore??? The first proof is a repeat % of what we have already said, but it is at least worth observing % that it can also be obtained by expanding the binomial series in % \reff{eq.potts.genfn.nle1.1} (I think). % The second and third proofs can probably be deleted if we end up % being able to generalize them to arbitrary $q_1$.} % % \begin{quote} % \begin{quote} % % \begin{proof} % Specializing \reff{eq.partition2bis.q1.q2} to $\n = \one$, % we obtain a sum over ordered partitions $\pi = (\pi_1,\ldots,\pi_\ell)$ % of $V$ into $\ell$ nonempty blocks. % Passing from ordered to unordered partitions, % we get a factor $\ell!$ that cancels the $1/\ell!$ % in \reff{eq.partition2bis.q1.q2}. % Specializing to $q_1 = 1$ and using \reff{ZG.q=1}, % we obtain \reff{eq.prop.ZG.partitions.1}. % % The remaining two formulae are obtained by specialization % to $q=0$ [after division by $q$] and $q=-1$, respectively. % \end{proof} % % % Let us also give a pair of simple direct proofs of % \reff{eq.prop.ZG.partitions.1}: % % \secondproofof{Proposition~\ref{prop.ZG.partitions}} % Since both sides of \reff{eq.prop.ZG.partitions.1} are polynomials in $q$, % it suffices to prove the identity for all positive integers $q$. % We shall do this using Theorem~\ref{thm.FK}. % Each (not-necessarily-proper) coloring $\sigma \colon\, V \to [q]$ % induces a partition $\pi_\sigma$ of $V$ into its nonempty color classes, % and we have % \begin{equation} % \prod_{e=ij \in E} \, % \biggl[ 1 + v_e \delta\bigl(\sigma(i), \sigma(j)\bigr) \biggr] % \;=\; % \prod_{B\in \pi_\sigma} \, \prod_{e \in E(G[B])} (1+v_e) % \;. % \end{equation} % Conversely, each partition $\pi$ of $V$ arises in this way from % $q^{\underline{|\pi|}}$ different colorings $\sigma$, % since we have $q$ choices to color the lexicographically first block of $\pi$, % $q-1$ choices for the lexicographically second block, and so forth. % This proves \reff{eq.prop.ZG.partitions.1}. % \end{proof} % % \thirdproofof{Proposition~\ref{prop.ZG.partitions}} % The double product on the right-hand side of \reff{eq.prop.ZG.partitions.1} % can be interpreted as enumerating all spanning subgraphs $H$ of $G$ % that are {\em compatible}\/ with $\pi$ % in the sense that each block of $\pi$ is a union of (vertex sets of) % connected components of $H$. % Fixing such a subgraph $H$ and summing over the allowed $\pi$, % we argue as in the second proof of Theorem~\ref{thm.Potts_genfn}, % using \reff{eq.stirlingidentity}, % to obtain a weight $q^{k(H)} \!\! \prod\limits_{e \in E(H)} v_e$. % \end{proof} % % \end{quote} % \end{quote} Specializing \reff{eq.prop.ZG.partitions.1}--\reff{eq.prop.ZG.partitions.3} to $v_e = -1$ for all edges $e$, we have: \begin{corollary} \label{cor.ZG.partitions} Let $G=(V,E)$ be a finite loopless graph with $|V|=n$. Then: \begin{eqnarray} P_G(q) & = & \sum_{k=1}^n q^{\underline{k}} \, Q_G(k) \label{eq.cor.ZG.partitions.1} \\[2mm] P'_G(0) \;=\; C_G(-1) & = & \sum_{k=1}^n (-1)^{k-1} \, (k-1)! \: Q_G(k) \label{eq.cor.ZG.partitions.2} \\[2mm] P_G(-1) & = & \sum_{k=1}^n (-1)^k \, k! \: Q_G(k) \label{eq.cor.ZG.partitions.3} \end{eqnarray} where $Q_G(k)$ denotes the number of partitions of $V$ into $k$ nonempty {\em independent} subsets. \end{corollary} Of course, \reff{eq.cor.ZG.partitions.1} is well known and has a trivial direct proof by counting proper $q$-colorings; and \reff{eq.cor.ZG.partitions.2}/\reff{eq.cor.ZG.partitions.3} are immediate corollaries of \reff{eq.cor.ZG.partitions.1}. %% {\bf Is there a combinatorial interpretation of $P'_G(0)$ %% or $P_G(-1)$ in terms of some kind of inclusion-exclusion? %% Note that $k! Q_G(k)$ equals the number of \emph{ordered}\/ %% partitions of $V$ into $k$ nonempty independent subsets.} Let us conclude by giving two direct combinatorial proofs of the fundamental Proposition~\ref{prop.ZG.partitions.q1q2}: one using the subgraph representation \reff{def.ZG}, and the other using the coloring representation \reff{eq.FK.identity}. \begin{proof}[Second Proof of Proposition~\ref{prop.ZG.partitions.q1q2}] Use the partition formula \reff{eq.prop.ZG.partitions.0} [which itself had a simple direct combinatorial proof] to expand $Z_G(q_2,\bv)$ on the left-hand side of \reff{eq.prop.ZG.partitions.q1q2} and to expand each $Z_{G[B]}(q_1,\bv)$ on the right-hand side. %% of \reff{eq.prop.ZG.partitions.q1q2}. We can then interpret the double sum on the right-hand side as a sum over partitions $\pi$ 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 \begin{equation} \sum_{k=1}^n \stirlingsubset{n}{k} \, (q_2/q_1)^{\underline{k}} \;=\; (q_2/q_1)^n \label{eq.stirling2} \end{equation} where $n = |\pi|$, we get exactly the expression on the left-hand side. \end{proof} It will not escape the reader's notice that the argument using \reff{eq.stirling2} is identical to the one given earlier using \reff{eq.stirlingidentity}. \begin{proof}[Third Proof of Proposition~\ref{prop.ZG.partitions.q1q2}] Since both sides of \reff{eq.prop.ZG.partitions.q1q2} 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~\ref{thm.FK}. Consider a (not-necessarily-proper) coloring $\sigma \colon\, V \to [q_2]$. Fix a bijection $[q_2] \simeq [q_1] \times [r]$ and write $\sigma = (\tau,\psi)$ where $\tau \colon\, V \to [q_1]$ and $\psi \colon\, V \to [r]$. We then trivially have \begin{subeqnarray} Z_G(q_2, \bv) & = & \sum_{ \sigma \colon\, V \to [q_2]} \; \prod_{e=ij \in E} \, \biggl[ 1 + v_e \delta\bigl(\sigma(i), \sigma(j)\bigr) \biggr] \\[2mm] & = & \sum_{ \psi \colon\, V \to [r]} \; \sum_{ \tau \colon\, V \to [q_1]} \; \prod_{e=ij \in E} \, \biggl[ 1 + v_e \delta\bigl(\tau(i), \tau(j)\bigr) \delta\bigl(\psi(i), \psi(j)\bigr) \biggr] \,. \qquad \quad \end{subeqnarray} The map $\psi$ induces a partition $\pi_\psi$ of $V$ into its nonempty color classes, and the remaining sum over $\tau$ gives (by Theorem~\ref{thm.FK} again) $\prod_{B \in \pi_\psi} Z_{G[B]}(q_1,\bv)$. On the other hand, each partition $\pi$ of $V$ arises in this way from $r^{\underline{|\pi|}}$ different colorings $\psi$, since we have $r$ choices to color the lexicographically first block of $\pi$, $r-1$ choices for the lexicographically second block, and so forth. This proves \reff{eq.prop.ZG.partitions.q1q2}. \end{proof} {\bf Important note:} The formulae in this subsection --- notably \reff{eq.prop.ZG.partitions.2} together with the $q=1$ case of \reff{eq.prop.ZG.partitions.0} --- are strongly reminiscent of M\"obius inversion on the lattice of partitions $\Pi(V)$. This is not an accident. In fact, the formula \reff{eq.prop.ZG.partitions.q1q2.alt2} is a special case of a ``$q_1$--$q_2$ generalization'' of M\"obius inversion that we present in Appendix~\ref{app.Mobius}. We are grateful to an anonymous referee for drawing our attention to the connection of these formulae with M\"obius inversion and for challenging us to find the underlying general principle. \subsubsection{Convolution formulae} In a similar way we can obtain convolution formulae for the multivariate Tutte polynomial by specializing \reff{eq.id1.multidim}--\reff{eq.id2.multidim}: %% Our last main result is the following: \begin{proposition} \label{prop.ZG.recursions} Let $G=(V,E)$ be a finite loopless graph. Then \begin{equation} Z_G(q_1+q_2,\bv) \;=\; \sum_{ W \subseteq V } Z_{G[W]}(q_1,\bv) \, Z_{G[V \setminus W]}(q_2,\bv) \;. \label{eq.lin.0} \end{equation} Moreover, for each $i \in V$ we have \begin{equation} \Zhat_G(q_1+q_2,\bv) \;=\; \sum_{\begin{scarray} W \subseteq V \\ W \ni i \end{scarray} } \Zhat_{G[W]}(q_1,\bv) \, Z_{G[V \setminus W]}(q_2,\bv) \label{eq.lin.1} \end{equation} and in particular \begin{equation} Z_G(q,\bv) \;=\; \sum_{\begin{scarray} W \subseteq V \\ W \ni i \end{scarray} } q C_{G[W]}(\bv) \, Z_{G[V \setminus W]}(q,\bv) \;. \label{eq.lin.2} \end{equation} We also have \begin{equation} |V| \, Z_G(q_2,\bv) \;=\, \sum_{\emptyset \neq W \subseteq V} \Bigl[ (q_1+q_2)|W| \,-\, q_1 |V| \Bigr] \, \Zhat_{G[W]}(q_1,\bv) \, Z_{G[V \setminus W]}(q_2,\bv) \;. \qquad \label{eq.lin.2a} \end{equation} \end{proposition} \begin{proof} \reff{eq.lin.0} and \reff{eq.lin.1} are just \reff{eq.id1.multidim} and \reff{eq.id2.multidim}, respectively, specialized to $\n = \one$. Further specializing the latter to $q_1 = 0$, we obtain \reff{eq.lin.2}. Finally, \reff{eq.lin.2a} is obtained by subtracting $(q_1+q_2) \times \hbox{\reff{eq.lin.1}}$ from \reff{eq.lin.0} and summing over $i \in V$. \end{proof} For completeness, let us give a simple direct proof of \reff{eq.lin.1}. [\reff{eq.lin.0} is similar but easier, and is left as an exercise for the reader.] \begin{proof}[Alternate Proof of Proposition~\ref{prop.ZG.recursions}] {}From the definition \reff{def.ZhatG} we have \begin{equation} \Zhat_G(q_1+q_2, \bv) \;=\; \sum_{A \subseteq E} (q_1+q_2)^{k(A)-1} \prod_{e \in A} v_e \;. \end{equation} The factor $(q_1+q_2)^{k(A)-1}$ can be handled by choosing, for each connected component of $(V,A)$ {\em 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 \subseteq V$ to be the vertex set corresponding to the union of the components colored ``1'' {\em 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 \setminus W$. Moreover, every $W \ni 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 \reff{eq.lin.1} is given precisely by such a sum over compatible pairs $(W,A)$ [the $\widehat{\hphantom{Z}}$ on $\Zhat_{G[W]}(q_1,\bv)$ accounts for the fact that the component containing $i$ carries no color and hence no factor $q_1$]. \end{proof} We do not know whether the Abel-type extensions \reff{eq.id1.t.multidim}/\reff{eq.id2.t.multidim}, when applied to the multivariate Tutte polynomial, are of any interest. \subsection{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)$, $\Zhat_n(q,v)$ and $C_n(v)$ for the corresponding polynomials. \subsubsection{Partition formulae} Specializing \reff{eq.prop.ZG.partitions.q1q2}, we obtain the general identity \begin{equation} Z_n(q_2,v) \;=\; \sum\limits_{\pi \in \Pi_n} (q_2/q_1)^{\underline{|\pi|}} \prod_{i=1}^{|\pi|} Z_{|\pi_i|}(q_1,v) \;, \label{eq.Znqv.partitions.q1q2} \end{equation} where the sum runs over (unordered) partitions $\pi$ of $[n]$, say $\pi = \{\pi_1,\ldots,\pi_\ell\}$, and $|\pi|$ denotes the number of blocks in $\pi$ (i.e., $|\pi| = \ell$). Special cases of \reff{eq.Znqv.partitions.q1q2} arise at particular values of $q_1$: \medskip {\bf Case \mbox{\boldmath$q_1=0$}.} Specializing \reff{eq.prop.ZG.partitions.0}, we obtain the trivial identity \begin{equation} Z_n(q,v) \;=\; \sum\limits_{\pi \in \Pi_n} q^{|\pi|} \prod_{i=1}^{|\pi|} C_{|\pi_i|}(v) \;. \label{eq.Znqv.partitions.0} \end{equation} %% where the sum runs over (unordered) partitions $\pi$ of $[n]$, %% say $\pi = \{\pi_1,\ldots,\pi_\ell\}$, %% and $|\pi|$ denotes the number of blocks in $\pi$ (i.e., $|\pi| = \ell$). \medskip {\bf Case \mbox{\boldmath$q_1=1$}.} Specializing \reff{eq.prop.ZG.partitions.1}--\reff{eq.prop.ZG.partitions.3}, we obtain the less trivial relations \begin{eqnarray} Z_n(q, v) & = & \sum\limits_{\pi \in \Pi_n} q^{\underline{|\pi|}} \: (1+v)^{n(n-1)/2 - \|\pi\|} \label{eq.Znqv.partitions} \\[2mm] C_n(v) & = & \sum\limits_{\pi \in \Pi_n} (-1)^{|\pi|-1} \: (|\pi| -1)! \: (1+v)^{n(n-1)/2 - \|\pi\|} \label{eq.Cnv.partitions} \\[2mm] Z_n(-1, v) & = & \sum\limits_{\pi \in \Pi_n} (-1)^{|\pi|} \: |\pi|! \: (1+v)^{n(n-1)/2 - \|\pi\|} \label{eq.Znminusonev.partitions} \end{eqnarray} %% where the sum runs over (unordered) partitions $\pi$ of $[n]$, %% say $\pi = \{\pi_1,\ldots,\pi_\ell\}$; %% here $|\pi|$ denotes the number of blocks in $\pi$ (i.e., $\ell$), %% and where \begin{equation} \| \pi \| \;=\; \sum_{1 \le i k > 1$ and $k$ is a descendant of $j$ (i.e., the path from 1 to $k$ passes through $j$). We define the {\em inversion enumerator for trees}\/ \cite{Mallows_68,Gessel_79,Kreweras_80} (see also \cite{Gessel_95,Gessel_96,Chauve_00}) to be the polynomial \begin{equation} I_n(y) \;=\; \sum_{\hbox{\scriptsize trees $T$ on $[n]$}} y^{{\rm inv}(T)} \label{def.In} \end{equation} where ${\rm inv}(T)$ denotes the number of inversions in $T$. This polynomial turns out to be related to $C_n(v)$ by the beautiful formula \cite{Mallows_68,Gessel_79,Kreweras_80,Beissinger_82} \begin{equation} C_n(v) \;=\; v^{n-1} I_n(1+v) \;. \label{eq.Cn.In} \end{equation} Now, Mallows, Riordan and Kreweras \cite{Mallows_68,Kreweras_80} show that $I_n(y)$ satisfies the recursion \begin{equation} I_n(y) \;=\; \sum_{k=1}^{n-1} {\binom {n-2 } { k-1}} \left( \sum_{j=0}^{k-1} y^j \right) I_k(y) \, I_{n-k}(y) \qquad\hbox{for } n \ge 2 \;. \label{eq.nonlin.In} \end{equation} But using \reff{eq.Cn.In}, it is easily seen that \reff{eq.nonlin.In} is equivalent to \reff{eq.nonlin.Kn.q=0}. %% Just set $y=1+v$ and divide both sides of \reff{eq.nonlin.Kn.q=0} %% by (y-1)^{n-1}. Let us remark, finally, that even without using \reff{def.In}, it follows immediately from the recursion \reff{eq.nonlin.In} [together with the initial condition $I_1(y) = 1$] that the polynomials $I_n(y) \equiv C_n(y-1)/(y-1)^{n-1}$ have nonnegative (indeed, strictly positive) integer coefficients. %% --- a fact that can also be proven by other methods %% \cite[Remark~2 in Section~4.1]{Sokal_chromatic_bounds} %% \cite[Proposition~2.5]{Scott-Sokal_lovasz}. On the other hand, the nonnegativity of the derivatives of $I_n(y)$ at $y=0$ is also a special case of Proposition~\ref{prop.ineq.CGlambda}. % {\bf If one substitutes $C_n(v) = v^{n-1} I_n(1+v)$ into the % \emph{linear} identity, one obtains % $$ % (y-1)^{n-1} I_n(y) \;=\; % y^{n(n-1)/2} \,-\, % \sum_{k=1}^{n-1} {\binom {n-1 } { k-1}} \, (y-1)^{k-1} I_k(y) \, % y^{(n-k)(n-k-1)/2} % \;. % $$ % But it's not obvious to me how to see {\em a priori}\/ % that the RHS is divisible by $(y-1)^{n-1}$.} \appendix \section{A generalization of M\"obius inversion on the partition lattice} \label{app.Mobius} In this appendix we present an apparently new generalization of M\"obius inversion on the lattice of partitions of a finite set, which is inspired by the formulae in Section~\ref{subsubsec.partitions} and in particular by \reff{eq.prop.ZG.partitions.q1q2.alt2}, and more generally by \reff{eq.partition2bis.q1hat.q2}. We refer to \cite[Chapter~3]{Stanley_86} for basic facts about posets and M\"obius inversion. To begin with, let $P$ be a finite poset. Then the {\em zeta function}\/ $\zeta$ on $P$ is the function $\zeta \colon\, P \times P \to \Z$ defined by \be \zeta(x,y) \;=\; \begin{cases} 1 & \text{if $x \le y$} \\ 0 & \text{if $x \not\le y$} \end{cases} \ee (We think of $\zeta$ as a matrix whose rows and columns are indexed by $P$.) The {\em M\"obius function}\/ $\mu$ on $P$ is the two-sided matrix inverse of $\zeta$, i.e., it satisfies $\zeta\mu = \mu\zeta = I$. It can be computed by the recursion \be \mu(x,y) \;=\; \begin{cases} 1 & \text{if $x = y$} \\[1mm] -\sum\limits_{x \le z < y} \mu(x,z) & \text{if $x < y$} \\[1mm] 0 & \text{if $x \not\le y$} \end{cases} \ee Now let $S$ be a finite set, and let $P$ be the lattice $\Pi(S)$ of partitions of $S$, ordered by refinement. It is well known \cite[p.~128]{Stanley_86} that the M\"obius function of $\Pi(S)$ is given by \be \mu(\sigma,\pi) \;=\; \begin{cases} \prod\limits_{i=1}^k (-1)^{\lambda_i-1} (\lambda_i-1)! & \parbox{2.5in}{if $\sigma \le \pi = \{B_1,\ldots,B_k\}$ and $B_i$ is partitioned into $\lambda_i$ blocks in $\sigma$} \\[7mm] 0 & \text{if $\sigma \not\le \pi$} \end{cases} \label{def.mu.partition} \ee We generalize this as follows: let $q_1$ and $q_2$ be indeterminates, and define \be \mu_{q_1,q_2}(\sigma,\pi) \;=\; \begin{cases} \prod\limits_{i=1}^k \prod\limits_{j=1}^{\lambda_i-1} (q_2 - jq_1) & \parbox{2.5in}{if $\sigma \le \pi = \{B_1,\ldots,B_k\}$ and $B_i$ is partitioned into $\lambda_i$ blocks in $\sigma$} \\[7mm] 0 & \text{if $\sigma \not\le \pi$} \end{cases} \label{def.muq1q2.partition} \ee Let us observe for future reference that \be \prod\limits_{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}} \;. \ee Then we have in particular \begin{subeqnarray} \mu_{0,1} & = & \zeta \\[1mm] \mu_{1,0} & = & \mu \\[1mm] \mu_{q,q} & = & I \quad\hbox{for all $q$} \end{subeqnarray} We shall prove the following generalization of M\"obius inversion: \begin{theorem} \label{thm.mobius} Let $S$ be a finite set, and define the matrices $\mu_{q_1,q_2}$ on $\Pi(S)$ by \reff{def.muq1q2.partition}. Then \be \mu_{q_1,q_2} \, \mu_{q_2,q_3} \;=\; \mu_{q_1,q_3} \qquad\text{(matrix multiplication)} \label{eq.thm.mobius} \ee \end{theorem} We interpret \reff{eq.thm.mobius} as an identity in the polynomial ring $\Z[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\"obius inversion corresponds to the special cases $(q_1,q_2,q_3) = (0,1,0)$ and $(1,0,1)$. The proof of Theorem~\ref{thm.mobius} 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. %% {\bf Ask some other people about this!!!} \begin{lemma} \label{lemma.partitions} Let $m$ be a positive integer, and let $r$ and $s$ be indeterminates. Then \be \sum_{\omega \in \Pi_m} r^{\underline{|\omega|}} \, \Biggl( \prod_{B \in\omega} s^{\underline{|B|}} \Biggr) \;=\;\, (rs)^{\underline{m}} \label{eq.lemma.partitions} \ee as an identity in the polynomial ring $\Z[r,s]$. \end{lemma} Let us remark that if one divides \reff{eq.lemma.partitions} by $s^m$ and takes $s \to\infty$ (or equivalently just extracts the coefficient of $s^m$), one obtains the well-known formula \reff{eq.stirlingidentity}/\reff{eq.stirling2}; while if one sets $r = q/\epsilon$, $s = \epsilon q$ and takes $\epsilon\to 0$, then one obtains the formula \be \sum_{\pi \in \Pi_m} \mu(\hat{0},\pi) \, q^{|\pi|} \;=\; q^{\underline{m}} \ee due to Rota \cite[Section~9]{Rota_64} \cite[pp.~128, 162, 187]{Stanley_86} (here $\hat{0}$ denotes the partition in which every element is a singleton). \begin{proof}[Proof of Lemma~\ref{lemma.partitions}] It suffices to prove \reff{eq.lemma.partitions} 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] \times [s]$ %% = \{ (i,j) \colon\, i \in [r] \hbox{ and } j \in [s] \}$ and define $\omega$ 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. \end{proof} \medskip \noindent {\it Second Proof of Lemma~\ref{lemma.partitions} (suggested independently by Christian Krattenthaler and Richard Stanley).} We use the isomorphism of weighted species \be \hbox{Partitions} \;=\; \hbox{Sets} \circ \hbox{NonemptySets} \;, \ee 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 $\omega$ is weighted as on the left-hand side of \reff{eq.lemma.partitions}.\footnote{ See \cite[pp.~44, 86]{Bergeron_98} for this isomorphism with a different weighting. For the reader unfamiliar with the theory of combinatorial species \cite{Bergeron_98}, 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 \cite[Theorem~5.1.4]{Stanley_99} to complete the proof. } The corresponding exponential generating functions are \begin{eqnarray} F(x) & = & \sum_{b=0}^\infty {\frac {x^b } { b!}} \, r^{\underline{b}} \;=\; (1+x)^r \\[1mm] G(x) & = & \sum_{k=1}^\infty {\frac {x^k } { k!}} \, s^{\underline{k}} \;=\; (1+x)^s - 1 \end{eqnarray} and hence \be (F \circ G)(x) \;=\; (1+x)^{rs} \;=\; \sum_{m=0}^\infty {\frac {x^m } { m!}} \, (rs)^{\underline{m}} \;, \ee which proves \reff{eq.lemma.partitions} for all $m \ge 0$. \qed \medskip \begin{proof}[Proof of Theorem~\ref{thm.mobius}] Let $\sigma \le \pi = \{B_1,\ldots,B_k\}$ where $B_i$ is partitioned into $\lambda_i$ blocks in $\sigma$, and let us compute \be ( \mu_{q_1,q_2} \, \mu_{q_2,q_3} )(\sigma,\pi) \;=\; \sum_{\sigma \le \tau \le \pi} \mu_{q_1,q_2}(\sigma,\tau) \, \mu_{q_2,q_3}(\tau,\pi) \;. \label{eq.proof.thm.mobius} \ee The partition $\tau$ is specified by saying, for each $i \in [k]$, how the corresponding $\lambda_i$~blocks of $\sigma$ get grouped in $\tau$. %% (let's say into $\mu_i$ groups). The sum \reff{eq.proof.thm.mobius} will then factorize over $i$, with the $i$th factor given by \begin{eqnarray} & & \sum_{\begin{scarray} \omega \in \Pi_{\lambda_i} \\ \omega = \{ \widehat{B}_1,\ldots, \widehat{B}_{\mu_i} \} \end{scarray}} \!\!\! \left( \prod\limits_{\alpha=1}^{\mu_i} \prod\limits_{j=1}^{|\widehat{B}_\alpha|-1} (q_2 -jq_1) \right) \prod\limits_{k=1}^{\mu_i-1} (q_3 -kq_2) \nonumber \\[2mm] & & \qquad\qquad =\; \!\!\! \sum_{\begin{scarray} \omega \in \Pi_{\lambda_i} \\ \omega = \{ \widehat{B}_1,\ldots, \widehat{B}_{\mu_i} \} \end{scarray}} \!\!\! \left( \prod\limits_{\alpha=1}^{\mu_i} q_1^{|\widehat{B}_\alpha|} q_2^{-1} (q_2/q_1)^{\underline{|\widehat{B}_\alpha|}} \right) q_2^{\mu_i} q_3^{-1} (q_3/q_2)^{\underline{\mu_i}} \nonumber \\[2mm] & & \qquad\qquad =\; q_1^{\lambda_i} q_3^{-1} \!\!\! \sum_{\begin{scarray} \omega \in \Pi_{\lambda_i} \\ \omega = \{ \widehat{B}_1,\ldots, \widehat{B}_{\mu_i} \} \end{scarray}} \!\!\! \left( \prod\limits_{\alpha=1}^{\mu_i} (q_2/q_1)^{\underline{|\widehat{B}_\alpha|}} \right) (q_3/q_2)^{\underline{\mu_i}} \nonumber \\[2mm] & & \qquad\qquad =\; q_1^{\lambda_i} q_3^{-1} (q_3/q_1)^{\underline{\lambda_i}} \end{eqnarray} by Lemma~\ref{lemma.partitions}. \end{proof} \begin{proof}[Second Proof of Theorem~\ref{thm.mobius} (suggested by Richard Stanley)] We prove \reff{eq.thm.mobius} for\break $S=[n]$ simultaneously for all $n \ge 1$, using the interpretation of convolution of multiplicative functions on $\bm{\Pi} = (\Pi_1,\Pi_2,\ldots)$ in terms of composition of exponential generating functions \cite[pp.~7--8]{Stanley_99}. We first observe that $\mu_{q_1,q_2}$ is a multiplicative function on $\bm{\Pi}$, with underlying numerical function \be f_{q_1,q_2}(m) \;=\; \prod\limits_{j=1}^{m-1} (q_2 - jq_1) \;=\; q_1^m q_2^{-1} (q_2/q_1)^{\underline{m}} \ee and corresponding exponential generating function \be F_{q_1,q_2}(x) \;=\; \sum_{m=1}^\infty f_{q_1,q_2}(m) \, {\frac {x^m } { m!}} \;=\; q_2^{-1} [(1+ q_1 x)^{q_2/q_1} - 1] \;. \ee It is easy to check that \be F_{q_2,q_3}(F_{q_1,q_2}(x)) \;=\; F_{q_1,q_3}(x) \;. \ee By \cite[Theorem~5.1.11]{Stanley_99}, the identities \reff{eq.thm.mobius} for all $n \ge 1$ are an immediate consequence.\footnote{ Using \cite[Theorem~5.1.11]{Stanley_99} with the coefficient field $K$ taken to be (say) $\R$, this argument proves \reff{eq.thm.mobius} for $q_1,q_2,q_3 \in \R \setminus \{0\}$, which is more than enough to imply it as a polynomial identity. Alternatively, we can use \cite[Theorem~5.1.11]{Stanley_99} with $K$ taken to be (say) the field $\R(q_1,q_2,q_3)$ of rational functions in the indeterminates $q_1,q_2,q_3$, which yields \reff{eq.thm.mobius} directly as a polynomial identity. } \end{proof} \begin{remark} If we define the diagonal matrix $D_r$ by \be D_r(\sigma,\pi) \;=\; \begin{cases} r^{|\sigma|} & \text{if $\sigma = \pi$} \\ 0 & \text{if $\sigma \neq \pi$} \end{cases} \ee then an easy calculation shows that \be D_r \, \mu_{q_1,q_2} \, D_r^{-1} \;=\; \mu_{rq_1,rq_2} \;. \ee This is why many things involving $\mu_{q_1,q_2}$ depend only on the ratio $q_2/q_1$ [cf.\ \reff{eq.prop.ZG.partitions.q1q2}]. \end{remark} We can apply Theorem~\ref{thm.mobius} as follows: Let $R$ be a commutative ring, and fix a function $f \colon\, \Pi(S) \to R$ and an element $q_0 \in R$ (it could be an indeterminate if desired). Now introduce a new indeterminate $q$, and define $F_q \colon\, \Pi(S) \to R[q]$ by \be F_q \;=\; f \, \mu_{q_0,q} \ee or in more detail \be F_q(\pi) \;=\; \sum_{\sigma \in \Pi(S)} f(\sigma) \, \mu_{q_0,q}(\sigma,\pi) \;. \ee By construction we have imposed the ``initial condition'' \be F_{q_0} \;=\; f \ee (here $F_{q_0}$ means of course that the indeterminate $q$ is replaced by the value $q_0 \in R$). Most importantly, Theorem~\ref{thm.mobius} implies that the $q$-dependence of $F_q$ is ``coherent'' in the sense that \be F_{q_1} \, \mu_{q_1,q_2} \;=\; F_{q_2} \;. \label{eq.Fq.coherent} \ee The formula \reff{eq.prop.ZG.partitions.q1q2.alt2} is now the special case of \reff{eq.Fq.coherent} in which we take $S=V$, \be F_q(\pi) \;=\; \prod_{B\in \pi} \, \Zhat_{G[B]}(q,\bv) \;, \ee and we evaluate \reff{eq.Fq.coherent} at $\pi = \hat{1}$ (the partition in which all of $V$ belongs to a single block). More generally, in place of $\Zhat_{G[B]}(q,\bv)$ we can use $\ahat_{\one_B}(q)$ where $\{ \ahat_\n(q) \}$ is {\em any}\/ family arising as in Section~\ref{sec2}; we then obtain \reff{eq.partition2bis.q1hat.q2} specialized to $\n = \one$.\footnote{ Note also that, in these formulae, we use $\ahat_\n(q)$ [or $c_\n$] only for $\zero \le \n \le \one$. } \bigskip 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\"obius inversion for some other posets? Maybe even for some natural {\em class}\/ of posets? \section*{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 \cite[Section~3.1]{Bergeron_98} and notably to \cite[p.~189, Exercise~3.1.22]{Bergeron_98}, from which we learned about the Abel-type extensions \reff{eq.id1.t}--\reff{eq.id4.t}. 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. Finally, we are grateful to an anonymous referee for pointing out the connection of the formulae of Section~\ref{subsubsec.partitions} with M\"obius 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. %% \clearpage %%\addcontentsline{toc}{section}{References} \begin{thebibliography}{199} % \bibitem{Aigner_79} M. Aigner, {\em Combinatorial Theory}\/, % Grundlehren der mathematischen Wissenschaften \#234 % (Springer-Verlag, Berlin--New York, 1979). \bibitem{Andrews_99} G.E. Andrews, R. Askey and R. Roy, {\em Special Functions}\/ (Cambridge University Press, Cambridge--New York, 1999), Section~6.2. \bibitem{Bateman} W. Magnus, F. Oberhettinger, and F.G. Tricomi, {\em Higher Transcendental Functions}\/, vol.~2 (McGraw-Hill, New York, 1953). \bibitem{Beissinger_82} J.S. Beissinger, On external activity and inversions in trees, J. Combin. Theory B {\bf 33}, 87--92 (1982). \bibitem{Birkhoff_12} G.D. Birkhoff, A determinant formula for the number of ways of coloring a map, Ann. Math. {\bf 14}, 42--46 (1912). \bibitem{Bergeron_98} F. Bergeron, G. Labelle and P. Leroux, {\em Combinatorial Species and Tree-Like Structures}\/ (Cambridge University Press, Cambridge--New York, 1998). % \bibitem{Biggs_77} N.L. Biggs, {\em Interaction Models}\/, % London Mathematical Society Lecture Note Series \#30 % (Cambridge University Press, Cambridge, 1977). \bibitem{Biggs_93} N. Biggs, {\em Algebraic Graph Theory}\/, 2nd ed.\ (Cambridge University Press, Cambridge--New York, 1993), p.~103, item 13e. \bibitem{Bjorner_92} A. Bj\"orner, The homology and shellability of matroids and geometric lattices, in N.~White (editor), {\em Matroid Applications}\/ (Encyclopedia of Mathematics and its Applications \#40), Chapter 7, pp.~226--283 (Cambridge University Press, Cambridge, 1992). \bibitem{Borgs_00} C. Borgs, Polymer systems, Pirogov--Sinai theory and conductance bounds. Lecture notes, Microsoft Research, October 2000, unpublished, cited in \cite[p.~68]{Borgs_06}. \bibitem{Borgs_06} C. Borgs, Absence of zeros for the chromatic polynomial of bounded degree graphs, Combin. Probab. Comput. {\bf 15}, 63--74 (2006). \bibitem{Chauve_00} C. Chauve, P. Duchon and S. Dulucq, Une g\'en\'eralisation des r\'esultats de Kreweras sur le polyn\^ome \'enum\'erateur des inversions dans les arborescences, Ann. Sci. Math. Qu\'ebec {\bf 24}, 129--144 (2000). \bibitem{Comtet_74} L. Comtet, {\em Advanced Combinatorics: The Art of Finite and Infinite Expansions}\/ %% Translated from the French by J. W. Nienhuys. (D.~Reidel, Dordrecht--Boston, 1974), Section~3.3. \bibitem{Fillmore_73} 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 {\bf 1}, 67--80 (1973). \bibitem{Foata_74} D. Foata, {\em La s\'erie g\'en\'eratrice exponentielle dans les probl\`emes d'\'enum\'eration}\/ (Presses de l'Universit\'e de Montr\'eal, Montr\'eal, 1974). \bibitem{Foata_70} D. Foata and M.-P. Sch\"utzenberger, {\em Th\'eorie g\'eom\'etrique des polyn\^omes eul\'eriens}\/, Lecture Notes in Mathematics \#138 (Springer-Verlag, Berlin--New York, 1970), Chapitre III. \bibitem{Fortuin_72} C.M. Fortuin and P.W. Kasteleyn, On the random-cluster model. I. Introduction and relation to other models, Physica {\bf 57}, 536--564 (1972). \bibitem{Garsia_73} A.M. Garsia, An expos\'e of the Mullin--Rota theory of polynomials of binomial type, Linear and Multilinear Algebra {\bf 1}, 47--65 (1973). \bibitem{Gessel_95} I.M. Gessel, Enumerative applications of a decomposition for graphs and digraphs, Discrete Math. {\bf 139}, 257--271 (1995). \bibitem{Gessel_03} I.M. Gessel, Applications of the classical umbral calculus, Algebra Univers. {\bf 49}, 397--434 (2003). \bibitem{Gessel_96} I.M. Gessel and B.E. Sagan, The Tutte polynomial of a graph, depth-first search, and simplicial complex partitions, Electron. J. Combin. {\bf 3}, no.~2, \#R9 (1996). \bibitem{Gessel_79} I. Gessel and D.-L. Wang, Depth-first search as a combinatorial correspondence, J. Combin. Theory A {\bf 26}, 308--313 (1979). \bibitem{Gould_56} H.W. Gould, Some generalizations of Vandermonde's convolution, Amer. Math. Monthly {\bf 63}, 84--91 (1956). \bibitem{Gould_57} H.W. Gould, Final analysis of Vandermonde's convolution, Amer. Math. Monthly {\bf 64}, 409--415 (1957). \bibitem{Gould_74} H.W. Gould, Coefficient identities for powers of Taylor and Dirichlet series, Amer. Math. Monthly {\bf 81}, 3--14 (1974). \bibitem{Gould_66} H.W. Gould and J. Kauck\'y, Evaluation of a class of binomial coefficient summations, J. Comb. Theory {\bf 1}, 233--247 (1966); erratum, J. Comb. Theory A {\bf 12}, 309--310 (1972). \bibitem{Graham_94} R.L. Graham, D.E. Knuth and O. Patashnik, {\em Concrete Mathematics: A Foundation for Computer Science}\/, 2nd ed.~(Addison-Wesley, Reading, Mass., 1994). \bibitem{Grimmett_book_to_appear} G. Grimmett, {\em The Random-Cluster Model}\/ (Springer-Verlag, New York, 2006). \bibitem{Harary_73} F. Harary and E.M. Palmer, {\em Graphical Enumeration}\/ (Academic Press, New York, 1973). \bibitem{Johnson_07} W.P. Johnson, The Pfaff/Cauchy derivative identities and Hurwitz type extensions, Ramanujan J. {\bf 13}, 167--201 (2007). \bibitem{Kasteleyn_69} P.W. Kasteleyn and C.M. Fortuin, Phase transitions in lattice systems with random local properties, J. Phys. Soc. Japan {\bf 26} (Suppl.), 11--14 (1969). \bibitem{Knuth_92} D.E. Knuth, Convolution polynomials, Mathematica J. {\bf 2}, 67--78 (1992); {\tt ar$\chi$iv:math.CA/9207221}. \bibitem{Kreweras_80} G. Kreweras, Une famille de polyn\^omes ayant plusieurs propri\'et\'es \'enumeratives, Period. Math. Hungar. {\bf 11}, 309--320 (1980). \bibitem{Labelle_80} G. Labelle, Sur l'inversion et l'it\'eration continue des s\'eries formelles, Europ. J. Combin. {\bf 1}, 113--138 (1980). \bibitem{Labelle_81} G. Labelle, Une nouvelle d\'emonstration combinatoire des formules d'inversion de Lagrange, Adv. Math. {\bf 42}, 217--247 (1981). \bibitem{Labelle_96} G. Labelle and P. Leroux, An extension of the exponential formula in enumerative combinatorics, Electron. J. Combin. {\bf 3}, no.~2, \#R12 (1996). %% \bibitem{Laskar_75} R. Laskar and W.R. Hare, %% The chromatic polynomial of a complete $r$-partite graph, %% Amer. Math. Monthly {\bf 82}, 752--754 (1975). \bibitem{Lass_01} B. Lass, Orientations acycliques et le polyn\^ome chromatique, European J. Combin. {\bf 22}, 1101--1123 (2001). \bibitem{Lebedev_65} N.N. Lebedev, {\em Special Functions and Their Applications}\/ (Prentice-Hall, Englewood Cliffs, N.J., 1965). \bibitem{Leroux_88} P. Leroux, Methoden der Anzahlbestimmung f\"ur einige Klassen von Graphen [Methods of enumeration for some classes of graphs], Bayreuth. Math. Schr. {\bf 26}, 1--36 (1988). \bibitem{Mallows_68} C.L. Mallows and J. Riordan, The inversion enumerator for labeled trees, Bull. Amer. Math. Soc. {\bf 74}, 92--94 (1968). \bibitem{Mullin_70} R. Mullin and G.-C. Rota, On the foundations of combinatorial theory. III.~Theory of binomial enumeration, in {\em Graph Theory and its Applications}\/, %% (Proceedings of an advanced seminar, Mathematics Research Center, %% University of Wisconsin, Madison, October 13--15, 1969), edited by Bernard Harris (Academic Press, New York, 1970), pp.~167--213. \bibitem{Nijenhuis_79} A. Nijenhuis and H.S. Wilf, The enumeration of connected graphs and linked diagrams, J. Combin. Theory A {\bf 27}, 356--359 (1979). \bibitem{Penrose_67} O. Penrose, Convergence of fugacity expansions for classical systems, in T.A. Bak (editor), {\em Statistical Mechanics: Foundations and Applications}\/, pp.~101--109 (Benjamin, New York--Amsterdam, 1967). \bibitem{Pitman_01} J. Pitman, Random mappings, forests, and subsets associated with Abel--Cayley--Hurwitz multinomial expansions, S\'em. Lothar. Combin. {\bf 46}, article B46h (2001). \bibitem{Pitman_02} J. Pitman, Forest volume decompositions and Abel--Cayley--Hurwitz multinomial expansions, J. Combin. Theory A {\bf 98}, 175--191 (2002). \bibitem{Potts_52} R.B. Potts, Some generalized order-disorder transformations, Proc. Cambridge Philos. Soc. {\bf 48}, 106--109 (1952). \bibitem{Reiner_77} D.L. Reiner, Multivariate sequences of binomial type, Stud. Appl. Math. {\bf 57}, 119--133 (1977). \bibitem{Riordan_68} J. Riordan, {\em Combinatorial Identities}\/ (Wiley, New York, 1968), especially Sections~1.5 and 1.6. \bibitem{Riordan_unpub} J. Riordan, unpublished, cited in \cite[p.~8]{Harary_73} and \cite[pp.~356--357]{Nijenhuis_79}. \bibitem{Roman_78} S.M. Roman and G.-C. Rota, The umbral calculus, Adv. Math. {\bf 27}, 95--188 (1978). \bibitem{Roman_84} S.M. Roman, {\em The Umbral Calculus}\/ (Academic Press, New York, 1984). \bibitem{Rota_64} G.-C. Rota, On the foundations of combinatorial theory. I.~Theory of M\"obius functions, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete {\bf 2}, 340--368 (1964). \bibitem{Rota_73} G.-C. Rota, D. Kahaner and A. Odlyzko, On the foundations of combinatorial theory. VIII.~Finite operator calculus, J. Math. Anal. Appl. {\bf 42}, 684--760 (1973). [Reprinted in G.-C. Rota, {\em Finite Operator Calculus}\/ (Academic Press, New York--London, 1975), Chapter~2.] \bibitem{Rota_94} G.-C. Rota and B.D. Taylor, The classical umbral calculus, SIAM J. Math. Anal. {\bf 25}, 694--711 (1994). \bibitem{Scott-Sokal_lovasz} A.D. Scott and A.D. Sokal, The repulsive lattice gas, the independent-set polynomial, and the Lov\'asz local lemma, J. Stat. Phys. {\bf 118}, 1151--1261 (2005); {\tt ar$\chi$iv:cond-mat/0309352}. \bibitem{Scott-Sokal_lovasz_shortpaper} A.D. Scott and A.D. Sokal, On dependency graphs and the lattice gas, Combin. Probab. Comput. {\bf 15}, 253--279 (2006). \bibitem{Scott-Sokal_cn_bounds} 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. \bibitem{Sokal_chromatic_bounds} A.D. Sokal, Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions, Combin. Probab. Comput. {\bf 10}, 41--77 (2001); {\tt ar$\chi$iv:cond-mat/9904146}. \bibitem{Sokal_bcc2005} A.D. Sokal, The multivariate Tutte polynomial (alias Potts model) for graphs and matroids, in {\em Surveys in Combinatorics, 2005}\/, edited by Bridget S.~Webb (Cambridge University Press, Cambridge--New York, 2005), pp.~173--226; {\tt ar$\chi$iv:math.CO/0503607}. \bibitem{Stam_87} A.J. Stam, Two identities in the theory of polynomials of binomial type, J. Math. Anal. Appl. {\bf 122}, 439--443 (1987). \bibitem{Stanley_86} R.P. Stanley, {\em Enumerative Combinatorics}\/, vol.~1 (Wadsworth \& Brooks/Cole, Monterey, California, 1986). Reprinted by Cambridge University Press, 1997. \bibitem{Stanley_99} R.P. Stanley, {\em Enumerative Combinatorics}\/, vol.~2 (Cambridge University Press, Cambridge--New York, 1999). \bibitem{Strehl_92} V. Strehl, Identities of Rothe--Abel--Schl\"afli--Hurwitz-type, Discrete Math. {\bf 99}, 321--340 (1992). \bibitem{Swenson_73} J.R. Swenson, The chromatic polynomial of a complete bipartite graph, Amer. Math. Monthly {\bf 80}, 797--798 (1973). \bibitem{Tutte_67} W.T. Tutte, On dichromatic polynominals, J. Combin. Theory {\bf 2}, 301--320 (1967). \bibitem{Uhlenbeck_62} 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), {\em Studies in Statistical Mechanics}\/, vol.~I, pp.~119--211 (North-Holland, Amsterdam, 1962). \bibitem{Welsh_00} D.J.A. Welsh and C. Merino, The Potts model and the Tutte polynomial, J. Math. Phys. {\bf 41}, 1127--1152 (2000). \bibitem{Whitney_32a} H. Whitney, A logical expansion in mathematics, Bull. Amer. Math. Soc. {\bf 38}, 572--579 (1932). \bibitem{Wilf_94} H.S. Wilf, {\em generatingfunctionology}\/, 2nd ed. (Academic Press, San Diego--London, 1994), Chapter 3. \bibitem{Wu_82} F.Y. Wu, The Potts model, Rev. Mod. Phys. {\bf 54}, 235--268 (1982); erratum {\bf 55}, 315 (1983). \bibitem{Wu_84} F.Y. Wu, Potts model of magnetism (invited), J. Appl. Phys. {\bf 55}, 2421--2425 (1984). \bibitem{Zeng_96} J. Zeng, Multinomial convolution polynomials, Discrete Math. {\bf 160}, 219--228 (1996). \end{thebibliography} \end{document}