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

> An annotated edition of this paper on Fermat's Library, where scientists and readers explain its ideas, equations and history in the margins. Annotated edition: https://fermatslibrary.com/s/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

- **Authors:** Doron Zeilberger
- **Published:** 2011
- **Topic:** Mathematics
- **Original:** https://s3-us-west-1.amazonaws.com/fermatslibrary/uploads%2F1569898161733-aa0z2qfchto-230f3a8668750830bfbab0d046027100%2F1110.4379.pdf
- **Pages:** 1
- **Annotations:** 5 comments in 5 threads
- **Featured:** Fermat's Library Journal Club
- **Annotated edition:** https://fermatslibrary.com/s/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

## Annotations

### Annotation 1 (page 1)

Beside the passage: “Doron ZEILBERGER 1”

**Annotation** by Luís Batalha (2019-10-01):

> This is probably the paper with the largest ratio: title/paper size - a title with 24 words for just a 1 page paper :)

### Annotation 2 (page 1)

Beside the passage: “Doron ZEILBERGER 1”

**Annotation** by Luís Batalha (2019-10-01):

> 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 :)
>
> ![](https://i.imgur.com/oDKBbFr.png)

### Annotation 3 (page 1)

Beside the passage: “. 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 .”

**Annotation** by Luís Batalha (2019-10-01):

> 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

### Annotation 4 (page 1)

Beside the passage: “. 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 .”

**Annotation** by Luís Batalha (2019-10-01):

> For a nice proof that the number of 321-avoiding n-permutations equals $C_n$ check D. E. Knuth the "Art of computer Programming"

### Annotation 5 (page 1)

Beside the passage: “. 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 .”

**Annotation** by Luís Batalha (2019-10-01):

> 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.

## Full text

Extracted from the PDF. [Annotation N] marks where each annotation above sits.

#### Page 1

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 [Annotation 2] 1 [Annotation 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. [Annotation 3] 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 [Annotation 4] n . [Annotation 5]

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

---

Source: [Fermat's Library](https://fermatslibrary.com/) — https://fermatslibrary.com/s/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. More annotated papers: https://fermatslibrary.com/llms.txt
