HMMT 二月 2009 · COMB 赛 · 第 4 题

英文解析

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 } ?
   Answer: 196
   Solution: A fixed point of a function f is an element a such that f ( a ) = a . The condition is equivalentto the property that f maps every number to a fixed point. Counting by the number of fixed pointsof f , the total number of such functions is
   ( )
   ∑5
   5 − k 0 4 1 3 25
   k = 1 · (5 ) + 5 · (1 + 4 ) + 10 · (2 + 3 )
   k =1 k = 1 + 25 + 10 · 17 = 196 .