《波利亚计数定理》三 “伯氏引理” 3.3 伯氏引理的证明
让我们先定下伯氏引理:设$G$是一个$n$阶群,有元$g_1 ,g_2 ,\cdots ,g_n$,$S$是一个有限集,而$G$作用于$S$上.如果$r$是这个作用下的轨的个数,则
$$rn =\vert X(g_1 )\vert +\cdots +\vert X(g_n )\vert ,$$
$X(g)$是由$S$中所有满足$g\ast s=s$的元$s$组成的集,$\vert X(g)\vert $是这个集的元的个数.
未证明这条定理前,让我们用第$3.1$节的两个例子印证一下.在第一个例子里,数据如下:
$$n=8;\vert X(x_0 )\vert =24,\vert X(x_1 )\vert =\cdots =\vert X(x_7 )\vert =0.$$
为什么是这样呢?对$x_0 $来说,作用是不移动正方形,所以不论是$24$个摆法中的哪一个,经$x_0 $的作用后还是同一个,所以$X(x_0 )$是全部$24$个摆法组成的集.对任何别的元,作用总是移动了某些角,所以不论是哪一个摆法,经它的作用后肯定不是同一个,所以$X(x_1 )$、$X(x_2 )$、$\cdots $、$X(x_7 )$都是空集.把数据代入伯氏引理的公式,轨的数目$r$满足$8r=24+0+\cdots +0=24$,所以$r=3$.在第二个例子里,数据如下:
$$n=8;\vert X(x_0 )\vert =16,\vert X(x_1 )\vert =2,\vert X(x_2 )\vert =4,$$
$$\vert X(x_3 )\vert =2,\vert X(x_4 )\vert =4,\vert X(x_5 )\vert =8,$$
$$\vert X(x_6 )\vert =4,\vert X(x_7 )\vert =8.$$
为什么是这样呢?迟一点我们将在第$3.4$节里介绍一个概括的普遍算法,读者暂时不妨按照定义就着个别特殊情况计算,这对以后的解释,是有助于理解的.把数据代入伯氏引理的公式,轨的数目$r$满足$8r=16+2+4+2+4+8+4+8=48$,所以$r=6$.
证明伯氏引理的方法,是用两种不同的看法去数同一个数目,这个数目就是全部满足$g\ast s=s$的有序偶$(g,s)$的个数,暂记作$M$.先选定$g$,应有$\vert X(g)\vert $个那种有序偶,再走遍$G$中元$g$,得到$M=\vert X(g_1 )\vert +\cdots +\vert X(g_n )\vert $.再选定$s$,应有$\vert G_s \vert $个那种有序偶,再走遍$S$中元$s$,得到$M=\sum \vert G_s \vert $,求和式中的项数等于$S$中元的个数,利用第$3.2$节的公式,我们把$\vert G_s \vert $换作$n/n(s)$,$n(s)$是轨$G(s)$的元的个数.如果轨$G(s)$有元$s_1 $、$\cdots $、$s_j ,j=n(s)$,便有
$$\vert G_{s_1} \vert +\cdots +\vert G_{s_j} \vert =n(1/j+\cdots +1/j)=n,$$
因为式中正好有$j$个$1/j$.因此,如果有$r$个轨,$M=\sum \vert G_s \vert =rn $.把两个计算$M$的答案比较,便有
$$rn =\vert X(g_1 )\vert +\cdots +\vert X(g_n )\vert .$$
证明完毕.
设$G$是一个群,$H$是$G$的一个子群,定义一个群$H$在集$G$上的作用:对$H$中元$h$和$G$中元$g$,规定$h\ast g$是$gh^{-1}$($g$和$h^{-1}$在$G$里的乘积).在第$3.2$节里你已见过类似的作用,这时$g$的轨$H(g)=\lbrace gh^{-1}\vert h\in H\rbrace $也就是$\lbrace gh\vert h\in H\rbrace $,在第$2.5$节里这个叫做包含$g$的$H$的(左)陪集,陪集的个数叫做$H$的指数,记作$(G\colon H)$.把伯氏引理应用于这个特殊情况,数据如下:
$$n=\vert H\vert ;\vert X(e)\vert =\vert G\vert ;$$
$$\vert X(h)\vert =0,h\neq e;r=(G\colon H).$$
读者试写下$X(h)$的定义便明白了.因此,公式变成$(G\colon H)\vert H\vert =\vert G\vert $,那即是第$2.5$节提及的拉格朗日定理的内容.就这个意义说,伯氏引理是拉格朗日定理的推广.