動機
一排有顏色的位置有明確的起點和終點。項鏈忽略起始位置,手鏈還進一步忽略閱讀方向。這些改變會把若干個字等同為同一個對象,但被等同的字的個數並不是常數:單色字的對稱性遠多於一般的字。
正確的計數方法,是對所有容許的對稱變換取固定構形個數的平均。我們要證明這個平均為甚麼恰好把每個軌道只計一次。旋轉的循環結構使固定字易於計數,反射的循環結構處理手鏈,而最小週期則分離出那些旋轉軌道確實達到完整長度的字。
必要的有限群記號會在需要時給出定義。
定義
定義 2.10.1
(群作用、軌道與穩定子)
有限群 具有結合的運算、單位元,且每個元素都有逆元。群 在有限集 上的一個作用,是給每個群元素指定一個置換 ,使得單位元的作用為恆等變換,並且 。
的軌道是 。它的穩定子是 ,而 的不動點集是 。軌道就是在容許指定對稱變換時所得的等價類。
長度為 的字,是給以模 為指標的每個位置指定 種顏色之一,其中 , 為非負整數。項鏈是在 個旋轉作用下的一個軌道。對於 ,手鏈是在由旋轉和一個反射生成的 個置換作用下的一個軌道。固定字在位置置換的每個循環上都取常值。
使一個字保持不變的最小正旋轉位移稱為它的最小週期 。它整除 ,而且該字是長度為 的塊的重複。本原字是最小週期為 的字。令 為長度為 的本原字的個數,其中各位置仍然是可區分的。令 表示在 至 中與 互質的剩餘類的個數,並規定 。
定理/命題
定理 2.10.2
(由不動點集平均值進行軌道計數)
對於有限群作用,,並且軌道的個數為
無需假設所有軌道大小相等。除以群的階,針對的是不動點對的總和,而不是單單針對構形的個數。
定理 2.10.3
(項鏈與手鏈公式)
長度為 的 色項鏈的個數為
對於 ,手鏈的個數為
其中
各種顏色的名稱仍然保持可區分;這裏沒有對顏色作置換後再取商。
定理 2.10.4
(本原週期有莫比烏斯計數)
對每個正整數 ,
這裏 是前面已經建立的整除意義下的莫比烏斯(Möbius)函數。每個本原旋轉軌道恰有 個字,所以本原項鏈的個數為 。所有項鏈(包括由重複塊構成的項鏈)滿足 。
證明思路或證明
證明
(軌道—穩定子與不動點對的雙重計數)
軌道關係由單位元得自反性,由逆元得對稱性,由乘法得傳遞性。固定一點 ,考慮從 到其軌道的映射,把 送到 。若 ,則 當且僅當 固定 。因此 上方的纖維是 ,大小為 。各纖維大小相等,便得到軌道—穩定子恆等式。
數一數滿足 的對 。先對 求和,得到不動點集之和;先對 求和,得到 。在同一個軌道上,由穩定子恆等式,每個點的穩定子大小都等於 除以該軌道的大小,所以這個軌道恰好貢獻 。因此,把對的個數除以 ,就得到軌道的個數。
證明透視
先數對稱變換—構形對,再作除法
證明以兩種次序計算同一個有限集,即不動點對,而全部內容都在第二種次序裏。群結構在那裏透過軌道—穩定子進入:從 到 的映射,其纖維是穩定子的陪集,所以大小全部相同。因此軌道上每一點的穩定子大小都是群的階除以軌道大小,不論軌道多大,整個軌道的貢獻都是群的階。對稱性很高的字位於較小的軌道,卻被更多元素固定;兩種效應恰好抵消。這種抵消是吸收軌道大小不等的唯一地方。把字的原始個數直接除以對稱變換的個數,就跳過了這一步,所以會失效。
這個論證也說明了,為甚麼不同的對稱變換可以有大小懸殊的不動點集,卻不會使平均公式失效。
旋轉的循環結構決定固定字
證明
(旋轉與反射的循環個數)
旋轉 個位置的置換有 個循環。事實上,一個位置的軌道是不斷加 (模 ),在 步之後第一次回到原處。這些長度相等的循環把所有位置劃分開來。固定字對每個循環獨立地選取一種顏色,因此有 個固定字。
把旋轉位移按 分組。這樣的位移形如 ,其中 取模 且與 互質。這樣的選擇有 個;當 時包括恆等位移。固定字的個數為 。求和並應用軌道計數定理,就證明了項鏈公式,而完全不必枚舉軌道本身。
對於反射,位置以模 為指標。每個反射都形如 ,其中 取 個值之一。它的不動位置是模 下 的解;其餘位置構成互相交換的位置對。
若 為奇數,則乘以二在模 下可逆,所以恰有一個不動位置。每個反射有 個位置循環。若 為偶數且 為偶數,則有兩個不動位置,因而有 個循環。若 為奇數,則沒有不動位置,因而有 個循環。兩種類型各佔反射的一半。由此得到的固定字總數恰為 。加上旋轉的貢獻,再除以群的階 ,便證明了手鏈公式。
最小週期為本原劃分提供依據
證明
(最小週期、本原塊與莫比烏斯反演)
固定某個字的位移集合,在模 下對加法和取負封閉。改把它們看作整數,並包括位移 。設 是其中最小的正元素,把任何其他固定位移除以 。由封閉性,餘數仍是固定位移;由最小性,餘數只能是零。特別地, 整除 ,並且固定位移恰為 在模 下的倍數。
該字由其前 個位置決定,並重複這些位置,因為位移 固定它。這個塊在長度 下是本原的:若塊有更小的週期,它就會固定整個字,與最小性矛盾。反之,把任一長度為 的因數 的本原塊重複,就得到最小週期恰為 的長度為 的字。若有更小的位移固定這個重複字,它在塊上的剩餘類作用就會給出塊的更小週期。
按這個唯一的因數 對長度為 的所有字分類。對每個這樣的因數,塊的選擇有 個,所以它們的總和為 。應用前面已證明的整除意義下的莫比烏斯反演,便得到本原公式。長度為 的本原字的旋轉穩定子是平凡的,所以它的軌道大小為 。更一般地,最小週期為 的字,其軌道大小為 ,這解釋了最後一個關於所有項鏈的求和式。
限制條件必須施加在固定構形上
如果規定每種顏色必須出現的位置個數,同樣的軌道計數定理仍然適用,因為旋轉保持這些個數。然而,長度為 的置換循環現在會使其所選顏色出現 次。它不加約束時的選擇個數,不能脫離總數而獨立地沿用。
一個精確的辦法,是給顏色 一個變量 。長度為 的位置循環貢獻多項式 。把各個循環的因子相乘,再提取所需顏色總數對應的係數。這個係數恰好數出滿足限制條件的固定字。然後像前面一樣,對群取這些係數的平均。這是有限的多項式計算,不涉及形式收斂問題,也說明了為甚麼固定內容的項鏈往往不能簡單地把不同的調色板大小代入無限制公式。
例題詳解
例題 2.10.5
(長度為四的六條二元項鏈,軌道大小各不相同)
旋轉的固定字個數為:恆等變換十六個,旋轉一步兩個,旋轉兩步四個,旋轉三步兩個。它們的平均值為六。代表元為 。
它們的軌道大小依次為一、一、四、四、四、二,總共十六個字。把十六除以四會得到四,漏掉了對稱構形的補償。對於這個長度的手鏈,反射的貢獻是 ,所以手鏈的個數同樣是六。
例題 2.10.6
(在長度為六時,反轉使一對項鏈合併)
對於長度為六的二元字,旋轉之和為 ,得到十四條項鏈。反射的貢獻合計為 ,得到十三條手鏈。
以 和 為代表的項鏈是不同的旋轉軌道,但它們經反轉和一次旋轉而互相聯繫。因此它們成為同一條手鏈。總數顯示,恰有一對這樣的項鏈軌道被合併;所有其他項鏈軌道在手鏈中仍各自保持為單獨的軌道。
把旋轉後的單詞反向讀取,只會得到原單詞反向讀取後的另一個旋轉。因此反向在項鏈等價類上有良好定義,且做兩次回到原類。它只會固定一個類或交換兩個類,所以十四個項鏈類變為十三個手鏈類時,恰好合併了一對。
例題 2.10.7
(本原二元字與重複項鏈可以清楚分開)
對於長度為六,莫比烏斯反演給出 。除以六,得到九條本原項鏈。其餘的項鏈,最小週期為一、二或三。
在這些長度下,本原字的個數分別為二、二和六。它們對項鏈的貢獻分別為二、一和二,合計五。把這五條重複項鏈與九條本原項鏈相加,便還原出十四。若把長度為六的所有字都除以六,恰恰會在這些較短的軌道上出錯。
概念視角組合
對稱性改變等價關係,而週期衡量其穩定子
字、項鏈和手鏈有相同的底層有色位置,但對「相等」的理解不同。最小週期控制旋轉軌道的大小,而反射可以把兩個不同的旋轉軌道合併。在商的計數有確定含義之前,必須先指明所用的群以及容許的顏色限制。
常見錯誤
反例模式
構形的個數不一定能被對稱群的階整除
長度為六的二元字有六十四個,而手鏈的群有十二個元素。它們的商甚至不是整數,而正確的手鏈個數是十三。這個群並非自由作用:對稱的字具有非平凡的穩定子。只有證明了作用是自由的,才可以把原始構形個數除以整個群的階。
反射公式只對長度至少為三的情形陳述,這樣通常的多邊形對稱變換才恰好給出所述的群。
常見錯誤
(本原字不是本原項鏈)
計算的是位置有區別的字;每條本原項鏈恰好包含其中 個。二元長度六時有 個本原字,但只有 條本原項鏈。把 當作項鏈個數,或把非本原的個數除以 ,都混淆了兩個層次。
常見錯誤
(沒有顏色作用卻等同顏色名稱)
這些公式保留顏色名稱的區別: 與 是不同的二元項鏈。把它們視為相同是另一個問題,需要再加一個置換顏色的作用,並另行計算軌道。
總結
軌道—穩定子計數使平均不動點集公式即使在軌道大小不一時也是精確的。旋轉與反射的循環結構給出項鏈與手鏈的個數。最小週期整除長度,並給出本原字的莫比烏斯反演;而固定內容的限制,則在取平均之前透過循環權重的係數來施加。
練習
快速檢查
(計算長度為三的三色項鏈與手鏈的個數,並計算本原項鏈的個數。)
使用三個旋轉和三個反射,並保持各顏色名稱可區分。
解答
旋轉之和為 ,所以有十一條項鏈。每個反射有兩個位置循環,固定九個字;加上它們的貢獻,得到手鏈個數 。
在質數長度三下,只有常值字的週期更短。因此 ,本原項鏈的個數為八。其餘三條項鏈是單色的項鏈。
快速檢查
(計算長度為四、且每種顏色恰好出現在兩個位置上的二元項鏈的個數。請計算固定字的個數,而不要使用無限制調色板的公式。)
考察半圈旋轉,並注意哪些旋轉能保持所要求的總數。
解答
恆等變換固定所有 個容許的字。旋轉一步或三步只固定常值字,而常值字中沒有一個滿足每種顏色各佔兩個位置。半圈旋轉有兩個含兩個位置的循環;給它們指定不同的顏色,得到兩個固定字。平均值為 。
代表元為 和 。前者的軌道大小為四,後者為二,合起來恰好包含全部六個字。內容限制既作用於顏色的選擇,也作用於循環的長度。
快速檢查
(對於質數長度 和非負整數 ,用組合方法證明 整除 。)
把常值字與本原字分開,並利用它們的軌道大小。
解答 · 答案
最小週期整除質數長度 ,所以它要麼是一,要麼是 。週期為一的字恰為 個常值字。其餘每個字都是本原的,屬於大小為 的旋轉軌道。因此 是 的倍數。當顏色數為零或一時,同樣的結論成立,只是相應的集合為空或全是常值字;證明中沒有用到除以零的構形個數。