%-----------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 <j \leq p} (q_j-q_i+j-i) \prod_{j=1}^p \frac{(n+p-j)!}{(q_j+j-1)!\,
(n-q_j+p-j)!}.
\end{eqnarray}

In the trivial case $p=1$ one has $S_n(1)=2^n$. The next cases are slightly more involved, for instance,
$S_n(2)=\binom{2n+1}{ n}$ and $S_n(3)=\frac{2^{n+1}}{n+2} \binom{2n+1}{ n}$. But, as remarked by Essam and
Guttmann, ``a clear pattern emerges", which led them to conjecture that
\begin{eqnarray} \label{conj}
S_n(p) = 2^{p n} \prod_{j=1}^p \frac{((j+1)/2)_n}{(j)_n}.
\end{eqnarray}
Here we use the Pochhammer symbol $(x)_n=x(x+1)\ldots (x+n-1)$.

This closed form representation indepently has been conjectured by Arrowsmith et al.\ \cite{Arrow}. Finally, as
described by Arrowsmith and Essam \cite{AE}, it turned out, as an observation of Krattenthaler, that \eqref{conj}
can be obtained from the Bender-Knuth conjecture for the specialization $q\rightarrow 1$. As mentioned above this
conjecture is now a theorem, but the proofs (e.g. Gordon \cite{Gordon} or Andrews \cite{Andrews:PP}) are far from
being trivial. Therefore our motivation to look at this problem is guided by the question whether there are
possible ways to derive the multisum evaluations via elementary $\Omegaop$-manipulatorics.

Actually the idea of applying Partition Analysis to the multisum in \eqref{brushes} is a very natural one since the
inequality constraints on the summation parameters $q_i$ just invite to do so.


\subsection{The case $\boldsymbol{p=2}$}

We reformulate the case $p=2$ of \eqref{brushes} as follows:

\begin{prop} \label{prop2}
For any nonnegative integer $n$:
\begin{align}
S_n(2) & = \sum_{k_1} \sum_{k_2\leq k_1} \frac{k_1-k_2}{n+1} \binom{n+1}{ k_1} \binom{n+1}{ k_2} \label{prop2 1}\\
& = \binom{2n+1}{ n}. \label{prop2 2}
\end{align}
\end{prop}

The doublesum representation \eqref{prop2 1} is immediate from \eqref{brushes}. In order to compute the evaluation
\eqref{prop2 2} we introduce a lemma that serves as a standard tool in applications of this kind. (Cf., for
instance, the proof of \eqref{2.8}.) It concerns a ``difference property" of the factor $\lam - 1$ which enables
the reduction of an $\Omegaop$ expression to a simpler ``coefficient-of'' operation designated by $\langle \
\rangle$.

\begin{lem} \label{Simple diff}
Let $f(\lam)$ be a Laurent polynomial over the complex numbers, in short, $f(\lam)\in \mathbb{C}[\lam,\lam^{-1}]$.
Then for any integer $\alpha$:
\begin{eqnarray} \label{simple diff}
\Omegaop \, (\lam -1) \lam^{-\alpha} f(\lam)= \langle \lam^{\alpha -1}\rangle\, f(\lam).
\end{eqnarray}
\end{lem}

\noindent \textit{Proof.} Let $f(\lam)=\sum_k f_k \lam^k$ then the left hand side of \eqref{simple diff} equals
\[
\Omegaop \sum_k f_k \lam^{k-\alpha+1} - \Omegaop \sum_k f_k \lam^{k-\alpha}= \sum_{k\geq \alpha-1} f_k -
\sum_{k\geq \alpha} f_k = f_{\alpha -1}.
\]
\hfill\qedsymbol

\medskip
Now we are able to evaluate the doublesum.

\noindent \textit{Proof of Proposition \ref{prop2}.} Let $D_\lam$ denote the derivation operator with respect to
$\lam$. We rewrite the doublesum in \eqref{prop2 1} as
\begin{align*}
S_n(2) & = \frac{1}{n+1}\, \Omegaop \sum_{k_1, k_2} \lam^{k_1-k_2} (k_1-k_2) \binom{n+1}{ k_1} \binom{n+1}{ k_2} \\
& = \frac{1}{n+1}\, \Omegaop \, \lam  D_{\lam} \sum_{k_1,k_2} \lam^{k_1-k_2} \binom{n+1}{ k_1} \binom{n+1}{ k_2}\\
& = \frac{1}{n+1}\, \Omegaop \, \lam D_\lam (1+\lam)^{n+1} \bigl(1+\frac{1}{\lam} \bigr)^{n+1} = \frac{1}{n+1}\,
\Omegaop \, \lam D_\lam \frac{(1+\lam)^{2n+2}}{\lam^{n+1}} \\ & = \frac{1}{n+1}\, \Omegaop
\frac{(2n+2)(1+\lam)^{2n+1} \lam^{n+1}-(1+\lam)^{2n+2} (n+1) \lam^n}
              { \lam^{2n+1} } \\
