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

英文解析

36. [ 25 ] An ordering of a set of n elements is a bijective map between the set and { 1 , 2 , . . . , n } . Call anordering ρ of the 10 unordered pairs of distinct integers from the set { 1 , 2 , 3 , 4 , 5 } admissible if, for any
    1 ≤ a < b < c ≤ 5, either p ( { a, b } ) < p ( { a, c } ) < p ( { b, c } ) or p ( { b, c } ) < p ( { a, c } ) < p ( { a, b } ). Find the total number of admissible orderings.
    Answer: 768
    This problem is a special case of the higher Bruhat order , a class of combinatorial object widelystudied for its connection to an assortment of mathematical areas such as algebraic geometry, algebraiccombinatorics, and computational geometry.
    Guts Round
    An admissble order in our problem—the higher Bruhat order B (5 , 2)—are best viewed as the setof reduced decompositions of the permutation 4321. Loosely speaking, a reduced decomposition is asequence of adjacent transpositions that changes the permutation n, n − 1 , . . . , 1 to 1 , 2 , . . . , n . Forexample, for n = 4, the sequence (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4) induces the following reduceddecomposition:
    43 21 → 4 31 2 → 41 32 → 14 32 → 1 42 3 → 12 43 → 1234 .
    For each permutation above, switching the two bolded numbers yields the next permutation in thechain. For example, switching 3 and 1 in 4 31 2 yields 4132.
    Readers interested in the connection between the higher Bruhat order and reduced decompositions arereferred to Delong Meng’s paper “Reduced decompositions and permutation patterns generalized tothe higher Bruhat order” for background as well as recent development of this subject. The paper isavailable athttp://web.mit.edu/delong 13/www/papers.html .
    The number of reduced decompositions of n, n − 1 , . . . , 1 is equal to the number of ( n − 1)st standard
    Young Tableaux of staircase shape, given by the formula
    ( )
    !n
    .2
    n − 1 n − 2
    1 · 3 · · · (2 n − 3)
    When n = 5, the formula gives 768.
    Young Tableaux are one of the most important tools in algebraic combinatorics, especially for problemsinvolving permutations, integer partitions, and posets. For a concise and accessible introduction to the
    Young Tableaux and reduced decompositions (and much more cool combinatorial stuff!), see Section
    7 of Richard Stanley’s note “A Combinatorial Miscellany” athttp://math.mit.edu/ ∼ rstan/papers/comb.pdf .
    Guts Round