求满足条件的从 $\left\{ 1,2,3,4,5 \right\}$ 到 $\left\{ 1,2,3,4,5 \right\}$ 的 $f\left( x \right)$ 的个数，使得 $f\left( f\left( x \right) \right)\text{=}f\left( f\left( f\left( x \right) \right) \right)$ 对任意 $x\in \left\{ 1,2,3,4,5 \right\}$ 成立。
【难度】
【出处】
2018年第36届美国数学邀请赛Ⅱ（AIMEⅡ）
【标注】
【答案】
756
【解析】
设 $y\text{=}f\left(f\left( x \right) \right)$，则 $y\text{=}f\left( y \right)$ 。于是 $f$ 至少有一个不动点。令 $A\text{=}\left\{\left. y \right|y\text{=}f\left( x \right) \right\}$ 我们以 $f$ 的不动点的个数分类讨论
1．$\left|A \right|=1$，不动点的选择有 $C_{5}^{1}=5$ 种。剩余点中满足 $f\left( x \right)\in A$ 的若有 $1$ 个，其选择有 $C_{4}^{1}=4$ 种，则剩下的 $x$ 取值仅有 $1$ 种选择；满足 $f\left(x \right)\in A$ 的若有 $2$ 个，其选择有 $C_{4}^{2}\text{=}6$ 种，剩下的 $x$ 取值各有 $2$ 种选择；满足 $f\left( x \right)\in A$ 的若有 $3$ 个，其选择有 $C_{4}^{3}=4$ 种，剩下的 $x$ 取值各有 $3$ 种选择；满足 $f\left(x \right)\in A$ 的若有 $4$ 个，其选择有 $C_{4}^{4}\text{=}1$ 种。故此类情况共 $5\cdot \left( 4\cdot{{1}^{3}}+6\cdot {{2}^{2}}+4\cdot 3+1 \right)=205$ 个。
2．$\left|A \right|=2$，不动点的选择有 $C_{5}^{2}=10$ 种。剩余点中满足 $f\left( x \right)\in A$ 的若有 $1$ 个，有 $C_{3}^{1}\cdot2\text{=}6$ 种；满足 $f\left( x \right)\in A$ 的若有 $2$ 个，有 $C_{3}^{2}\cdot {{2}^{2}}\cdot2\text{=24}$ 种；满足 $f\left( x \right)\in A$ 的若有 $3$ 个，有 $C_{3}^{3}\cdot{{2}^{3}}\text{=8}$ 种。故此类情况一共有 $10\cdot \left( 6+24+8 \right)\text{=}380$ 个。
3．$\left|A \right|=3$，不动点的选择有 $C_{5}^{3}=10$ 种。剩余点中满足 $f\left( x \right)\in A$ 的若有 $1$ 个，有 $C_{2}^{1}\cdot3\text{=}6$ 种；剩余点中满足 $f\left( x \right)\in A$ 的若有 $2$ 个，有 $C_{2}^{2}\cdot{{3}^{2}}\text{=9}$ 种。故此类情况一共有 $10\cdot \left( 6+9 \right)=150$ 个。
4．$\left|A \right|=4$，此类情况有 $C_{5}^{1}\cdot C_{4}^{1}\text{=20}$ 个。
5．$\left|A \right|=5$，此类情况有 $1$ 个。
综上，一共有 $205+380+150+20+1\text{=}756$ 个
1．$\left|A \right|=1$，不动点的选择有 $C_{5}^{1}=5$ 种。剩余点中满足 $f\left( x \right)\in A$ 的若有 $1$ 个，其选择有 $C_{4}^{1}=4$ 种，则剩下的 $x$ 取值仅有 $1$ 种选择；满足 $f\left(x \right)\in A$ 的若有 $2$ 个，其选择有 $C_{4}^{2}\text{=}6$ 种，剩下的 $x$ 取值各有 $2$ 种选择；满足 $f\left( x \right)\in A$ 的若有 $3$ 个，其选择有 $C_{4}^{3}=4$ 种，剩下的 $x$ 取值各有 $3$ 种选择；满足 $f\left(x \right)\in A$ 的若有 $4$ 个，其选择有 $C_{4}^{4}\text{=}1$ 种。故此类情况共 $5\cdot \left( 4\cdot{{1}^{3}}+6\cdot {{2}^{2}}+4\cdot 3+1 \right)=205$ 个。
2．$\left|A \right|=2$，不动点的选择有 $C_{5}^{2}=10$ 种。剩余点中满足 $f\left( x \right)\in A$ 的若有 $1$ 个，有 $C_{3}^{1}\cdot2\text{=}6$ 种；满足 $f\left( x \right)\in A$ 的若有 $2$ 个，有 $C_{3}^{2}\cdot {{2}^{2}}\cdot2\text{=24}$ 种；满足 $f\left( x \right)\in A$ 的若有 $3$ 个，有 $C_{3}^{3}\cdot{{2}^{3}}\text{=8}$ 种。故此类情况一共有 $10\cdot \left( 6+24+8 \right)\text{=}380$ 个。
3．$\left|A \right|=3$，不动点的选择有 $C_{5}^{3}=10$ 种。剩余点中满足 $f\left( x \right)\in A$ 的若有 $1$ 个，有 $C_{2}^{1}\cdot3\text{=}6$ 种；剩余点中满足 $f\left( x \right)\in A$ 的若有 $2$ 个，有 $C_{2}^{2}\cdot{{3}^{2}}\text{=9}$ 种。故此类情况一共有 $10\cdot \left( 6+9 \right)=150$ 个。
4．$\left|A \right|=4$，此类情况有 $C_{5}^{1}\cdot C_{4}^{1}\text{=20}$ 个。
5．$\left|A \right|=5$，此类情况有 $1$ 个。
综上，一共有 $205+380+150+20+1\text{=}756$ 个
答案
解析
备注