& =\Omegaop \, (\lam -1) \frac{(1+\lam)^{2n+1}}{\lam^{n+1}} = \langle \lam^{n} \rangle \, (1+\lam)^{2n+1} =
\binom{2n+1}{ n},
\end{align*}
where in last line we used Lemma \ref{Simple diff}. \hfill\qedsymbol


\subsection{The case $\boldsymbol{p=3}$}

Similar to the case $p=2$ we can treat the case $p=3$ of \eqref{brushes} which we state as follows:

\begin{prop} \label{prop3}
For any nonnegative integer $n$:
\begin{align}
S_n(3) & = \sum_{k_1} \sum_{k_2\leq k_1} \sum_{k_3\leq k_2} \frac{(k_1-k_2)(k_2-k_3)(k_1-k_3)}{(n+2)^2(n+1)}
\binom{n+2}{ k_1} \binom{n+2}{ k_2} \binom{n+2 }{ k_3}\label{prop3 1}\\ & = \frac{2^{n+1}}{n+2}\binom{2n+1}{ n}.
\label{prop3 2}
\end{align}
\end{prop}
\noindent Again the verification of equality \eqref{prop3 1} is immediate from the presentation \eqref{brushes}. As
the next step we derive a $\Omegaop$-presentation of the triple sum.

In the following we will often use $\lam$ and $\mu$ instead of the ``standard" $\Omegaop$-variables $\lam_1$ and
$\lam_2$.

\begin{lem} \label{Omega rep}
For any nonnegative integer $n$:
\begin{eqnarray} \label{omega rep}
S_n(3) = \Omegaop\, (\lam \mu -1)(\lam - \mu^2)(\mu -\lam^2) \frac{(1+\lam)^n (\lam+\mu)^n (1+\mu)^n}
     {\lam^{n+2} \mu^{n+2}}.
\end{eqnarray}
\end{lem}

\noindent \textit{Proof.} Let $D_i$ denote the derivation operator with respect to $\lam_i$, $i\in \{1,2,3\}$. We
rewrite the triplesum in \eqref{prop3 1} as
\begin{align*}
& S_n(3) = \\
& = \Omegaop \sum_{k_1,k_2,k_3} \lam_1^{k_1-k_2} \lam_2^{k_2-k_3} \lam_3^{k_1-k_3} \frac{(k_1-k_2)
(k_2-k_3) (k_1-k_3)}{(n+2)^2 (n+1)} \binom{n+2}{ k_1} \binom{n+2}{ k_2} \binom{n+2}{ k_3} \\ & = \Omegaop \, \lam_1
\lam_2 \lam_3 D_1 D_2 D_3 \sum_{k_1,k_2,k_3} \frac{\lam_1^{k_1-k_2} \lam_2^{k_2-k_3} \lam_3^{k_1-k_3}} {(n+2)^2
(n+1)} \binom{n+2}{ k_1} \binom{n+2}{ k_2} \binom{n+2}{ k_3} \\ & = \Omegaop \, \lam_1 \lam_2 \lam_3 D_1 D_2 D_3
(1+\lam_1 \lam_3)^{n+2} \bigl(1+\frac{\lam_2}{\lam_1}\bigr)^{n+2} \bigl(1+\frac{1}{\lam_2
\lam_3}\bigr)^{n+2}/((n+2)^2 (n+1))
\\ & = \Omegaop\, \frac{(\lam_1 \lam_2 \lam_3^2 -1)(\lam_2-\lam_1^2 \lam_3) (\lam_1-\lam_2^2 \lam_3)}{(\lam_1
\lam_2 \lam_3)^2} (1+\lam_1 \lam_3)^{n} \bigl(1+\frac{\lam_2}{\lam_1}\bigr)^{n} \bigl(1+\frac{1}{\lam_2
\lam_3}\bigr)^{n}.
\end{align*}
If we now replace $\lam_1 \lam_3$ by $\lam$, and $\lam_2 \lam_3$ by $\mu$ we obtain the expression in \eqref{omega
rep}. \hfill\qedsymbol

