HMMT 二月 2009 · COMB 赛 · 第 4 题

HMMT February 2009 — COMB Round — Problem 4

[ 4 ] How many functions f : { 1 , 2 , 3 , 4 , 5 } → { 1 , 2 , 3 , 4 , 5 } satisfy f ( f ( x )) = f ( x ) for all x ∈ { 1 , 2 , 3 , 4 , 5 } ?

解析

[ 4 ] How many functions f : { 1 , 2 , 3 , 4 , 5 } → { 1 , 2 , 3 , 4 , 5 } satisfy f ( f ( x )) = f ( x ) for all x ∈ { 1 , 2 , 3 , 4 , 5 } ? Answer: 196 Solution: A fixed point of a function f is an element a such that f ( a ) = a . The condition is equivalent to the property that f maps every number to a fixed point. Counting by the number of fixed points of f , the total number of such functions is ( ) 5 ∑ 5 5 − k 0 4 1 3 2 k = 1 · (5 ) + 5 · (1 + 4 ) + 10 · (2 + 3 ) k k =1 = 1 + 25 + 10 · 17 = 196 .