組合數學$6 Polya 計數

C6 Polya 計數

S1 Burnside 定理

0）約定：記讨論的置換群為 G \mathrm{G} G，着色群為 C \mathrm{C} C

1）

着色

：一個映射 c c c ，為每個元素指定顔色

2）

着色轉換

： f ⋆ c f\star c f⋆c ：使得 i k i_k ik​ 具有顔色 c ( k ) c(k) c(k)，即 f ⋆ c ( l ) = c ( f − 1 ( l ) ) f\star c (l) = c(f^{-1}(l)) f⋆c(l)=c(f−1(l))

• ( g ∘ f ) ⋆ c = g ⋆ ( f ⋆ c ) (g\circ f)\star c = g\star(f\star c) (g∘f)⋆c=g⋆(f⋆c)

3）

着色等價

：存在置換使得着色可互相轉換，記為 c 1 ∼ c 2 c_1\sim c_2 c1​∼c2​

4）

穩定核

：使着色保持不變的置換集合，記 G ( c ) G(c) G(c) = { f ∣ f ∈ G , f ⋆ c = c } =\{f|f\in \mathrm{G} ,f\star c = c\} ={f∣f∈G,f⋆c=c}

不變着色集

： C ( f ) C(f) C(f) = { c ∣ c ∈ C , f ⋆ c = c } =\{c|c\in \mathrm{C},f\star c = c\} ={c∣c∈C,f⋆c=c} 為在置換 f f f 作用下保持不變的着色

S X S_X SX​ 指 X X X 上的 [ n ] ( h t t p s : / / w w w . n o t i o n . s o / S 1 − 70 c 9 d 97 e 975845 c 2 b 155 d c 8 d 09 f 439 e 9 ) [n](https://www.notion.so/S1-70c9d97e975845c2b155dc8d09f439e9) [n](https://www.notion.so/S1−70c9d97e975845c2b155dc8d09f439e9) 階對稱群

5）

軌道-穩定集定理

： G ( c ) G(c) G(c) 是置換群， ∀ g , f ∈ G : g ⋆ c = f ⋆ c    ⟺    f − 1 ∘ g ∈ G ( c ) \forall g,f\in \mathrm{G} :g\star c = f\star c \iff f^{-1}\circ g \in G(c) ∀g,f∈G:g⋆c=f⋆c⟺f−1∘g∈G(c)

• 推論：與着色 c c c 等價的着色數為 ∣ G ∣ ∣ G ( c ) ∣ \frac{|\mathrm{G}|}{|\mathrm{G}(c)|} ∣G(c)∣∣G∣​

6）

BurnSide 定理

：非等價着色數 N ( G , C ) = 1 ∣ G ∣ ∑ f ∈ G C ( f ) N(\mathrm{G,C}) = \frac{1}{|\mathrm{G}|}\sum\limits_{f\in\mathrm{G}}C(f) N(G,C)=∣G∣1​f∈G∑​C(f) = 1 ∣ G ∣ ∑ c ∈ C G ( c ) =\frac{1}{|\mathrm{G}|}\sum\limits_{c\in \mathrm{C}}G(c) =∣G∣1​c∈C∑​G(c)

S2 Poyla 定理

0） 2 n 2n 2n 階二面體群： n n n 邊形的角點對稱群 { ρ n 0 , ρ n 1 , ⋯   , ρ n n − 1 , τ 1 , ⋯   , τ n } \{\rho_n^0,\rho_n^1,\cdots,\rho_n^{n-1},\tau_1,\cdots,\tau_n\} {ρn0​,ρn1​,⋯,ρnn−1​,τ1​,⋯,τn​},（逆時針旋轉+對稱）

1）

Poyla定理

：非等價着色數 N ( G , C ) = 1 ∣ G ∣ ∑ f ∈ G m o n   f N(\mathrm{G,C}) = \frac{1}{|G|}\sum\limits_{f\in \mathrm{G}}\mathrm{mon} \ f N(G,C)=∣G∣1​f∈G∑​mon f

• 置換生成函數

  ： ∑ f ∈ G m o n   f \sum\limits_{f\in G}\mathrm{mon} \ f f∈G∑​mon f

• 置換群循環指數

  ： P G ( z 1 , z 2 , ⋯   , z n ) = 1 ∣ G ∣ ∑ f ∈ G m o n   f P_G(z_1,z_2,\cdots,z_n)=\frac{1}{|G|}\sum\limits_{f\in G}\mathrm{mon} \ f PG​(z1​,z2​,⋯,zn​)=∣G∣1​f∈G∑​mon f

• 置換單項式

  ： m o n   f = ∏ i = 1 n z i e i \mathrm{mon} \ f = \prod\limits_{i=1}^n z_i^{e_i} mon f=i=1∏n​ziei​​，即将 f f f 拆為多個循環的乘積， e i e_i ei​ 為長為 i i i 的循環的個數
• 若置換群 G \mathrm{G} G 包含全部置換，則 ∏ i = 1 n z i e i \prod\limits_{i=1}^n z_i^{e_i} i=1∏n​ziei​​ 的系數為 n ! ( ∏ e i ! ) ( ∏ i ! ) \frac{n!}{(\prod e_i!)(\prod i!)} (∏ei​!)(∏i!)n!​
• 當使用 k k k 種顔色時， N ( G , C ) = 1 ∣ G ∣ ∑ f ∈ G k e 1 + ⋯ + e n N(\mathrm{G,C})=\frac{1}{|\mathrm{G}|}\sum\limits_{f\in \mathrm{G}}k^{e_1+\cdots+e_n} N(G,C)=∣G∣1​f∈G∑​ke1​+⋯+en​，稱

  循環指數

• 當限制顔色個數為 t 1 , ⋯   , t k t_1,\cdots ,t_k t1​,⋯,tk​ 時， N ( G , C ) = 1 ∣ G ∣ ∑ f ∈ G ∏ i = 1 n z i e i , z i = ∑ j = 1 k u j i N(\mathrm{G,C})=\frac{1}{|\mathrm{G}|}\sum\limits_{f\in \mathrm{G}}\prod\limits_{i=1}^n z_i^{e_i},z_i = \sum_{j=1}^k u_j^i N(G,C)=∣G∣1​f∈G∑​i=1∏n​ziei​​,zi​=∑j=1k​uji​，則 u 1 t 1 u 2 t 2 ⋯ u k t k u_1^{t_1}u_2^{t_2}\cdots u_k^{t_k} u1t1​​u2t2​​⋯uktk​​ 系數為所求（不要漏 1 ∣ G ∣ \frac{1}{|G|} ∣G∣1​）

2）應用：

• n n n 階非同構圖數目與 n n n 階段完全圖的邊 2-着色數相等
• 置換群生成方式： n ！ n！ n！個頂點置換，生成的邊集置換