\medskip
For the evaluation of the $\Omegaop$-presentation we need a generalization of Lemma \ref{Simple diff}.

\begin{lem} \label{Multiple diff}
Let $f(\lam,\mu)\in \mathbb{C}[\lam,\lam^{-1},\mu,\mu^{-1}]$. Then for any pair of integers $\alpha$ and $\beta$:
\begin{align} \label{multiple diff}
\Omegaop & (\lam \mu-1) \lam^{-\alpha} \mu^{-\beta}f(\lam,\mu) = \nonumber\\ &\langle \lam^{\alpha -1}
\mu^{\beta-1} \rangle\, f(\lam,\mu)+ \sum_{i \geq \alpha} \langle \lam^{i} \mu^{\beta-1} \rangle\, f(\lam,\mu) +
\sum_{j \geq \beta} \langle \lam^{\alpha -1} \mu^{j} \rangle\, f(\lam,\mu).
\end{align}
\end{lem}

\noindent \textit{Proof.} Let $f(\lam,\mu)=\sum_{i,j} f_{i,j} \lam^i \mu^j$ and let the $\Omegaop$ operator act on
$\lam$ and $\mu$. The left hand side of \eqref{multiple diff} equals
\begin{align*}
& \Omegaop \sum_{i,j} f_{i,j} \lam^{i-\alpha+1} \mu^{j-\beta+1}- \Omegaop \sum_{i,j} f_{i,j} \lam^{i -\alpha}
\mu^{j-\beta} =\\ & \sum_{i\geq \alpha-1} \sum_{j\geq \beta-1}f_{i,j} - \sum_{i\geq \alpha} \sum_{j\geq
\beta}f_{i,j}= f_{\alpha -1,\beta-1}+\sum_{i\geq \alpha} f_{i,\beta-1}+ \sum_{j\geq \beta} f_{\alpha-1,j}.
\end{align*}
\hfill\qedsymbol

\medskip
The following corollary is an immediate consequence.
\begin{cor} \label{Cor}
Let $f(\lam,\mu)\in {\bf C}[\lam,\lam^{-1},\mu,\mu^{-1}]$ be symmetric, i.e., $f(\lam,\mu)=f(\mu,\lam)$. Then for
any integer $\alpha$:
\[
\Omegaop\, (\lam \mu-1) \lam^{-\alpha} \mu^{-\alpha}f(\lam,\mu) = \langle \lam^{\alpha -1} \mu^{\alpha-1} \rangle\,
f(\lam,\mu)+ 2\, \sum_{i \geq \alpha} \langle \lam^{i} \mu^{\alpha-1} \rangle\, f(\lam,\mu).
\]
\end{cor}

\medskip
Symmetric Laurent polynomials satisfy another useful property.
\begin{lem} \label{After cor}
Let $f(\lam,\mu)\in {\bf C}[\lam,\lam^{-1},\mu,\mu^{-1}]$ be such that $f(\lam,\mu)=f(\mu,\lam)$, then for any
univariate Laurent polynomial $g$:
\[
\Omegaop\, f(\lam,\mu) g(\lam) = \Omegaop\, f(\lam,\mu) g(\mu).
\]
\end{lem}

\noindent \textit{Proof.} Let $f(\lam,\mu)=\sum_{i,j} f_{i,j} \lam^i \mu^j$. The operator $\Omegaop$ is linear,
hence it suffices to prove the lemma for $g(\lam)=\lam^{-\alpha}$ where $\alpha$ is an arbitrary integer:
\begin{align*}
\Omegaop\, f(\lam,\mu) \lam^{-\alpha} & = \Omegaop \sum_{i,j} f_{i,j} \lam^{i-\alpha} \mu^j = \sum_{i\geq \alpha}
\sum_j f_{i,j} \\ & = \sum_{i\geq \alpha} \sum_j f_{j,i} = \sum_{i} \sum_{j\geq \alpha} f_{i,j} = \Omegaop
\sum_{i,j} f_{i,j} \lam^i \mu^{j-\alpha}.
\end{align*}
\hfill\qedsymbol

