34. $[\mathbf{2 5}]$ Let $w=w_{1}, w_{2}, \ldots, w_{6}$ be a permutation of the integers $\{1,2, \ldots, 6\}$. If there do not exist indices $iw_{j}>w_{k}>w_{l}$, then $w$ is said to be exquisite. Find the number of exquisite permutations.
Answer:
25
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}p$ or $d s(w)>q$, which later appeared on the Russian Math Olympiad.
In 1961, Schensted proved that the bound $p q+1$ is sharp, and he enumerated the number of permutations for $n=p q$ such that $i s(w) \leq p$ and $d s(w) \leq q$ (exquisite permutations for simplicity), with an elegant combinatorial proof based on the RSK-algorithm relating Young Tableux and permutations.
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, p q$, 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.
For a thorough exposition of increasing and decreasing subsequences and a collection of interesting open questions, see Richard Stanley's note for his undergraduate research students at MIT, "Increasing and decreasing subsequences and their variants" available at