《抽象代数》课程教学资料（近世代数）项链问题（上海交通大学：章璞）

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,·‚Ä

项链问题(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. ¯Œ±¤õ«ØÓ (/)‘ó? Äk‡rù‡¯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ґóf73†6ë‚ù^顶€ò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ґóf†g (½Ω¥ü‡f, g) 3ÓDn-;¥, …=òIґófÏ L,«^=½ö€òÒIґóg, ǑÒ´f†gAwŠÓ‘ó.~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¥, Kduj†ij 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α¥, j†ij?uÓӆÏf¥ƒ ¶¿…?uÓӆÏf¥ƒ ü ‡êil†mw½/X(j ij ).ùÒíѐ‡i, j uαÓӆÏf¥,Òkf(i) = f(j).  α.Ǒ(λ1, λ2, · · · , λn). Kαkλ1 + λ2 + · · ·+ λn‡p؃ӆÏ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. K
k 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, dI 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: k6ˆxÚ¾f, 3ˆçÚ¾f. ¯¤õ«ØÓ‘ó?