\medskip
After this preparatory work which essentially exhibits some elementary properties of the $\Omegaop$ operator, we
state another lemma which is convenient to introduce for technical reasons.

\begin{lem} \label{Powers}
For nonnegative integers $\alpha, \beta, a, b$, and $c$:
\begin{eqnarray} \label{powers}
\langle \lam^\alpha \mu^\beta \rangle\, (1+\lam)^a (\lam + \mu)^b (1+\mu)^c = \sum_i \binom{a}{ i} \binom{b}{
\alpha -i} \binom{c}{ \alpha + \beta -b -i}.
\end{eqnarray}
\end{lem}

\noindent \textit{Proof.} The left hand side of \eqref{powers} equals
\[
\langle \lam^\alpha \mu^\beta \rangle \sum_{i,j,k} \binom{a}{ i} \binom{b}{ j} \binom{c}{ k} \lam^{i+j}
\mu^{b-j+k}.
\]
Hence the lemma follows by rewriting the equations $i+j=\alpha$ and $b-j+k=\beta$ as $j=\alpha -i$ and $k=\beta - b
+\alpha -i$. \hfill\qedsymbol

\medskip
Now we are in the position to prove Proposition \ref{prop3}.

\noindent \textit{Proof of Proposition \ref{prop3}.} Let $p_n(\lam,\mu)=(1+\lam)^n (\lam + \mu)^n (1+\mu)^n$. By
Lemma \ref{Omega rep},
\begin{align*}
S_n(3) & = \Omegaop\, \frac{(\lam \mu -1)(\lam-\mu^2)(\mu-\lam^2)} {\lam^{n+2} \mu^{n+2}} p_n(\lam,\mu) \\ & =
\Omegaop\, (\lam \mu -1) \lam^{-n} \mu^{-n} p_n(\lam,\mu)+ \Omegaop\, (\lam \mu -1) \lam^{-(n+1)} \mu^{-(n+1)}
p_n(\lam,\mu)\\ &- \Omegaop\, (\lam \mu -1) \lam^{-(n-1)} \mu^{-(n+2)} p_n(\lam,\mu)- \Omegaop\, (\lam \mu -1)
\lam^{-(n+2)} \mu^{-(n-1)} p_n(\lam,\mu)\\ & =\Omegaop\, (\lam \mu -1) \lam^{-n} \mu^{-n} p_n(\lam,\mu)+ \Omegaop\,
(\lam \mu -1) \lam^{-(n+1)} \mu^{-(n+1)} p_n(\lam,\mu)\\ & - 2\, \Omegaop\, (\lam \mu -1) \lam^{-(n-1)}
\mu^{-(n+2)} p_n(\lam,\mu).
\end{align*}
\noindent The last equality is by Lemma \ref{After cor}. In the next step we apply Lemma \ref{Multiple diff} and
Corollary \ref{Cor}, respectively, and obtain
\[
S_n(3)=a_n+b_n-2\, c_n + 2(A_n+B_n-C_n^{(1)}-C_n^{(2)})
\]
where
\begin{align*}
& a_n=\langle \lam^{n-1} \mu^{n-1} \rangle \, p_n(\lam,\mu),\, \, b_n=\langle \lam^{n} \mu^{n} \rangle \,
p_n(\lam,\mu),\, \, c_n=\langle \lam^{n-2} \mu^{n+1} \rangle \, p_n(\lam,\mu),\\ & A_n = \sum_{i\geq n} \langle
\lam^i \mu^{n-1}\rangle\,  p_n(\lam,\mu),\, \, B_n = \sum_{i\geq n+1} \langle \lam^i \mu^{n} \rangle \,
p_n(\lam,\mu) \hbox{\ \ \ and}\\ & C_n^{(1)} = \sum_{i\geq n-1} \langle \lam^i \mu^{n+1} \rangle \,
p_n(\lam,\mu),\, \, C_n^{(2)} = \sum_{j\geq n+2} \langle \lam^{n-2} \mu^{j}\rangle \, p_n(\lam,\mu).
\end{align*}

