Question

求满射函数 $\pi$ 的个数，其中该函数从集合 $A = \{1, 2, 3, 4, 5, 6\}$ 映到 $A$ ，并且对每个 $a \in A$ 都有 $\pi(\pi(\pi(\pi(\pi(\pi(a)))))) = a\text{。}$

Find the number of functions $\pi$ mapping the set $A = \{1, 2, 3, 4, 5, 6\}$ onto $A$ such that for every $a \in A,$ $\pi(\pi(\pi(\pi(\pi(\pi(a)))))) = a.$

答案

答案：396

知识点：排列补集计数分类讨论

难度评级：2510

小提示：

有限集合到自身的满射是一个排列，而条件表示它的六次方是恒等映射

An onto map from a finite set to itself is a permutation, and the condition says its sixth power is the identity

大提示：

等价地，每个循环长度都整除 $6$ ，所以从 $720$ 中减去含有 $4$ -循环或 $5$ -循环的排列

Equivalently every cycle length divides $6,$ so subtract from $720$ the permutations that contain a $4$ -cycle or a $5$ -cycle

解答：

有限集合到自身的满射一定是双射，所以 $\pi$ 是六个元素的排列，条件表示 $\pi^6$ 是恒等映射。一个排列满足 $\pi^6 = \mathrm{id}$ ，当且仅当其循环分解中每个循环长度都整除 $6$ 。在可能的长度 $1$ 到 $6$ 中，只有 $4$ 和 $5$ 不整除 $6$ 。

要排除含有 $4$ -循环或 $5$ -循环的排列，并从 $6! = 720$ 中减去这些排列。循环类型 $4+1+1$ 给出 $\frac{6!}{4 \cdot 2!} = 90$ ，类型 $4+2$ 给出 $\frac{6!}{4 \cdot 2} = 90$ ，类型 $5+1$ 给出 $\frac{6!}{5} = 144$ ，共排除 $90 + 90 + 144 = 324$ 个排列。

所求个数为 $720 - 324 = 396$ 。

A function from a finite set onto itself is a bijection, so $\pi$ is a permutation of six elements, and the condition says $\pi^6$ is the identity. A permutation satisfies $\pi^6 = \mathrm{id}$ exactly when every cycle in its cycle decomposition has length dividing $6.$ Among the possible lengths $1$ through $6,$ only $4$ and $5$ fail to divide $6.$

We subtract the permutations containing a $4$ -cycle or a $5$ -cycle from $6! = 720.$ Cycle type $4+1+1$ gives $\frac{6!}{4 \cdot 2!} = 90,$ type $4+2$ gives $\frac{6!}{4 \cdot 2} = 90,$ and type $5+1$ gives $\frac{6!}{5} = 144,$ for $90 + 90 + 144 = 324$ excluded permutations.

The count is $720 - 324 = 396.$

2026 AIME I 第 7 题

答案：396

难度评级：2510

小提示：

大提示：

解答：

其他年份的第 7 题