HMMT 二月 2011 · 冲刺赛 · 第 34 题

英文解析

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 isi j k i j k lsaid 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 msubsequence if i < · · · < i and w < · · · < w . Define decreasing subsequences similarly. Let
    1 m i i
    1 mis ( w ) denote the length of the longest increasing sequence and ds ( w ) denote the length of the longestdecreasing sequence. We wish to find the number of permutations for n = 6 such that is ( w ) ≤ 2 andds ( 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 permutations for n = pq such that is ( w ) ≤ p and ds ( w ) ≤ q (exquisite permutations for simplicity), with anelegant 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 assignmentof 1 , 2 , . . . , pq , one to each unit square of the rectangle, such that every row and column is in increasingorder. There is a bijection between set of exquisite permutations and pairs of Young Tableaux. Sincethe number of ways to write 1 , 2 , . . . , 6 on a 2 × 3 rectangle with every row and column in increasingorder is 5, there are exactly 25 exquisite permutations.
    For a thorough exposition of increasing and decreasing subsequences and a collection of interesting openquestions, see Richard Stanley’s note for his undergraduate research students at MIT, “Increasing anddecreasing subsequences and their variants” available athttp://www.math.mit.edu/ ∼ rstan/papers/ids.pdf .