题目
对于集合 X 和函数 f : X \rightarrow X，定义 f 的 n 次迭代 f^{ [ n ] } 为：
- 若 n = 1，则 f^{ [ 1 ] } = f。
- 若 n > 1，则 f^{ [ n ] } = f \circ f^{ [ n - 1 ] }。
其中 f \circ g 表示函数复合，即 ( f \circ g ) ( x ) = f ( g ( x ) )。
设集合 U = \{ x | 1 \leq x \leq 100, x \in \mathbb{ N^{ * } } \}，函数 f 为满足定义域与值域均为 U 的随机函数，求 f^{ [ 30 ] } ( 1 ) = 1 的概率。
解析
考虑什么情况下有 f^{ [ 30 ] } ( 1 ) = 1，不难发现 f^{ [ 1 ] } ( 1 ) = 1 满足条件，f^{ [ 2 ] } ( 1 ) = 1 也满足条件。不难发现对于任意 n | 30，均有若 f^{ [ n ] } ( 1 ) = 1，则 f^{ [ 30 ] } ( 1 ) = 1。
不难发现满足 f^{ [ 1 ] } ( 1 ) = 1 的函数有 99! 个，满足 f^{ [ 2 ] } ( 1 ) = 1 的函数有 99! 个。不难发现对于任意 n | 30，均有满足 f^{ [ n ] } ( 1 ) = 1 的函数有 99! 个。
又因为满足定义域与值域均为 U 的函数 f 总共有 100! 个，故 f^{ [ 30 ] } ( 1 ) = 1 的概率即为 \dfrac{ \sigma_{ 0 } ( 30 ) \cdot 99! }{ 100! } = \dfrac{ 2 }{ 25 }（其中 \sigma_{ 0 } 为因数个数函数）。
by CXY。