1 项链问题 上海交通大学数学科学学院章璞 11.1 Burnside 设群G作用在集合M上.如何确定M的G-轨道的条数?许多科学技术及日常生活中的 计数问题都可归结为这个问题 对任意g∈G,令F(g)表示M在g作用下的不动点的个数，即F(g)=|{x∈M|g×x= x}|.则我们有 定理11.1(W.Burnside,1852-1927)设M是G-集，t是M的G-轨道的条数.则 1=F(O) 这就是说，G中元作用在M上平均使得t个元保持不动. 证令={(g,x)∈G×M|g×x=x}.这里注意两个×的区别：G×M中的×指卡 氏积，而g×x中的×指g在x上的作用. 现在我们用两种方法计算|| 第一种方法：先固定g∈G,看看有多少x∈M使得g×x=x(根据定义，恰好有F(g)个 这样的元x∈M);然后再让g取遍G中元.这样我们得到||=∑geF(g). 第二种方法：先固定x∈M,看看有多少g∈G使得g× x =x(根据定义，恰好有|G4|个 这样的元g∈G);然后再让x取遍M中元.设M=UGx3是M的按轨道的划分.注意到 1≤i≤t 若x∈ Gxi,则Gx =Gxi, |Gx| =|Gxi|.于是由上节公式(1)知 101=10.1=- --- 由这两种方法算得的||即得∑。ec F(g) =t|G|,从而结论得证. 11.2应用举例：项链问题 上述观察是Burnside 1911年发现的，通常称为Burnside 引理.直到1937年才由G. Polya (1887-1985)发现它在许多计数问题中有广泛的应用.作为例子，我们考虑1 ‘ó¯K þ°ÏŒÆêƉÆÆ Ùâ 11.1 Burnside Ún +GŠ^38ÜMþ. XÛ(½MG-;^ê? Nõ‰ÆEâ9F~)¹¥ Oê¯Kь8(Ǒù‡¯K. é?¿g ∈ G, -F(g) L«M3g Š^eØÄ:‡ê,=F(g) = |{x ∈ M | g × x = x}|. K·‚k ½n11.1 (W. Burnside, 1852-1927) M´G-8, t´MG-;^ê.K t = 1 |G| X g∈G F(g). ùÒ´`, G ¥Š^3Mþ²þt‡±ØÄ. y -Ω = {(g, x) ∈ G × M | g × x = x} . ùp5¿ü‡×«OµG × M ¥× k ¼È, g × x ¥× g3xþŠ^. y3·‚^ü«{OŽ|Ω|. 1«{: k½g ∈ G, wwkõx ∈ Mg × x = x (Šâ½Â,TkF(g)‡ ùx ∈ M); ,￾24gHG¥. ù·‚|Ω| = P g∈G F(g). 1«{:k½x ∈ M, wwkõg ∈ Gg × x = x (Šâ½Â,Tk|Gx|‡ ùg ∈ G); ,￾24xHM¥. M = S 1≤i≤t Gxi ´MU;y©. 5¿ ex ∈ Gxi , KGx = Gxi , |Gx| = |Gxi |. u´dþ!úª(1) |Ω| = X x∈M |Gx| = X x∈M |G| |Gx| = Xt i=1 X x∈Gxi |G| |Gx| = Xt i=1 X x∈Gxi |G| |Gxi | = Xt i=1 |Gxi | |G| |Gxi | = t|G|. dùü«{Ž|Ω| =P g∈G F(g) = t|G|, l (Øy.  11.2 A^Þ~: ‘ó¯K þã* ´Burnside 1911 uy,Ï~¡ǑBurnside Ún.†1937 âdG. P´olya (1887-1985) uy§3NõOê¯K¥k2A^. ŠǑ~f,·‚Ä