HMMT 二月 2011 · 冲刺赛 · 第 36 题
HMMT February 2011 — Guts Round — Problem 36
题目详情
- [ 25 ] An ordering of a set of n elements is a bijective map between the set and { 1 , 2 , . . . , n } . Call an ordering ρ 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. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
解析
- [ 25 ] An ordering of a set of n elements is a bijective map between the set and { 1 , 2 , . . . , n } . Call an ordering ρ 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 widely studied for its connection to an assortment of mathematical areas such as algebraic geometry, algebraic combinatorics, and computational geometry. Guts Round An admissble order in our problem—the higher Bruhat order B (5 , 2)—are best viewed as the set of reduced decompositions of the permutation 4321. Loosely speaking, a reduced decomposition is a sequence of adjacent transpositions that changes the permutation n, n − 1 , . . . , 1 to 1 , 2 , . . . , n . For example, for n = 4, the sequence (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4) induces the following reduced decomposition: 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 the chain. 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 are referred to Delong Meng’s paper “Reduced decompositions and permutation patterns generalized to the higher Bruhat order” for background as well as recent development of this subject. The paper is available at http://web.mit.edu/delong13/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 problems involving 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” at http://math.mit.edu/ ∼ rstan/papers/comb.pdf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Guts Round