 
\baselineskip=14pt
\parskip=10pt
\parindent=0pt
\overfullrule=0in
 
 
{\bf
Sylvie Corteel's One-Line Proof
of a Partition Theorem Discovered by Andrews-Paule-Riese's
Computer}
 
In the conference `Combinatorics and Physics' organized by Bill
Chen and Jim Louck (Los Alamos, Aug. 1998), George Andrews
stated an elegant computer-generated theorem that came out of
his project, with Peter Paule and Axel Riese, of automating
MacMahon's Omega calculus.
 
{\bf Theorem:} The number of partitions of $n$,
$\lambda=(\lambda_1,\lambda_2,\ldots,\lambda_k)$, such
that $\Delta^r \lambda$ has non-negative entries
(here $\Delta(\mu_1,\mu_2,\ldots,\mu_k):=(\mu_1-\mu_2, \dots, 
\mu_{k-1}-\mu_k, \mu_k)$) equals the number of partitions
of $n$ into parts of the form ${{i} \choose {r}}$.
 
A few minutes after the talk, Sylvie Corteel (who was probably
the youngest participant), came up with a brilliant human-generated
one-line-proof, that establishes a {\it natural bijection}
between the two sets. To wit it is:
$$
\lambda \rightarrow 
\left \{
\,\,{{i-1+r}\choose {r}}^{(\Delta^r\lambda)_i} \,\, \right \}, 
\,\,(1 \leq i \leq k) \quad ,
$$
where in the right side we use the frequency notation
of partitions $a^b$ meaning `$a$ repeated $b$ times'.
The right hand side is indeed a partition of $n$ (by summation by parts
$r$ times), and the reverse bijection is:
$$
\left \{
{{i-1+r}\choose {r}}^{\nu_i} \right \} (1 \leq i \leq k) \rightarrow 
\left (
\,\, \sum_{j=i}^{k} {{j+r-i} \choose {r-1}} \nu_j
\,\, \right )_{1 \leq i \leq k} \quad ,
$$
which again follows by summation by parts (this time only $r-1$ times).
Note that when $r=1$ this is the classical bijection between
a partition and its conjugate.
 
Reported by: Doron Zeilberger, zeilberg@math.temple.edu
\bye
 
