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 (â½Â,T kF(g) ùx ∈ M); ,24gHG¥. ù·|Ω| = P g∈G F(g). 1«{:k½x ∈ M, wwkõg ∈ Gg × x = x (â½Â,T k|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¥k2A^. Ǒ~f,·Ä
项链问题(Necklace problem):设有n颗珠子，r种颜色.将每颗珠子染上其中一种 色（未必每种颜色都要用到）.假设相同颜色的珠子是没有区别的.问可以配成多少种不同 的（图形）项链？ 首先要把这个问题转化成数学问题.用B={1,2,n}代表珠子的集合，用C={1,,,}代 表颜色的集合，用 f=12…n 劝物… 表示B到C的映射：i→斯∈C,1≤i≤n.作为映射当然也可将f写成 其中伯i2…n)是(12…n)的任意一个排列令n={f:B-→C 将颗珠子标号1，·，n,按逆时针方向（等距地）排成圈形.将第颗珠子染上某种颜 色h,i=1, ,这样我们就得到所谓的一条标号项链.显然，标号项链的集合和之 取n=6,颜色为白、黑、红三色.则 (日8文8)月 =(安数合合景)=（红及名合盘）月 是三个不同的映射，它们相应的标号项链分别为（其中O表示白色珠子，◆表示黑色珠子 ?表示红色球子)
2 ó¯K (Necklace problem)µkn¾f, r« Ú. òz¾f/þÙ¥« Ú(7z« ÚÑ^). bÓ Ú¾f´vk«O. ¯±¤õ«ØÓ (/)ó? Äkrù¯K=z¤êƯK. ^B = {1, 2, . . . , n}L¾f8Ü, ^C = {c1, c2, . . . , cr} L Ú8Ü,^ f = 1 2 · · · n y1 y2 · · · yn ! L«BCNµi 7→ yi ∈ C, 1 ≤ i ≤ n. ǑN,Ǒòf¤ f = i1 i2 · · · in yi1 yi2 · · · yin ! , Ù¥(i1 i2 · · · in) ´(1 2 · · · n)?¿ü.-Ω = {f | f : B −→ C}. òn¾fIÒ1, · · · , n, U_( å/)ü¤/. ò1i¾f/þ,« Úyi , i = 1, · · · , n, ù·Ò¤¢^IÒó. w,, IÒó8ÜÚΩ m3N, üö,ѹ|Ω| = r n.´ù¿·ó«ê. ~X, n = 6, ÚǑx!ç!ùnÚ. K f = 1 2 3 4 5 6 ù x x ç ù ç ! , g = 1 2 3 4 5 6 ç ù x x ç ù ! , h = 1 2 3 4 5 6 ù ç x x ù ç ! , ´nØÓN,§AIÒó©OǑ(Ù¥ L«xÚ¾f, ♣L«çÚ¾f, ♥L«ùÚ¾f) f = ♥ ♣ ♣ ♥ g = ♣ ♥ ♣ ♥ h = ♥ ♣ ♥ ♣
3 但是，将第一条标号项链∫绕中心逆时针方向旋转60°就得到第二条标号项链g(注意珠子的 标号只是为了叙迷方便才标号的，所有的珠子是不加区分的：只有不同颜色的珠子才加以 区分)：将第一条标号项链∫绕3与6连线这条对称轴翻折一下就得到第三条标号项链h.因 此这三条标号项链应该是同一种项链 我们规定：如 一条圈形项链通过转或者翻折就与另一条项链重合（这里及以 的“重合”是指相同位置的珠子颜色相同)，则这两条项链应视为同一种类，并且，如果一条项 链无论怎么转怎么翻也不能与另一条项链重合，则这两条项链应视为不同种类. 考虑二面体群Dn在集合上的如下作用.设 12..,n a= 定义 -(日8…)(0)-( 为了方便地验证这的确是群作用，我们将中元与D中元按置换的乘法法则形式”地相 乘，则a×∫可写成 a×f-fa-1 这样就容易看出2是Dn-集 两条标号项链f与g(或2中的两个元，g)在同一Dm轨道中，当且仅当将标号项链f通 过某种旋转或者翻折就得到标号项链，也就是∫与9应看作同一项链，例如，在上图中， g-(:58）x-(:8)x 现在我们得到：Ω的D轨道的条数就是我们要计算的项链的种数 这样，由Burnside引理知，项链的种类 t=Ea)=六a 其中F(a)={f∈n|a×f=fl关键是求出F(a).设a∈DnCSn,将a分解成互不相 交的轮换图子的乘积. 引理11.2a×∫=∫当且仅当若i,j位于a的同一轮换图子中，则f回)=f0), -()
3 ´,ò1^IÒóf7¥%_^=60◦Ò1^IÒóg (5¿¾f IÒ´Ǒ QãBâIÒ, ¤k¾f´Ø\«©¶kØÓ Ú¾fâ\± «©)¶ò1^IÒóf736ëù^顶òeÒ1n^IÒóh. Ï dùn^IÒóAT´Ó«ó. ·5½µXJ^/óÏL^=½öòÒ,^óÜ(ùp9±e “Ü”´Ó ¾f ÚÓ), Kùü^óAÀǑÓ«a,¿ ,XJ^ ó ØNo=NoǑØU,^óÜ,Kùü^óAÀǑØÓ«a. Ä¡N+Dn38ÜΩþXe^. α = 1 2 · · · n i1 i2 · · · in ! ∈ Dn, f = 1 2 · · · n y1 y2 · · · yn ! ∈ Ω. ½Â α × f = 1 2 · · · n i1 i2 · · · in ! × 1 2 · · · n y1 y2 · · · yn ! := i1 i2 · · · in y1 y2 . . . yn ! . Ǒ B/yù(´+^, ·òΩ¥Dn¥U{{K“/ª”/ , Kα × f¤ α × f = fα−1 . ùÒN´wÑΩ´Dn-8. ü^IÒófg (½Ω¥üf, g) 3ÓDn-;¥, =òIÒófÏ L,«^=½öòÒIÒóg, ǑÒ´fgAwÓó.~X,3þã¥, g = 1 2 3 4 5 6 2 3 4 5 6 1 ! × f, h = 1 2 3 4 5 6 5 4 3 2 1 6 ! × f. y3·µ ΩDn-;^êÒ´·Oó«ê. ù,dBurnsideÚn, ó«a t = 1 |Dn| X α∈Dn F(α) = 1 2n X α∈Dn F(α), Ù¥F(α) = |{f ∈ Ω | α × f = f}|. ' ´ÑF(α). α ∈ Dn ⊆ Sn. òα©)¤pØ ÓÏfÈ. Ún11.2 α × f = f =ei, j uαÓÓÏf¥,Kf(i) = f(j). y α = 1 2 · · · n i1 i2 · · · in ! , f = 1 2 · · · n y1 y2 · · · yn ! . K α × f = i1 i2 · · · in y1 y2 . . . yn ! . (1)
我们可将写成 (“) 若f回=f0),其中i,j位于a的同一轮换国子中，则由于j与，位于a的同一轮换国子 中，所以斯=f0)=f)=班，1≤j≤n.比较(1)和（②）得到a×f=f: 反之，如果a×f=,比较(1)和（②）得到，=贴，1≤j≤n.这说明f)=f(.而 在中，j与处于同一轮换国子中的相邻位置：并且处于同一轮换国子中的相邻位置的两 个数字从左至右看一定形如))这就推出只要，位于a的同一轮换因子中，就有f间 f0) 设a型为(1,2，…，入n.则a有1+2++Xn个互不相交的轮换因子.由引理11.2， a×f=f当且仅当对于位于a的同一轮换因子中的数字i和j均有f问=f》.而对每个轮 换因子中的数字i,回有r种选择，故满足条件a×f=f的f有+++入个，即Fa) rA+a+.+ 从而 其中a的型为(，2…，An).这就解决了项链问题： ∑cA,2,,n)r+++ 种不同的图形项链，这里(1,2，…，入n)取遍二面体群Dn的型，c(入，2，入n)是Dn中型 为(A1,2,…,入)的元素的个数. 11.3项链问题的一般公式 下面我们利用命题11.3和上节中已知的Dn-{a,2,…,”-dn,,2,…,oT= }中每个元的型，给出项链问题的一般公式 旋转(1≤i≤n)的型为高m.事实上，因为=(12…,对于1≤i≤n,由指标 模知=高i+1=向n+1放有 。=i+1,2+1,（-+ 因此。是，n)个长为向的轮换的乘积即。的型为高.从而 aeDn。是翻转
4 ·òf¤ f = i1 i2 · · · in yi1 yi2 · · · yin ! . (2) ef(i) = f(j), Ù¥i, j uαÓÓÏf¥, Kdujij uαÓÓÏf ¥,¤±yj = f(j) = f(ij ) = yij , 1 ≤ j ≤ n.'(1)Ú(2) α × f = f. , XJα × f = f, '(1)Ú(2)yij = yj, 1 ≤ j ≤ n. ù`²f(j) = f(ij). 3α¥, jij?uÓÓÏf¥ ¶¿ ?uÓÓÏf¥ ü êilmw½/X(j ij ).ùÒíÑi, j uαÓÓÏf¥,Òkf(i) = f(j). α.Ǒ(λ1, λ2, · · · , λn). Kαkλ1 + λ2 + · · ·+ λnpØÓÏf. dÚn11.2, α × f = f =éu uαÓÓÏf¥êiiÚjþkf(i) = f(j). ézÓ Ïf¥êii, f(i)kr«ÀJ,÷v^α × f = ff kr λ1+λ2+···+λn, =F(α) = r λ1+λ2+···+λn . l t = 1 2n X α∈Dn r λ1+λ2+···+λn , Ù¥α.Ǒ(λ1, λ2, · · · , λn). ùÒ)û ó¯K: ·K11.3 kn¾f, r« Ú. òz¾f/¤Ù¥« Ú.Ó Ú¾f ´vk«O. Kk t = 1 2n X (λ1,λ2,...,λn) c(λ1, λ2, . . . , λn) r λ1+λ2+···+λn «ØÓ/ó, ùp(λ1, λ2, · · · , λn)H¡N+Dn., c(λ1, λ2, . . . , λn)´Dn¥. Ǒ(λ1, λ2, · · · , λn)ê. 11.3 ó¯Kúª e¡·|^·K11.3 Úþ!¥®Dn = {σ, σ2 , · · · , σn = IdΩ, στ, σ2 τ, · · · , σn τ = τ} ¥z.§Ñó¯Kúª. ^=σ i (1 ≤ i ≤ n) .Ǒ n (i,n) (i,n) . ¯¢þ, ÏǑσ = (12 · · · n), éu1 ≤ i ≤ n, dI n 1 = n (i,n) i + 1 = i (i,n) n + 1, k σ i = (1, i + 1, 2i + 1, · · · ,( n (i, n) − 1)i + 1)· · · Ïdσ i ´(i, n) Ǒ n (i,n) Óȧ=σ i .Ǒ n (i,n) (i,n) . l t = 1 2n ( Xn i=1 r (i,n) + X α∈Dn,α´= r λ1+λ2+···+λn ).
当n是奇数时，n件翻转r(1≤i≤m)型都是12宁.故 当n是偶数时，有受件翻转7（为奇数，1≤i≤n)的型都是2：还有受件翻转7位为 偶数，1≤i≤n)的型都是12学故 空++半 t= 这就解决了项链问题： 定理11,4设有颗珠子，r种颜色.将每颗珠子染成其中一种颜色.则项链的种数为 宫… 命题11.4是群的一件真实而美妙的应用：问题本无“群，解决须作用”. 例设有6颗珠子，3种颜色.则可做成t=立3+32+3+32+3+3)+33=2种 不同的项链 利用群作用，类似染可以解决：分子结构的计数，正多面体着色，开关线路，图的计 数，等等。 习题 设有4颗珠子，2种颜色，问能组成多少种不同的项链 探索题：设有6颗白色的珠子，3颗黑色的珠子.问配成多少种不同的项链？
5 n´Ûê, n=σ i τ (1 ≤ i ≤ n) .Ñ´1 12 n−1 2 . t = 1 2n ( Xn i=1 r (i,n) + nr n+1 2 ). n´óê, kn 2=σ i τ (iǑÛê, 1 ≤ i ≤ n) .Ñ´2 n 2 ;kn 2=σ i τ (iǑ óê, 1 ≤ i ≤ n) .Ñ´1 22 n−2 2 . t = 1 2n ( Xn i=1 r (i,n) + n 2 (r n 2 + r n+2 2 )). ùÒ)û ó¯K: ½n11.4 kn¾f, r« Ú. òz¾f/¤Ù¥« Ú.Kó«êǑ t = 1 2n Xn i=1 r (i,n) + 1 2 r n+1 2 , n Û, 1 4 r n 2 (1 + r), n ó. ·K11.4 ´+ý¢ {©A^: ¯K “+”,)ûL“^”. ~ k6¾f, 3« Ú. K¤t = 1 12 (31 + 32 + 33 + 32 + 31 + 36 ) + 33 = 92 « ØÓó. |^+^§aq/±)ûµ©f(Oê§õ¡NXÚ§m'´§ãO ê§ . SK k4¾f, 2« Ú, ¯U|¤õ«ØÓó? &¢K: k6xÚ¾f, 3çÚ¾f. ¯¤õ«ØÓó?