This is probably the paper with the largest ratio: title/paper size...
The story behind this paper is pretty funny. In 1996, Doron Zeilber...
The Catalan numbers (1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, ...
For a nice proof that the number of 321-avoiding n-permutations equ...
There are several ways to prove this recurrence relation - $\sum_{i...
arXiv:1110.4379v2 [math.CO] 21 Oct 2011
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
3
n
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
=
P
n−1
i=0
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
n−1
X
b=2
(C
b
− C
b−1
)(C
n−b+1
− C
n−b
) =
n
X
b=1
(C
b
− C
b−1
)(C
n−b+1
− C
n−b
)
=
n
X
b=1
C
b
C
n−b+1
−
n
X
b=1
C
b
C
n−b
−
n
X
b=1
C
b−1
C
n−b+1
+
n
X
b=1
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
=
3
n
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 Shalosh B. Ekhad and Doron
Zeilberger http://www.math.rutgers.edu/~zeilberg/pj.html and arxiv.org . Supported in part by the NSF.
1
This is probably the paper with the largest ratio: title/paper size - a title with 24 words for just a 1 page paper :)
For a nice proof that the number of 321-avoiding n-permutations equals $C_n$ check D. E. Knuth the "Art of computer Programming"
The Catalan numbers (1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, ...), named after Eugène Charles Catalan (1814–1894), arise in a number of problems in combinatorics.
Among other things, the Catalan numbers describe:
1 - the number of ways a polygon with n+2 sides can be cut into n triangles
2 - the number of ways to use n rectangles to tile a stairstep shape (1, 2, ..., n−1, n).
3 - the number of ways in which parentheses can be placed in a sequence of numbers to be multiplied, two at a time
4 - the number of planar binary trees with n+1 leaves
5 - the number of paths of length 2n through an n-by-n grid that do not rise above the main diagonal
The story behind this paper is pretty funny. In 1996, Doron Zeilberger suggested this problem to John Noonan, who ends up writing a paper with a [solution](https://www.sciencedirect.com/science/article/pii/0012365X9500247T).
At the time Noonan published the paper with the solution, Doron Zeilberger offered a prize of 25 Dollars to the first person to come up "nice bijective proof" to the problem.
In combinatorics, bijective proof is a proof technique that finds a bijective function (that is, a one-to-one and onto function) f : A → B between two finite sets A and B, or a size-preserving bijective function between two combinatorial classes, thus proving that they have the same number of elements, |A| = |B|.
15 years later in September 2011, Alex Burstein from Howard University wrote a short [3 page bijective solution](https://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i2p21/pdf) for the problem, granting him the well deserved prize.
Just a month later Doron Zeilberger came up with an even shorter 1 page solution to the problem :)
There are several ways to prove this recurrence relation - $\sum_{i=0}^{n-1} C_iC_{n-1-i} = C_n$ - but perhaps the most elegant is by appealing to Dyck paths of length 2(n+1), which we saw above that $C_{n+1}$ counts. Given a Dyck path of length 2(n+1), let 2(k+1) be the first nonzero xx-coordinate where the path hits the xx-axis, then $n_0≤k≤n$.
The path breaks up into two pieces, the part to the left of 2(k+1) and the part to its right. The part to the right is a Dyck path of length 2(n−k), so it is counted by $C_{n-k}$. The part to the left is a northeast step, then a Dyck path of length 2k, and then a southeast step. (The middle path is a Dyck path "on stilts"; it never dips below its starting point because it cannot hit the xx-axis earlier than 2(k+1).) There are $C_k$ of these. So there are a total of $C_kC_{n-k}$ paths which hit the x-axis first at $2(k+1)$, and summing these terms up gives $C_{n+1}$, which is the recurrence relation.