HMMT 二月 2011 · 冲刺赛 · 第 34 题
HMMT February 2011 — Guts Round — Problem 34
题目详情
- [ 25 ] Let w = w , w , . . . , w be a permutation of the integers { 1 , 2 , . . . , 6 } . If there do not exist indices 1 2 6 i < j < k such that w < w < w or indices i < j < k < l such that w > w > w > w , then w is i j k i j k l said to be exquisite . Find the number of exquisite permutations.
解析
- [ 25 ] Let w = w , w , . . . , w be a permutation of the integers { 1 , 2 , . . . , 6 } . If there do not exist indices 1 2 6 i < j < k such that w < w < w or indices i < j < k < l such that w > w > w > w , then w is i j k i j k l said to be exquisite . Find the number of exquisite permutations. Answer: 25 Given a permutation w = w , . . . , w for some n , call a sequence w , w , . . . , w an increasing 1 n i i i 1 2 m subsequence if i < · · · < i and w < · · · < w . Define decreasing subsequences similarly. Let 1 m i i 1 m 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 ) ≤ 2 and ds ( w ) ≤ 3. We note here that 6 = 2 × 3 is not a coincidence. Erdos and Szekeres first studied problems on the longest increasing and decreasing subsequences. In 1935, they showed that for any permutation w of { 1 , 2 , . . . , pq + 1 } , either is ( w ) > p or ds ( w ) > q , which later appeared on the Russian Math Olympiad. In 1961, Schensted proved that the bound pq + 1 is sharp, and he enumerated the number of permu- tations for n = pq such that is ( w ) ≤ p and ds ( w ) ≤ 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 × q rectangle. A Young Tableau is an assignment of 1 , 2 , . . . , 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 , . . . , 6 on a 2 × 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 http://www.math.mit.edu/ ∼ rstan/papers/ids.pdf .