函数f:{1,2,3}→{1,2,3,4}满足f(f(x))=f(x),则这样的函数共有多少个

Question

函数f:{1,2,3}→{1,2,3,4}满足f(f(x))=f(x),则这样的函数共有多少个

Answer 1

f[f(x)]=f(x)
即：f(x)=x
函数的个数由不同的映射关系确定.
映射：f：A→B,A中的元素在B中必须有像,但B中并非所有的元素有原像.所以映射由“一对一”,“多对一”两种类型.
（1）f：{1,2,3}→{1,2,3},可以有f(1)=1,f(2)=2,f(3)=3【当然也可以是f(1)=1,f(2)=3,f(3)=2,这个无所谓的】,这是1个函数；
（2）f：{1,2,3}→{1},此时满足f(1)=1;同理有,
f：{1,2,3}→{2}；{3}；共有3类不同的映射,因此有3个函数
（3）f：{1,2,3}→{1,2},此时满足f(1)=1,f(2)=2;首先任选两个元素作为值域,比如1,2；则有3种情况；则3可以对应1或2,有2种情况；则有C32*C21=6个函数
（4）f：{1,2,3}→{1,2,3,4},{1,2,3,4}作为值域的话,原像集{1,2,3}必然有有一个元素要对应2个像,这不符合映射的定义,故这个映射关系不成立,
综上所述,一共有10个函数.【注意,有几个函数是通过不同的映射关系确定的】
【下面从不动点角度解释】
满足f(x)=x的x称为f(x)的不动点.所有满足f(x)=x的x的取值的集合称为不动点集.
从f(x)=x看,所有不动点集显然是函数f(x)值域的子集；
从f[f(x)]=f(x),看f(x)的值域是不动点集的子集；
所以不动点集=值域.
然后根据值域数目枚举：
（1）值域只有一个元素的函数3个
（2）值域有两个元素,根据两个元素的不同有3种情况.而给定值域后,由于值域中的点都是不动点,我们只需要确定余下元素的取值,只有两种情况,所以这部分总共3*2=6个函数
（3）对于值域3个元素的函数,由于这三个数都是不动点,只有1个函数
总共3+6+1=10个函数