\noindent By Lemma \ref{Powers}, with $a=b=c=n$, we have,
\[
a_n=\sum_i \binom{n}{ i} \binom{n}{ i+1} \binom{n}{ i+2},\, \, b_n=\sum_i \binom{n}{ i}^3 \hbox{\ \ and \ \ }
c_n=a_n.
\]
Again by Lemma \ref{Powers}, with $a=b=c=n$, we have,
\begin{align*}
& A_n=\sum_{j\geq n}\sum_i \binom{n}{ i} \binom{n}{ j-i} \binom{n}{ j-i-1},\, \, B_n=\sum_{j\geq n+1} \sum_i
\binom{n}{ i} \binom{n}{ j-i}^2,\\ & C_n^{(1)}=\sum_{j\geq n-1}\sum_i \binom{n}{ i} \binom{n}{ j-i} \binom{n}{
j-i+1} =A_n \hbox{\ \ and \ \ } \\ & C_n^{(2)}=\sum_{j\geq n+2}\sum_i \binom{n}{ i} \binom{n}{ i+2} \binom{n}{
j-i-2}.
\end{align*}
\noindent Summarizing, the application of the $\Omegaop$ operator results in the reduction of the triplesum problem
into one involving a linear combination of single- and double-sums, namely
\begin{eqnarray*}
S_n(3)= b_n-a_n + 2(B_n-C_n^{(2)}).
\end{eqnarray*}
\noindent Finally we observe that
\begin{eqnarray} \label{Bn}
2\, B_n = 2^n \binom{2n}{ n} - b_n
\end{eqnarray}
\noindent and
\begin{eqnarray} \label{Cn}
2\, C_n^{(2)} = 2^n \binom{2n}{ n-2} - a_n,
\end{eqnarray}
which gives
\[
S_n(3)=2^n \binom{2n}{ n} - 2^n \binom{2n}{ n-2} = \frac{2^{n+1}}{n+2} \binom{2n+1}{ n}.
\]

First we prove relation \eqref{Bn}. To this end we evaluate a variation of the doublesum representation for $B_n$.
Namely, after dropping the condition on the summation parameter $j$ we obtain by Vandermonde's formula,
\[
\sum_j \sum_i \binom{n}{ i} \binom{n}{ j-i}^2= \sum_i \binom{n}{ i} \sum_j  \binom{n}{ j}^2= \binom{2n}{ n} \sum_i
\binom{n}{ i} = 2^n \binom{2n}{ n}.
\]
\noindent In addition, we observe that
\begin{eqnarray} \label{star}
\sum_{j\leq n} \sum_i \binom{n}{ i} \binom{n}{ j-i}^2 = \sum_{j\geq n} \sum_i \binom{n}{ i} \binom{n}{ j-i}^2.
\end{eqnarray}
\noindent This is verified by applying to the left hand side the summation parameter transform $j\rightarrow 2n-j$,
i.e.,
\[
\sum_{j\leq n} \sum_i \binom{n}{ i} \binom{n}{ j-i}^2 = \sum_{j\geq n} \sum_i \binom{n}{ i} \binom{n}{ 2n-j-i}^2.
\]
Then after $i\rightarrow n-i$ we arrive at the right hand side of \eqref{star}. Finally we combine all this in
order to obtain \eqref{Bn}:
\begin{align*}
2^n \binom{2n}{ n} & = \Bigl( \sum_{j\leq n}+\sum_{j\geq n+1} \Bigr) \sum_i \binom{n}{ i} \binom{n}{ j-i}^2\\ & =
\sum_{j\geq n} \sum_i \binom{n}{ i} \binom{n}{ j-i}^2 + B_n= 2\, B_n + b_n.
\end{align*}

The proof of relation \eqref{Cn} is completely analogous. Dropping the condition on the summation parameter $j$
gives,
\[
\sum_j \sum_i \binom{n}{ i} \binom{n}{ i+2} \binom{n}{ j-i-2}= \sum_i \binom{n}{ i} \binom{n}{ i+2}\sum_j
\binom{n}{ j}= 2^n \binom{2n}{ n-2},
\]
where we used again Vandermonde's formula. The analogue to identity \eqref{star} reads as
\begin{eqnarray} \label{star star}
\sum_{j\leq n+1} \sum_i \binom{n}{ i} \binom{n}{ i+2} \binom{n}{ j-i-2} = \sum_{j\geq n+1} \sum_i \binom{n}{ i}
\binom{n}{ i+2} \binom{n}{ j-i-2}.
\end{eqnarray}
\noindent For the proof we apply $j\rightarrow 2n+2-j$ to the left hand side, i.e.,
\[
\sum_{j\leq n+1} \sum_i \binom{n}{ i} \binom{n}{ i+2} \binom{n}{ j-i-2} = \sum_{j\geq n+1} \sum_i \binom{n}{ i}
\binom{n}{ i+2} \binom{n}{ 2n-j-i}.
\]
Then after $i\rightarrow n-i-2$ we arrive at the right hand side of \eqref{star star}. Finally we obtain \eqref{Cn}
as follows:
\begin{align*}
2^n \binom{2n}{ n-2} & = \Bigl( \sum_{j\leq n+1}+\sum_{j\geq n+2} \Bigr) \sum_i \binom{n}{ i} \binom{n}{ i+2}
\binom{n}{ j-i-2}\\ & = \sum_{j\geq n+1} \sum_i \binom{n}{ i} \binom{n}{ i+2} \binom{n}{ j-i-2} + C_n^{(2)}= 2\,
C_n^{(2)} + a_n.
\end{align*}
\noindent This completes the proof of Proposition \ref{prop3}. \hfill\qedsymbol


