HMMT 十一月 2010 · 冲刺赛 · 第 20 题

英文解析

20. [ 11 ] Given a permutation π of the set { 1 , 2 , . . . , 10 } , define a rotated cycle as a set of three integersi, j, k such that i < j < k and π ( j ) < π ( k ) < π ( i ). What is the total number of rotated cycles over allpermutations π of the set { 1 , 2 , . . . , 10 } ?
    Answer: 72576000 Let us consider a triple ( i, j, k ) with i < j < k and determine how many
    ( )
    permutations rotate it. There are choices for the values of π ( i ) , π ( j ) , π ( k ) and the choice of this 10
    set of three determines the values of π ( i ) , π ( j ) , π ( k ). The other 7 values then have 7! ways to be arranged 3
    ( )
    (any permutation of them will work), so exactly 7! permutations rotate ( i, j, k ). Therefore, as there 10
    ( ) ( )3
    10 102
    are such triples, the total number of rotated triples is · 7! = 72576000.
    3 3