%-----------LaTeX file begins here------------------- \documentclass[12pt, %a4paper ]{article} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amssymb} \addtolength{\oddsidemargin}{-1cm} \addtolength{\textwidth}{2cm} \addtolength{\medskipamount}{3pt} %\renewcommand{\label}{\arabic{sectioning}}%enumi}{(\roman{enumi})}{section} \renewcommand{\thefootnote}{\fnsymbol{footnote}} \renewcommand{\theequation}{1.\arabic{equation}} \newtheoremstyle{thmsty}{\medskipamount}{\medskipamount}% {\it}{}{\bfseries}{.}{.5em}{} \newtheoremstyle{dfnsty}{\medskipamount}{\medskipamount}% {}{}{\bfseries}{.}{.5em}{} \theoremstyle{thmsty} \newtheorem{thm}{Theorem}[section] \newtheorem{lem}{Lemma}[section] \newtheorem{cor}{Corollary}[section] \newtheorem{prob}{Problem}[section] \newtheorem{prop}{Proposition}[section] \theoremstyle{dfnsty} \newtheorem{dfn}{Definition}[section] \newtheorem*{exa}{Example} \newtheorem*{rem}{Remark} \allowdisplaybreaks \newcommand{\D}{\cal D} \newcommand{\fr}{\frac} \newcommand{\dis}{\displaystyle} \newcommand{\hj}{h_j(y_1, \dots, y_m)} \newcommand{\myit}[1]{\textit{\textrm{#1}}} \newcommand{\Omegage}{\underset{\scriptscriptstyle \geq}{\Omega}} \newcommand{\Omegaop}{\underset{\scriptscriptstyle \geqq}{\Omega}} \newcommand{\OmegaEqop}{\underset{\scriptscriptstyle =}{\Omega}} \newcommand{\lam}{\lambda} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} \title{MacMahon's Partition Analysis IV:\\ Hypergeometric Multisums} \author{George E.~Andrews\thanks{Partially supported by the visiting researcher program of the J.~Kepler University Linz.}\\ Department of Mathematics\\ The Pennsylvania State University\\ University Park, PA 16802, USA\\ \texttt{andrews@math.psu.edu}\\ \and Peter Paule\thanks{Supported by SFB-grant F1305 of the Austrian FWF.}\\ Research Institute for Symbolic Computation\\ Johannes Kepler University Linz\\ A--4040 Linz, Austria\\ \texttt{Peter.Paule@risc.uni-linz.ac.at}} \date{February 16, 1999} \maketitle \begin{abstract} \noindent In his famous book ``Combinatory Analysis" MacMahon introduced Partition Analysis as a computational method for solving problems in connection with linear homogeneous diophantine inequalities and equations, respectively. The object of this paper is to introduce an entirely new application domain for MacMahon's operator technique. Namely, we show that Partition Analysis can be also used for proving hypergeometric multisum identities. Our examples range from combinatorial sums involving binomial coefficients, harmonic and derangement numbers to multisums which arise in physics and which are related to the Knuth-Bender theorem. \end{abstract} \section{Introduction} %%%%%%%%%%%%%%%%%%%%%% \setcounter{equation}{0} %\label{sectioning} MacMahon devoted about hundred pages of his famous book \cite[Vol.~2]{MacMahon:CA} to the study of Partition Analysis, a computational method for solving problems in connection with linear homogeneous diophantine inequalities and equations, respectively. Nevertheless, with the exception of Stanley's article \cite{Stanley:Duke}, MacMahon's method has remained dormant until recently when M.~Bousquet-M\'elou and K. Eriksson \cite{BM-E:LHP} discovered their ``Lecture Hall Partition Theorem", a beautiful refinement of Euler's classic result \cite[p.~5]{Andrews:TOP}. It was exactly this achievement that brought Partition Analysis back on stage. Namely, the first named author observed in \cite{Andrews:MMPA} that this type of partition theorem is perfectly tailored for MacMahon's approach; see also \cite{Andrews:MMPA2}. In addition, it turned out that Partition Analysis is ideally suited for being supplemented by modern computer algebra methods. We developed the computer algebra package \texttt{Omega} which implements various aspects of MacMahon's ideas. For an introduction to basic facts of ``Omega Calculus'' and for a variety of applications see \cite{APR:III} and \cite{APR:V}. In order to illustrate what Partition Analysis is about, we recall the definition of MacMahon's Omega operator $\Omegaop$: \begin{dfn} \label{dfn:Omega def} The operator $\Omegaop$ is defined by \[ \Omegaop \sum_{s_1=-\infty}^{\infty} \cdots \sum_{s_r=-\infty}^{\infty} A_{s_1,\dots,s_r} \lambda_1^{s_1} \cdots \lambda_r^{s_r} := \sum_{s_1=0}^{\infty} \cdots \sum_{s_r=0}^{\infty} A_{s_1,\dots,s_r}, \] \end{dfn} \noindent where the domain of the terms $A_{s_1,\ldots,s_r}$ (e.g., functions of several complex variables, or certain formal Laurent or power series) is such that the action is well-defined in some suitable analytic or algebraic context. In the context of this paper convergence is no issue at all because the operator $\Omegaop$ will only act on (multivariate) Laurent polynomials ${\bf C}[\lam_1,\dots,\lam_r,\lam_1^{-1},\dots,\lam_r^{-1}]$ over the complex numbers; the only exceptions are in Sections 3 and 4 where we must assume $|\lambda| > 1$. The operator $\Omegaop$ can be viewed as a generalization of the constant term operator for which MacMahon introduced the symbol $\OmegaEqop$. More precisely we have: \begin{dfn} \label{dfn:OmegaEq def} The operator $\OmegaEqop$ is defined by \[ \OmegaEqop \sum_{s_1=-\infty}^{\infty} \cdots \sum_{s_r=-\infty}^{\infty} A_{s_1,\dots,s_r} \lambda_1^{s_1} \cdots \lambda_r^{s_r} := A_{0,\dots,0}. \] \end{dfn} \noindent Let $a(\lam_1,\dots,\lam_r)$ denote the multisum expression. For picking up coefficients we will use the notation \[ \langle \lam_1^{t_1}\cdots \lam_r^{t_r} \rangle\, a(\lam_1,\dots,\lam_r):= A_{t_1,\dots,t_r}. \] \noindent In other words, we have \[ \langle \lam_1^{t_1}\cdots \lam_r^{t_r} \rangle\, a(\lam_1,\dots,\lam_r)= \OmegaEqop \frac{a(\lam_1,\dots,\lam_r)}{\lam_1^{t_1}\cdots \lam_r^{t_r}}. \] \noindent As pointed out by MacMahon \cite[Vol.~II, VIII, p.~104]{MacMahon:CA} the $\OmegaEqop$ operator is related to $\Omegaop$ by \begin{eqnarray} \label{omega relation} \OmegaEqop F(\lam) = \Omegaop F(\lam) + \Omegaop F(1/\lam) - F(1). \end{eqnarray} \medskip On page 102 of his book \cite[Vol.~II, VIII]{MacMahon:CA} MacMahon gives a ``short study" of {\it The operation $\Omegaop$}: ``In connection with the inequality $\alpha_1 \geq \alpha_2$ we have already found that the sum $\sum x^{\alpha_1} y^{\alpha_2}$ depends upon \begin{eqnarray} \label{rule} \Omegaop \frac{1}{(1-\lambda x) \big(1-\frac{y}{\lambda}\big)} = \frac{1}{ (1-x) (1-x\, y)}." \end{eqnarray} Then MacMahon continues by adding eleven similar rules, all being ``easily verifiable results". For instance, \medskip \noindent \textit{Proof of \eqref{rule}.} By geometric series expansion the left hand side equals \[ \Omegaop \sum_{i,j \geq 0} \lam^{i- j} x^i y^j = \Omegaop \sum_{j,k \geq 0} \lam^k x^{j +k} y^j, \] where the summation parameter $i$ has been replaced by $i=j +k$. But now $\Omegaop$ sets $\lam$ to 1 which completes the proof. \hfill\qedsymbol \medskip Next we come back to MacMahon's remark concerning the sum $\sum x^{\alpha_1} y^{\alpha_2}$ where the summation parameters are nonnegative integers satisfying the inequality $\alpha_1 \geq \alpha_2$. Obviously this sum can be rewritten as \[ \Omegaop \sum_{\alpha_1,\alpha_2 \geq 0} \lam^{\alpha_1-\alpha_2} x^{\alpha_1} y^{\alpha_2} = \Omegaop \frac{1}{(1-\lam x) \left(1-\frac{y}{\lam} \right)}, \] and after applying rule \eqref{rule} we arrive at a closed form representation. In other words, the rule is used in order to eliminate the $\Omegaop$-variable $\lam$. \medskip This elimination approach is the essence of MacMahon's method. For all applications of Partition Analysis to find in Section VIII of his book, he applied his catalogue of rules in order to compute closed forms of generating functions by successive elimination of those variables the $\Omegaop$ operator acts on. In \cite{APR:III} and \cite{APR:V} we show that this procedure can be put into an algorithmic setting, i.e., the elimination can be done in an entirely automatic fashion without any table-look up. Roughly spoken the application domain for this algorithmic machinery concerns problems in connection with partitions or compositions of numbers. \medskip The application domain we consider in this paper is a different one. In enumeration problems (e.g., lattice paths, analysis of algorithms, graph theory) one often meets multidimensional sums over hypergeometric summands with constraints on the summation indices. In many of these cases the constraints are in form of Diophantine inequalities. Thus the multisums may involve binomial coefficients. But also single sums involving combinatorial numbers as, for instance, the derangement numbers ${\D}_n$ or the harmonic numbers $H_n$, can be rewritten as double- or multisums over hypergeometric summands. We list a few examples that are treated in the following sections: \noindent Calkin's identity \cite{Calkin}, \begin{eqnarray} \label{calkin} \sum_{k=0}^n \left( \sum_{j=0}^k \binom{n}{j} \right)^3 = \frac{n}{2}\, 8^n + 8^n -\frac{3n}{4}\, 2^n \binom{2n}{ n}, \end{eqnarray} \noindent Callan's identity \cite{Callan}, for derangement numbers (defined in equation (3.1)) \begin{eqnarray} \label{callan} \sum_{j=0}^k \binom{k}{ j} {\D}_{k+n-j} = k!\, \sum_{j=0}^{\min(n,k)} \binom{k}{ j} \binom{k+n-j}{ k} {\D}_{n-j}, \end{eqnarray} \noindent a harmonic number identity (defined in equation (4.1)) that must be well-known, \begin{eqnarray} \label{new} \sum_{k=0}^n \binom{k}{ m} (H_k-H_{n-k})= \binom{n+1}{ m+1} H_m, \end{eqnarray} \noindent and an identity found by Essam and Guttmann \cite{EG} \begin{eqnarray} \label{EG} \sum_{k_1} \sum_{k_1 \leq k_2} \frac{k_1-k_2}{n+1} \binom{n+1}{ k_1} \binom{n+1}{ k_2} = \binom{2n+1}{ n}. \end{eqnarray} \medskip In the following sections we will show that MacMahon's Partition Analyis can be used to treat also problems of this kind. In order to do so, one essentially needs to exploit elementary properties of the $\Omegaop$ operator. We remark that using Omega calculus in this way for proving multisum identities seems to be entirely new. At least we have not found any such example in MacMahon's work. \medskip However, because of \eqref{omega relation} which relates the $\Omegaop$ operator to the constant term operator, such type of application does not come as a complete surprise. For instance, a good portion of Egorychev's book \cite{Egory} is devoted to the ``method of coefficients". This method formally corresponds to using certain properties of the constant term operator in order to lift a summation identity into a generating function algebra. Related to this technique is what Wilf \cite[Ch.~4.3]{Wilf} describes as the ``Snake Oil" method for combinatorial identities. \medskip As an elementary introduction to Omega calculus we prove the simple doublesum identity \begin{eqnarray} \label{simple} \sum_{k=0}^n \sum_{j=0}^k \binom{n }{ j} = 2^n + n\, 2^{n-1}. \end{eqnarray} \noindent \textit{Proof.} Denote by $f(n)$ the doublesum in question and let $F(x)=\sum_{n=0}^{\infty} f(n) x^n$ be the corresponding generating function. We rewrite $F(x)$ in terms of the $\Omegaop$ operator, \begin{eqnarray*} F(x) & = & \sum_{n=0}^{\infty} \sum_{k=0}^{n} \sum_{j=0}^{k} \binom{n }{ j} x^n \\ & = & {\Omegaop} \sum_{n,k,j} \lam^{k-j} \binom{n+k}{ j} x^{n+k} \\ & = & {\Omegaop} \sum_{n,k} (1 + \lam^{-1})^{n+k} \lam^k x^{n+k} \\ & & \hbox{\hskip 1in} \mbox{(by the Binomial Theorem)} \\ & = & \Omegaop \frac{1}{\left(1-x \left(1 +\frac{1}{\lam}\right)\right) (1 - x\lam(1+\frac{1}{\lam}))} \\ & &\hbox{\hskip 1in} \mbox{(by the geometric series)} \\ & = & \frac{1}{(1 - x)^2} \Omegaop \frac{1}{\left(1 - \frac{x}{1-x} \lam^{-1}\right)\left(1 - \frac{x}{1-x}\lam \right)} \\ & = & \frac{1}{(1 - x)^2} \frac{1}{\left(1 - \frac{x}{1-x}\right) \left(1 - \left(\frac{x}{1-x}\right)^2\right)} \\ & & \hbox{\hskip 1in} \mbox{(by (1.2))} \\ & = & \frac{1}{1-2x} + \frac{x}{(1 - 2x)^2}\;. \end{eqnarray*} \noindent From this the closed form evaluation of $f(n)$ is immediate. \hfill\qedsymbol \medskip \noindent This way of using the $\Omegaop$ operator is very close to MacMahon's Partition Analysis. The examples presented below will show that the scope of possible ways to apply this operator is much broader; sometimes certain properties of $\Omegaop$ even lead to surprising extra insight. \medskip Despite the success of the method in these examples, we have to point out that this usage of $\Omegaop$ manipulatorics is non-algorithmic. Today we already have computer programs for the automatic treatment of hypergeometric multisums. For instance, the WZ-engine of of Wilf and Zeilberger \cite{WZ} has been fine-tuned by Wegschaider \cite{Weg}. A more general engine, based on Zeilberger's ``holonomic systems approach to special functions" \cite{Zeil:holo} has been designed by Chyzak \cite{Chyzak}; its underlying mechanism is elimination via Gr\"obner bases methods for non-commutative operator algebras. These computer algebra packages are remarkably powerful for various applications. For instance, see Chyzak's computer proof \cite{Chyzak} of Calkin's identity \eqref{calkin}, or the proofs supplied by Wegschaider's package \cite{Weg} including a fully automatic proof of \eqref{EG}. But still one can observe certain complexity limitations; more detailed remarks on this aspect are to find in Section 5. Therefore manipulation methods like the $\Omegaop$ calculus that we are going to introduce still remain valuable tools in practical problem solving. Another application concerns the possibility that such methods might help to transform a problem into a form that finally can be treated automatically by a computer program. \medskip In Section 2 Omega calculus is applied to derive a new proof of Calkin's identity \eqref{calkin}. It is interesting to observe that the method provides insight into a whole class of such identities as, for instance, identity \eqref{simple}. In Section 3 we treat identities involving derangement numbers ${\D}_n$. Besides proving Callan's identity \eqref{callan}, Partition Analysis reveals its underlying structure and leads to a more general result in a straightforward manner. In Section 4 we show that harmonic number identities also fit into the scope of Partition Analysis. A well-known summation is derived as a corollary from a more general identity which we could not find in the standard literature. Finally in Section 5 we use Partition Analysis to evaluate the doublesum identity \eqref{EG} together with a triplesum companion. As explained by Essam and Guttman \cite{EG} such identities arise in certain physical models. Moreover, it is remarkable that these identities can be obtained as special cases of the Bender-Knuth conjecture which has been proved by Gordon \cite{Gordon} and independently by Andrews \cite{Andrews:PP}. \section{Calkin's Identity} \renewcommand{\theequation}{2.\arabic{equation}} \setcounter{equation}{0} The basis of the application of Partition Analysis in this section lies in the simple observation that for $n = 2$ or $3$, \begin{eqnarray} \label{2.1} \Omegaop \lam D_{\lam} (\lambda^{a_1-a_2} + \lambda^{a_2 - a_3} + \cdots + \lambda^{a_n-a_1}) = \max (a_1,a_2,\dots,a_n) - \min (a_1,a_2,\dots,a_n), \end{eqnarray} where $D_{\lam}$ denotes differentiation with respect to $\lam$. Our object is to provide a new proof of Calkin's intriguing identity \cite{Calkin}: %\setcounter{thm}{1.\arabic{section}} \begin{thm} \begin{equation} \sum_{k=0}^n \left( \sum_{j=0}^k \binom{n}{ j} \right)^3 = \frac{n}{2}\; 8^n + 8^n - \frac{3n}{4}\; 2^n \binom{2n}{ n}\;. \label{2.2} \end{equation} \end{thm} \begin{proof} We begin by defining \begin{equation} M(n) = \sum_{k_1,k_2,k_3 \geq 0} \binom{n }{ k_1} \binom{n}{ k_2} \binom{n}{ k_3} \max (k_1,k_2,k_3) \label{2.3} \end{equation} and \begin{equation} m(n) = \sum_{k_1,k_2,k_3 \geq 0} \binom{n }{ k_1} \binom{n}{ k_2} \binom{n}{ k_3} \min (k_1,k_2,k_3)\,. \label{2.4} \end{equation} Next we note that \begin{eqnarray} & & \sum_{k=0}^n \left( \sum_{j=0}^k \binom{n}{ j}\right)^3 \nonumber \\ & = & \sum_{k=0}^n \sum_{n\geq k_1,k_2,k_3 \geq 0} \binom{n }{ k_1} \binom{n}{ k_2} \binom{n}{ k_3} \nonumber \\ & = & \sum_{n\geq k_1,k_2,k_3 \geq 0} \binom{n }{ k_1} \binom{n}{ k_2} \binom{n}{ k_3} \sum_{k=\max(k_1,k_2,k_3)}^n 1 \nonumber \\ & = & \sum_{n\geq k_1,k_2,k_3 \geq 0} \binom{n }{ k_1} \binom{n}{ k_2} \binom{n}{ k_3} (n - \max (k_1,k_2,k_3) + 1) \nonumber \\ & = & (n+1) 8^n - M(n)\,. \label{2.5} \end{eqnarray} So to prove Calkin's identity we only need to prove that \begin{equation} M(n) = \fr{n}{2}\; 8^n + \fr{3n}{4} \; 2^n \binom{2n }{ n}\,. \label{2.6} \end{equation} To achieve this we note that \begin{eqnarray} M(n) & = & \sum_{n\geq k_1,k_2,k_3 \geq 0} \binom{n }{ k_1} \binom{n}{ k_2} \binom{n}{ k_3} \max (n-k_1,n-k_2,n-k_3) \nonumber \\ & = & \sum_{n\geq k_1,k_2,k_3 \geq 0} \binom{n }{ k_1} \binom{n}{ k_2} \binom{n}{ k_3} (n - \min (k_1,k_2,k_3)) \nonumber \\ & = & n \,8^n - m(n)\,. \label{2.7} \end{eqnarray} In addition, using \eqref{2.1} we find that \begin{eqnarray} M(n) & - & m(n) \nonumber \\ & = & \sum_{n\geq k_1,k_2,k_3 \geq 0} \binom{n }{ k_1} \binom{n}{ k_2} \binom{n}{ k_3} (\max (k_1,k_2,k_3) - \min (k_1,k_2,k_3)) \nonumber \\ & = & \Omegaop \lam D_{\lam} \sum_{n\geq k_1,k_2,k_3 \geq 0} \binom{n }{ k_1} \binom{n}{ k_2} \binom{n}{ k_3} (\lam^{k_1-k_2} + \lam^{k_2-k_3} + \lam^{k_3-k_1}) \nonumber \\ & = & 3 \cdot 2^n\, \Omegaop \lam\,D_{\lam} (1 + \lam)^n (1 + \lam^{-1})^n \nonumber \\ & = & -3 \cdot 2^n n\, \Omegaop (1 - \lambda) \lambda^{-n} (1 + \lambda)^{2n-1} \nonumber \\ & = & -3 \cdot 2^n n \left( \sum_{j=n}^{2n-1} \binom{2n-1}{ j} - \sum_{j=n-1}^{2n-1} \binom{2n-1 }{ j} \right) \nonumber \\ & = & 3 \cdot 2^n n \binom{2n-1}{ n-1} = \fr32 \;2^n n \binom{2n}{ n}\,. \label{2.8} \end{eqnarray} Eliminating $m(n)$ from these two identities, we find that \begin{equation} M(n) = \fr{n 8^n}{2} + \fr34\;n\,2^n \binom{2n}{ n}\,, \label{2.9} \end{equation} which proves our theorem. \end{proof} \begin{rem} When we computed $M(n)-m(n)$ we met the problem of evaluating the expression $\Omegaop(1-\lam) \lam^{-n} (1+\lam^{-1})^n$. In Section 5 we will see that this is typical for such kind of $\Omegaop$ applications; compare in particular Lemma \ref{Simple diff}. \end{rem} Unfortunately our Partition Analysis representation of $$\max (a_1,\dots,a_n) - \min (a_1,\dots,a_n)$$ is not valid for $n > 3$. Consequently, we cannot expect similarly nice results for \[ \sum_{k=0}^n \left(\sum_{j=0}^k \binom{n}{ j}\right)^m \] when $m > 3$. Of course, the same method can be used to prove easily that \[ \sum_{k=0}^n \left(\sum_{j=0}^k \binom{n}{ j}\right)^2 = \fr{n\,4^n}{2} + 4^n - \fr{n}{2} \binom{2n}{ n}\,. \] \section{Derangement Numbers} \renewcommand{\theequation}{3.\arabic{equation}} \setcounter{equation}{0} The derangement numbers, ${\D}_n$, are well-known in combinatorics. ${\D}_n$ is the number of permutations of $n$ letters without fixed points, and, in fact, \begin{equation} {\D}_n = n! \sum_{j=0}^n \fr{(-1)^j}{j!}\;. \label{3.1} \end{equation} So we see immediately that \begin{eqnarray} {\D}_n & = & \Omegage n! \lam^n \sum_{j=0}^{\infty} \fr{(-1)^j\lam^{-j}}{j!} \nonumber \\ & = & n!\, \Omegaop \lambda^n e^{-\fr1{\lam}}\,. \label{3.2} \end{eqnarray} To illustrate the utility of Partition Analysis in treating derangement number problems, we shall consider an identity of David Callan \cite{Callan}: \begin{equation} \sum_{j=0}^k \binom{k}{ j} {\D}_{k+n-j} = k! \sum_{j=0}^{\min(n,k)} \binom{k}{ j} \binom{k+n-j}{ k} {\D}_{n-j}\,. \label{3.3} \end{equation} Partition Analysis applied to each side of this identity leads us to a much stronger and more surprising result. \begin{thm} For any $N \geq n - k$, \begin{eqnarray} \sum_{j\geqq 0} \binom{k}{ j} \fr{(k+n-j)!}{(k + N-j)!} {\D}_{k+N-j} & = &(-1)^n \sum_{j=0}^n (-1)^j \binom{n}{ j}(j + k)! \\ (& = &(-1)^n k!\; _2 F_0(-n,k+1;1)\, \, \, \, \, )\,. \nonumber \label{3.4} \end{eqnarray} \end{thm} \begin{rem} The left-hand side of the above identity is the left-hand side of Callan's identity when $N = n$ and the right-hand side of Callan's identity when $N = n-k$. Since the right-hand side of the above identity is independent of $N$, we see that Callan' identity is a direct consequence of our theorem. \end{rem} \begin{lem} \label{L3.1} For nonnegative integers $n$ and $k$, \begin{equation} D_{\lam}^n \lam^{k+n} e^{\fr1{\lam}} = \sum_{j=k-n}^k c(k,n,j) \lam^j e^{\fr1{\lam}}\,, \label{3.5} \end{equation} where \begin{equation} c(k,n,j) = (-1)^{k+j} \binom{n}{ k-j} \fr{(j+n)!}{k!}\;. \label{3.6} \end{equation} \end{lem} \begin{proof} For $n =0$ we see immediately that $c(k,0,k) = 1$. For $n =1$, \begin{equation} D_{\lam} \lam^{k+1} e^{\fr1{\lambda}} = (k+1) \lam^k e^{\fr1{\lam}} - \lam^{k-1} e^{\fr1{\lam}}\,, \label{3.7} \end{equation} so $c(k,1,k-1) = -1$ and $c(k,1,k) = k+1$. Hence our Lemma is true for $n = 0$ and $1$. We now proceed by mathematical induction. \begin{eqnarray} D_{\lam}^{n+1} \lam^{k+n+1} e^{\fr1{\lam}} & = & D_{\lam}^n (D_{\lam} \lam^{k+n+1} e^{\fr1{\lam}}) \nonumber \\ & = & D_{\lam}^n ((k+n+1) \lam^{k+n} e^{\fr1{\lam}} - \lam^{k+n-1} e^{\fr1{\lam}}) \nonumber \\ & = & (k + n+1) \sum_{j=k-n}^k c(k,n,j) \lam^j e^{\fr1{\lam}} - \sum_{j=k-1-n}^{k-1} c(k-1,n,j) \lam^j e^{\fr1{\lam}} \label{3.8} \end{eqnarray} For this last expression, in order to equal \begin{equation} \sum_{j=k-(n+1)}^k c(k,n+1,j) \lam^j e^{\fr1{\lam}}\,, \label{3.9} \end{equation} we must have \begin{equation} c(k,n+1,j) = \left\{ \begin{array}{ll} (k + n + 1) c (k,n,k), & \mbox{ if } j = k, \\ (k + n + 1) c (k,n,j) - c(k - 1,n,j), & \mbox{ if } k - n \leq j < k, \\ -c(k-1,n,k-1-n), & \mbox{ if } j = k - n - 1. \end{array} \right. \label{3.10} \end{equation} It is a matter of simple algebra to show that $(-1)^{k+j} \binom{n}{ k-j}(j+n)!/k!$ satisfies these defining recurrences and initial conditions. This shows that \begin{equation} c(k,n,j) = (-1)^{k+j} \binom{n}{ k-j} \fr{(j+n)!}{k!} \label{3.11} \end{equation} and proves Lemma 3.1. \end{proof} \noindent \textit{Proof of Theorem 3.1}. First we note that \begin{eqnarray} k! \sum_{j=k-n}^k c(k,n,j) & = & (-1)^k \sum_{j=k-n}^k (-1)^j \binom{n}{ k-j} (j + n)! \nonumber \\ & = & (-1)^n \sum_{j=0}^n (-1)^j \binom{n}{ j} (j + k)!\,, \label{3.12} \end{eqnarray} which is the right-hand side of the identity in our theorem. Finally, using \eqref{3.2} and Lemma \ref{L3.1}, for $N \geqq n - k$ we obtain, \begin{eqnarray} & & \sum_{j\geqq 0} \binom{k}{ j} \fr{(k + n - j)!}{(k + N-j)!}\;{\D}_{k+N-j} \nonumber \\ & = & \sum_{j\geqq 0} \binom{k}{ j} \fr{(k + n - j)!}{(k + N-j)!}\;(k + N-j)!\, \Omegaop \lambda^{k+N-j} e^{-\fr1{\lam}} \nonumber \\ & = & k!\, \Omegaop e^{-\fr1{\lam}} \lam^N \sum_{j\geqq 0} \fr{(k+n-j)!}{(k-j)!\, j!} \;\lambda^{k-j} \nonumber \\ & = & k!\, \Omegaop e^{-\fr1{\lam}} \lam^N D_{\lam}^n \sum_{j\geqq 0}^{\infty} \fr{\lam^{k+n-j}}{j!} \nonumber \\ & = & k!\, \Omegaop e^{-\fr1{\lam}} \lam^N D_{\lam}^n \lam^{k+n} e^{\fr1{\lam}} \nonumber \\ & = & k!\, \Omegaop e^{-\fr1{\lam}} \lam^N \sum_{j=k-n}^k c(k,n,j) \lam^j e^{\fr1{\lam}} \nonumber \\ & = & k!\, \Omegaop \sum_{j=k-n}^k c(k,n,j)\lam^{N+j} \nonumber \\ & = & k!\, \sum_{j=k-n}^k c(k,n,j) \label{3.13} \end{eqnarray} because $N \geqq n - k$. The discovery of this result was quite straightforward using Partition Analysis. Each side of Callan's identity was represented in Partition Analysis, and each side came out to the final lines of the proof of our theorem first with $N = n$ then with $N = n-k$. Once that was observed, it was clear that any $N \geqq n - k$ would produce the same result. While Lemma 3.1 was found to be the necessary element in the proof, it was only upon examination of the $c(k,n,j)$ that we observed the closed form for them. \section{Harmonic Numbers} \renewcommand{\theequation}{4.\arabic{equation}} \setcounter{equation}{0} Previously \cite{AU:IC} harmonic number identities have been reduced to binomial coefficient or hypergeometric series identities by means of the operator identity \begin{equation} \delta \binom{x+n }{ n} = \sum_{j=1}^n \fr1{j} = H_n\,, \label{4.1} \end{equation} where \begin{equation} \delta\,f(x) = f'(0)\,. \label{4.2} \end{equation} In terms of Partition Analysis we may write \begin{eqnarray} H_n & = & \Omegaop \lam^n \sum_{j=1}^{\infty} \fr{\lam^{-j}}{j} \nonumber \\ & = & - \Omegaop \lam^n \log (1 - \fr1{\lam})\,. \end{eqnarray} We suspected that the previous treatment via operators would be replicated by Partition Analysis. Again we were surprised. We chose as a test case the identity [18; p. 14] \begin{equation} \sum_{k=0}^n \binom{k}{ m} H_k = \binom{n+1}{ m+1} \left(H_{n+1} - \fr1{m+1}\right) \label{4.4} \end{equation} Our attempt to prove this wound up proving instead: \begin{thm} \begin{equation} \sum_{k=0}^n \binom{k}{ m} (H_k - H_{n-k}) = \binom{n+1}{ m+1} H_m\,. \label{4.5} \end{equation} \end{thm} \begin{proof} As suggested, we start with \begin{eqnarray} \sum_{k=0}^n \binom{k}{ m} H_k & = & \Omegaop \sum_{k\geq 0} \lam^{n-k} \binom{k}{ m} \delta \binom{x+k}{ k} \nonumber \\ & = & \delta \Omegaop \lam^n \sum_{k\geq 0} \lam^{-k} \binom{x+k}{ k-m} \binom{x+m}{ m} \nonumber \\ & = & \delta \Omegaop \lam^n \binom{x+m}{ m}\sum_{k\geq 0} \lam^{-k-m} \binom{x+k+m}{ k} \nonumber \\ & = & \delta \Omegaop \lam^n \binom{x+m}{ m} \lam^{-m} (1 - \lam^{-1})^{-x-m-1} \nonumber \\ & = & \Omegaop \lam^{n-m} (-(1-\lam^{-1})^{-m-1} \log (1 - \lam^{-1}) + (1 - \lam^{-1})^{-m-1}H_m) \nonumber \\ & = & \Omegaop \left( - \sum_{j=0}^{\infty} \binom{m+j}{ j} \lam^{n-m-j} \log (1 - \lam^{-1}) + \sum_{j=0}^{\infty} \binom{m+j}{ j} \lam^{n-m-j} H_m \right) \nonumber \\ & = & \sum_{j=0}^{n-m} \binom{m+j}{ j} H_{n-m-j} + H_m \sum_{j=0}^{n-m} \binom{m+j}{ j} \nonumber \\ & = & \sum_{k=0}^n \binom{k}{ m} H_{n-k} + H_m \binom{n+1}{ m+1} \,, \label{4.6} \end{eqnarray} which proves our Theorem 4.1. \end{proof} \begin{cor} \begin{equation} \sum_{k=0}^n \binom{k}{ m} H_{n-k} = \binom{n+1}{ m+1} (H_{n+1} - H_{m+1} )\,. \label{4.7} \end{equation} \end{cor} \begin{proof} This follows immediately from (4.4) and (4.5) once we note that \[ H_m + \fr1{m+1} = H_{m+1}\,. \] \end{proof} \section{An Example from Physics} \renewcommand{\theequation}{5.\arabic{equation}} \setcounter{equation}{0} In \cite{EG} Essam and Guttmann considered configurations of $p$ vicious random walkers on a multi-dimensional lattice. The problem of vicious walkers finds many physical applications, for instance, in the context of Brownian motion or of directed polymer networks. For an introduction to fundamental results and examples, Essam and Guttmann refer to Fisher \cite{Fisher}. In \cite{EG} they were able to express the generating functions for the number of such configurations in terms of (generalized) hypergeometric functions. In particular, they found a hypergeometric multisum expression for the number $S_n(p)$ of configurations that combinatorially can be described, e.g., as the number of ``brushes of mutually avoiding hairs" of length $n$. Namely, \begin{eqnarray} \label{brushes} S_n(p) = \sum_{0\leq q_1 \leq \dots \leq q_p \leq n} w_n(q_1,\ldots,q_p), \end{eqnarray} where \begin{eqnarray} \label{w def} w_n(q_1,\ldots,q_p) = \prod_{1\leq i