HMMT 二月 2002 · 冲刺赛 · 第 48 题

HMMT February 2002 — Guts Round — Problem 48

[9] A permutation of a finite set is a one-to-one function from the set to itself; for instance, one permutation of { 1 , 2 , 3 , 4 } is the function π defined such that π (1) = 1, π (2) = 3, π (3) = 4, and π (4) = 2. How many permutations π of the set { 1 , 2 , . . . , 10 } have the property that π ( i ) 6 = i for each i = 1 , 2 , . . . , 10, but π ( π ( i )) = i for each i ?

解析

A permutation of a finite set is a one-to-one function from the set to itself; for instance, one permutation of { 1 , 2 , 3 , 4 } is the function π defined such that π (1) = 1, π (2) = 3, π (3) = 4, and π (4) = 2. How many permutations π of the set { 1 , 2 , . . . , 10 } have the property that π ( i ) 6 = i for each i = 1 , 2 , . . . , 10, but π ( π ( i )) = i for each i ? Solution: For each such π , the elements of { 1 , 2 , . . . , 10 } can be arranged into pairs { i, j } such that π ( i ) = j ; π ( j ) = i . Choosing a permutation π is thus tantamount to choosing a partition of { 1 , 2 , . . . , 10 } into five disjoint pairs. There are 9 ways to pair off the number 1, then 7 ways to pair off the smallest number not yet paired, and so forth, so we have 9 · 7 · 5 · 3 · 1 = 945 partitions into pairs.