UR #10 T3 列队 证明练习

给出群 $G$，求证 $\varphi: G \rightarrow S_n$ 的单同态数量 $f(G)$ 为 $$ f(G) = n![x^n]\exp \left(\sum_{H\le G} \frac{x^{[G:H]}}{[G:H]}\right) - \sum_{\mathrm{normal}\, N, {1} < N \le G} f(G/N) $$ 我们仅考虑同态的数量，我们知道 $\ker \varphi$ 是正规子群，单同态就是说 $\ker \varphi = 1$。 假设一个同态的核 $N = \ker \varphi$，我们知道 $\varphi(aN) = \varphi(a)$，因此自然而然的就是 $G/N$ 到 $S_n$ 的一个单同态，银从我们得到了 $$ \sum_{\mathrm{normal}\, N, 1\le N\le G} f(G/N) $$ 就是 $G$ 到 $S_n$ 的同态数量。我们要证明它等于 $n![x^n]\exp \left(\sum_{H\le G} \frac{x^{[G:H]}}{[G:H]}\right)$。我们考虑 $\operatorname{im} \varphi$ 对于 $[n]$ 作用所划分成的轨道。我们知道轨道与轨道之间是没有影响的。所以假设在 $S_k$ 上是大小为 $k$ 的轨道有 $a_k$ 种同态，那么 $n![x^n]\exp \sum_k a_k \frac{x^k}{k!}$ 就是 $S_n$ 总共的同态数量。 现在我们讨论 $a_k$，对于 $[k]$ 整体构成一个轨道，其稳定子 $H\le G$ 是一个子群，我们知道 $H$ 只能把 $1$ 映到 $1$，而设 $a_2H, a_3H,\dots, a_kH$ 陪集的全体 $(k-1)!$ 个排列，现在我们假设 $a_iH$ 将 $1$ 映射到 $i$，为了知道 $a_iH$ 将 $j$ 映射到哪，考虑 $\varphi(a_iH)\varphi(a_jH)1 = \varphi(a_iH)j = \varphi(a_ia_jH)1$，由此我们知道任何一个排列得以确定一个同态，而任何一个同态又得以确定一个排列，因此稳定子为 $H$ 的同态的数量就是 $(k-1)! = ([G:H]-1)!$。