\subsection{Remarks on the general case}

Weschaider \cite[Ch.~5.6]{Weg} has derived quite different proofs for the Propositions \ref{prop2} and \ref{prop3}.
These proofs are based on his Mathematica package MULTISUM which is an implementation of Wegschaider's algorithmic
refinement of WZ-theory \cite{WZ} for hypergeometric multisums. Using the MULTISUM package together with human
insight and interaction, Wegschaider was able to derive elegant proofs for \eqref{prop2 2} and \eqref{prop3 2}. In
addition he pointed out that {\it in principle} these identities can be proved in an entirely automatic fashion by
the computer. However, due to memory overflow he only was able to present such a proof for \eqref{prop2 2}.

This indicates that $\Omegaop$-manipulation on multisums may be used also in order to reduce complexity of
computation. For instance, our $\Omegaop$-proof of \eqref{prop3 2} reduces the triplesum problem to a problem
involving only single- and double-sums that then could be taken as input for computer programs like MULTISUM.

Another aspect of $\Omegaop$-manipulation is the flexibility of the method. For instance, another lemma that might
be useful in similar applications reads as follows:

\begin{lem} \label{no proof}
Let $f(\lam,\mu)\in {\bf C}[\lam,\lam^{-1},\mu,\mu^{-1}]$ be such that $f(\lam,\mu)=f(\mu,\lam)$. Then for integers
$\alpha, \beta, \gamma$ with $\alpha \leq \gamma$ and $\beta \leq \gamma$:
\[
\Omegaop\, (\lam^\alpha \mu^\beta - \lam^\beta \mu^\alpha) \lam^{-\gamma} \mu^{-\gamma} f(\lam,\mu) = 0.
\]
\end{lem}
\noindent Therefore in problems of the type
\[
\Omegaop\, p(\lam,\mu) f(\lam, \mu),
\]
where $p$ and $f$ are Laurent polynomials, one could try to represent $\Omegaop\, p(\lam,\mu) f(\lam, \mu)$ as a
linear combination of summands involving as many terms as possible that are of the same form as in the lemma. One
can expect that in this context Gr\"obner bases methods could be useful. We remark that if this technique is
applied to the case of \eqref{prop3 2}, one essentially ends up with a proof of a similar type as above.

Finally we want to add that the $\Omegaop$-method as described above can be used to prove also the cases $p=4$,
$p=5$, etc., of \eqref{brushes}. However, so far we have not found a common underlying pattern that proves {\it
all} the cases in one stroke. If such a pattern would be discovered, we have no doubt that the $q$-case could be
done analogously. In other words, this approach then would give a new alternative proof of the Knuth-Bender
conjecture.

%%%%%%%%%%%%%%%%%%%%%%%%%%HIER FORTSETZEN%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{thebibliography}{80}

\bibitem{Andrews:TOP} G.E.~Andrews, {\em The Theory of Partitions},
Encyclopedia of Mathematics and Its Applications, Vol.~2, G.-C.~Rota ed., Addison-Wesley, Reading, 1976. (Reissued:
Cambridge University Press, Cambridge, 1985.)

\bibitem{Andrews:PP} G.E.~Andrews, {\em Plane Partitions II: the
equivalence of the Bender-Knuth and MacMahon Conjectures}, Pac. J. Math. {\bf 72} (1977), 283--291.

\bibitem{Andrews:MMPA} G.E.~Andrews, {\em MacMahon's partition analysis I: the
lecture hall partition theorem}, (to appear).

