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)!)

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