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.

Theorem: The number of partitions of n, λ = (λ_{1}, λ_{2}, …, λ_{k}), such that Δ^{r}λ has non-negative entries (here Δ(μ_{1}, μ_{2}, …, μ_{k}) := (μ_{1} − μ_{2}, …, μ_{k−1} − μ_{k}, μ_{k})) equals the number of partitions of n into parts of the form \binom{i}{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 natural bijection between the two sets. To wit it is:

λ → \{ \binom{i − 1 + r}{r}^{(Δ^{r}λ)_{i}} \} , (1 ≤ i ≤ k) ,

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:

\{\binom{i − 1 + r}{r}^{ν_{i}}\} (1 ≤ i ≤ k) → ( ∑_{j=i}^{k} \binom{j + r − i}{r − 1}ν_{j} )_{1≤i≤k} ,

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