\bibitem{Andrews:MMPA2} G.E.~Andrews, {\em MacMahon's partition analysis II:
fundamental theorems}, (to appear).

\bibitem{AU:IC} G.E.~Andrews and K. Uchimura, {\em Identities in
Combinatorics IV: differentiation and harmonic numbers}, Utilitas Math. {\bf 28} (1985), 265--269.

\bibitem{APR:III} G.E.~Andrews, P.~Paule and A.~Riese, {\em MacMahon's
partition analysis III: The \texttt{Omega} Package}, 1999, preprint.

\bibitem{APR:V} G.E.~Andrews, P.~Paule and A.~Riese, {\em MacMahon's
partition analysis V: magic squares}, (in preparation).

\bibitem{Arrow} D.K.~Arrowsmith, P.~Mason and J.W.~Essam, {\em
Vicious walkers, flows and directed percolation}, Physica A {\bf 177} (1991), 267--272.

\bibitem{AE} D.K.~Arrowsmith and J.W.~Essam, {\em Chromatic polynomials
and mod-$\lam$ flows on directed graphs and their applications}, 1998, preprint.

\bibitem{BM-E:LHP} M.~Bousquest-M\'elou and K.~Eriksson, {\em Lecture hall
partitions}, The Ramanujan Journal {\bf 1} (1997), 101--111.

\bibitem{Calkin} N.J.~Calkin, {\em A curious binomial identity},
Discrete Math.\ {\bf 131} (1994), 335--337.

\bibitem{Callan} D. Callan, {\em Problem 10643}, Amer.\ Math.\
Monthly {\bf 105}, No.~2, (1998).

\bibitem{Chyzak} F.~Chyzak, {\em Fonctions holonomes en Calcul formel},
Ph.D.\ Thesis, Ecole Polytechnique, Paris, 1998. Available via: \texttt{http://algo.inria.fr/libraries/}.

\bibitem{Egory} G.P.~Egorychev, {\em Integral Representation and the
Computation of Combinatorial Sums}, AMS Translations {\bf 59}, 1984.

\bibitem{EG} J.W.~Essam and A.J.~Guttmann, {\em Vicious walkers
and directed polymer networks in general dimension}, Phys.\ Rev. E {\bf 52} (1995), 5849--5862.

\bibitem{Fisher} M.E.~Fisher, {\em Walk, walls, wetting and melting},
J.\ Stat. Phys.\ {\bf 34} (1984), 667--729.

\bibitem{Gordon} B.~Gordon, {\em A proof of the Bender-Knuth
conjecture}, Pacific J.\ Math.\ {\bf 108}, 99--113.

\bibitem{GrKn} D. H. Greene and D. E. Knuth, {\em Mathematics for the
Analysis of Algorithms}, Birkhaeuser, Boston, 1981.

\bibitem{MacMahon:CA} P.A.~MacMahon, {\em Combinatory Analysis}, 2 vols.,
Cambridge University Press, Cambridge, 1915-1916 (Reprinted: Chelsea, New York, 1960).

%\bibitem{Stanley:BOOK} R.P.~Stanley, {\em Enumerative Combinatorics - Volume 1},
%Wadsworth, Monterey, California, 1986.

\bibitem{Stanley:Duke} R.P.~Stanley, {\em Linear homogeneous diophantine
equations and magic labelings of graphs}, Duke Math.\ J.\ {\bf 40} (1973), 607--632.

\bibitem{Weg} K.~Wegschaider, {\em Computer Generated Proofs of Binomial
Multi-Sum Identities}, Diploma Thesis, RISC, J. Kepler University Linz, 1997. Available via:

\noindent \texttt{http://www.risc.uni-linz.ac.at/research/combinat/ risc/}.

\bibitem{Wilf} H.S.~Wilf, {\em Generating functionology}, Academic Press, 1990.

\bibitem{WZ} H.S.~Wilf and D.~Zeilberger, {\em An algorithmic proof theory
for hypergeometric (ordinary and ``q") multisum/integral identities}, Inventiones Mathematicae {\bf 108} (1992),
575--633.

\bibitem{Zeil:holo} D.~Zeilberger, {\em A holonomic systems approach to
special functions identities}, J.\ Comp. Appl.\ Math.\ {\bf 32} (1990), 321--368.

\end{thebibliography}



\end{document}
