$A\text{=}\left\{ 1,2,3,4,5,6,7 \right\}$，$N$ 为 $A$ 到 $A$ 的函数 $f$ 的个数，其中 $f$ 满足 $f\left( f\left( x \right) \right)$ 为常数。求 $N$ 模1000的值
【难度】
【出处】
2013年第31届美国数学邀请赛Ⅱ（AIMEⅡ）
【标注】
【答案】
399
【解析】
记定义域为 $R\text{=}\left\{\left. f\left( x \right) \right|x\in A \right\}$，记常值函数为 $f\left( f\left( x\right) \right)\text{=}c\text{,}c\in R$ 。对每个 $a\in \mathbb{R}$，因为 $f\left(f\left( x \right) \right)\text{=}c$，则 $f\left( a \right)\text{=}c$ 。分析可知 $\left| R\right|$ 不能超过 $4$，因为值域中元素的象为 $c$，而不同于 $c$ 的元素至少有一个原象。于是可分类讨论
$\left| R \right|=1$，$R$ 的选择有 $\left(\begin{matrix}
7 \\
1 \\
\end{matrix} \right)=7$ 种，$c$ 有 $\left(\begin{matrix}1 \\
1 \\
\end{matrix} \right)=1$ 种选择。非 $R$ 中的 $6$ 个元素只有一种映射方式，故共有 $7\cdot1\cdot 1=7$ 种。
$\left|R \right|=2$，$R$ 的选择有 $\left( \begin{matrix}
7 \\
2 \\
\end{matrix} \right)=21$ 种，$c$ 有 $\left( \begin{matrix}2 \\
1 \\
\end{matrix}\right)=2$ 种选择。剩余 $5$ 个元素有 ${{2}^{5}}=32$ 种映射方法，但若象均为 $c$，则 $\left| R \right|=1$ 与此类情况假设矛盾。故剩余元素映射方法有 $32-1=31$ 种。一共有 $21\cdot2\cdot 31=1302$ 种
$\left|R \right|=3$，$R$ 的选择有 $\left( \begin{matrix}
7 \\
3 \\
\end{matrix} \right)=35$ 种，$c$ 有 $\left( \begin{matrix}3 \\
1 \\
\end{matrix}\right)=3$ 种选择。求剩余 $4$ 个元素的映射等价于将 $4$ 个数分成三组，使得其中两组至少包含一个元素。 ${{3}^{4}}-2\cdot{{2}^{4}}+{{1}^{4}}=50$ 种分组方法。故此类情况共有 $35\cdot 3\cdot 50=5250$ 种
$\left| R\right|=4$，$R$ 的选择有 $\left( \begin{matrix}
7 \\
4 \\
\end{matrix} \right)=35$ 种，$c$ 有 $\left( \begin{matrix}4 \\
1 \\
\end{matrix}\right)=4$ 种选择。剩余 $3$ 个元素映射到 $3$ 个象，故此类情况共有 $35\cdot 4\cdot 3!=840$ 种
综上共有 $7+1302+5250+840=7399$ 种映射，所求值为 $399$
$\left| R \right|=1$，$R$ 的选择有 $\left(\begin{matrix}
7 \\
1 \\
\end{matrix} \right)=7$ 种，$c$ 有 $\left(\begin{matrix}1 \\
1 \\
\end{matrix} \right)=1$ 种选择。非 $R$ 中的 $6$ 个元素只有一种映射方式，故共有 $7\cdot1\cdot 1=7$ 种。
$\left|R \right|=2$，$R$ 的选择有 $\left( \begin{matrix}
7 \\
2 \\
\end{matrix} \right)=21$ 种，$c$ 有 $\left( \begin{matrix}2 \\
1 \\
\end{matrix}\right)=2$ 种选择。剩余 $5$ 个元素有 ${{2}^{5}}=32$ 种映射方法，但若象均为 $c$，则 $\left| R \right|=1$ 与此类情况假设矛盾。故剩余元素映射方法有 $32-1=31$ 种。一共有 $21\cdot2\cdot 31=1302$ 种
$\left|R \right|=3$，$R$ 的选择有 $\left( \begin{matrix}
7 \\
3 \\
\end{matrix} \right)=35$ 种，$c$ 有 $\left( \begin{matrix}3 \\
1 \\
\end{matrix}\right)=3$ 种选择。求剩余 $4$ 个元素的映射等价于将 $4$ 个数分成三组，使得其中两组至少包含一个元素。 ${{3}^{4}}-2\cdot{{2}^{4}}+{{1}^{4}}=50$ 种分组方法。故此类情况共有 $35\cdot 3\cdot 50=5250$ 种
$\left| R\right|=4$，$R$ 的选择有 $\left( \begin{matrix}
7 \\
4 \\
\end{matrix} \right)=35$ 种，$c$ 有 $\left( \begin{matrix}4 \\
1 \\
\end{matrix}\right)=4$ 种选择。剩余 $3$ 个元素映射到 $3$ 个象，故此类情况共有 $35\cdot 4\cdot 3!=840$ 种
综上共有 $7+1302+5250+840=7399$ 种映射，所求值为 $399$
答案
解析
备注
