Harvard-MIT Mathematics Tournament

Solution:
Given a permutation $w = w_{1}, \ldots, w_{n}$ for some $n$, call a sequence $w_{i_{1}}, w_{i_{2}}, \ldots, w_{i_{m}}$ an increasing subsequence if $i_{1} < \cdots < i_{m}$ and $w_{i_{1}} < \cdots < w_{i_{m}}$. Define decreasing subsequences similarly. Let $is(w)$ denote the length of the longest increasing sequence and $ds(w)$ denote the length of the longest decreasing sequence. We wish to find the number of permutations for $n = 6$ such that $is(w) \leq 2$ and $ds(w) \leq 3$. We note here that $6 = 2 \times 3$ is not a coincidence.

The main idea of his proof is as follows. Consider a $p \times q$ rectangle. A Young Tableau is an assignment of $1, 2, \ldots, pq$, one to each unit square of the rectangle, such that every row and column is in increasing order. There is a bijection between set of exquisite permutations and pairs of Young Tableaux. Since the number of ways to write $1, 2, \ldots, 6$ on a $2 \times 3$ rectangle with every row and column in increasing order is $5$, there are exactly $25$ exquisite permutations.