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

HMMT November 2010 — Guts Round — Problem 20

[ 11 ] Given a permutation π of the set { 1 , 2 , . . . , 10 } , define a rotated cycle as a set of three integers i, j, k such that i < j < k and π ( j ) < π ( k ) < π ( i ). What is the total number of rotated cycles over all permutations π of the set { 1 , 2 , . . . , 10 } ?

解析

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