Alexander Burstein’s Lovely Combinatorial Proof of John Noonan’s Beautiful Theorem that the number of n-permutations that contain the Pattern 321 Exactly Once Equals

(3/n)(2n)!/((n-3)!(n+3)!)

Doron ZEILBERGER^{1}

Alex Burstein[1] gave a lovely combinatorial proof of John Noonan’s[2] lovely theorem that the number of n-permutations that contain the pattern 321 exactly once equals \frac{3}{n} \binom{2n}{n+3}. Burstein’s proof can be made even shorter as follows. Let C_{n} := (2n)!/(n!(n + 1)!) be the Catalan numbers. It is well-known (and easy to see) that C_{n} = ∑_{i=0}^{n−1} C_{i}C_{n−1−i}. It is also well-known (and fairly easy to see) that the number of 321-avoiding n-permutations equals C_{n}.

Any n-permutation, π, with exactly one 321 pattern can be written as π_{1}cπ_{2}bπ_{3}aπ_{4}, where cba is the unique 321 pattern (so, of course a < b < c). All the entries to the left of b, except c, must be smaller than b, and all the entries to the right of b, except for a, must be larger than b, or else another 321 pattern would emerge. Hence σ_{1} := π_{1}bπ_{2}a is a 321-avoiding permutation of {1, …, b} that does not end with b and σ_{2} := cπ_{3}bπ_{4} is a 321-avoiding permutation of {b, …, n} that does not start with b. This is a bijection between the Noonan set and the set of pairs (σ_{1}, σ_{2}) as above (for some 2 ≤ b ≤ n − 1). For any b the number of possible σ_{1} is C_{b} − C_{b−1}. Similarly, the number of possible σ_{2} is C_{n−b+1} − C_{n−b}. Hence the desired number is

∑_{b=2}^{n−1}(C_{b} − C_{b−1})(C_{n−b+1} − C_{n−b}) = ∑_{b=1}^{n}(C_{b} − C_{b−1})(C_{n−b+1} − C_{n−b})

= ∑_{b=1}^{n} C_{b}C_{n−b+1} − ∑_{b=1}^{n} C_{b}C_{n−b} − ∑_{b=1}^{n} C_{b−1}C_{n−b+1} + ∑_{b=1}^{n} C_{b−1}C_{n−b}

= C_{n+2} − 2C_{n+1} − 2(C_{n+1} − C_{n}) + C_{n} = C_{n+2} − 4C_{n+1} + 3C_{n} = \frac{3}{n}\binom{2n}{n + 3} .

References

1. Alex Burstein, A short proof for the number of permutations containing the pattern 321 exactly once, Elec. J. Comb. 18(2)(2011), #P21.

2. John Noonan, The number of permutations containing exactly one increasing subsequence of length three, Discrete Math. 152(1996), 307-313 .

1 Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen

Rd., Piscataway, NJ 08854-8019, USA. zeilberg at math dot rutgers dot edu , http://www.math.rutgers.edu/~zeilberg/ . Based on a mathematics colloquium talk at Howard University, Oct.

14, 2011, 4:10-5:00pm, where Alex Burstein was presented with a $25 check prize promised in John Noonan’s 1996 Discrete Math paper. Oct 18., 2011. Exclusively published in the Personal Journal of Shalosb B. Ekhad and Doron Zeilberger http://www.math.rutgers.edu/~zeilberg/pj.html and arxiv.org . Supported in part by the NSF.