Alexander Burstein's Lovely Combinatorial Proof of John Noonan's Beautiful Formula
that the number of n-permutations that contain the Pattern 321 Exactly Once
Equals (3/n)(2n)!/((n-3)!(n+3)!)
By Doron Zeilberger
.pdf
.ps
.tex
This article (Doron Zeilberger's, expositing Alex Burstein's paper, NOT Burstein's original paper that
only appears in the Elec. J. of Comb.) is
published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger
and is also to appear in of J. of Pure and Applied Algebra (Special Issue for the Proceedings of Permutation Patterns 2010, V. Vatter, ed.)
Written: Oct. 18, 2011.
In 1996, my brilliant student John Noonan,
discovered, and
proved
that there are 3(2n)!/(n(n+3)!(n-3)!) ways
to line-up n people of
different heights in such a way that out of the n(n-1)(n-2)/6 possible triples of people
exactly one is such that the tallest stands (not necessarily immediately) in front of the
second-tallest, who in turn, stands (not necessarily immediately) in front of the shortest.
In that article, I promised a prize of 25 dollars for a nice combinatorial proof.
Alex Burstein
gave such a proof.
On Oct. 14, 2011, I talked about Alex's lovely proof at the
Howard U. math colloquium,
and publicly presented the $25-dollar prize.
The present note is the outcome. Congratulations Alex!
Personal Journal of Shalosh B. Ekhad and Doron Zeilberger
Doron Zeilberger's Home Page