返回题库

HMMT 二月 2009 · GEN1 赛 · 第 9 题

HMMT February 2009 — GEN1 Round — Problem 9

专题
Discrete Math / 离散数学
难度
L3
来源
HMMT

题目详情

  1. [ 6 ] 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 } ?
解析
  1. [ 6 ] 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 5 0 4 1 3 2 k = 1 · (0 + 5 ) + 5 · (1 + 4 ) + 10 · (2 + 3 ) k k =1 = 1 + 25 + 10 · 17 = 196 .