置換群在計(jì)數(shù)中的應(yīng)用

置換群在計(jì)數(shù)中的應(yīng)用凈聽我瞎扯淡吧【笑1你要知道置換群是什么鬼一．置換群的基本概念定義1任一集合A到自身的映射都叫做的A一個(gè)變換，如果A是有限集且變換是一一變換（雙射），那么這個(gè)變換為A的一個(gè)置換。有限集合A的若干個(gè)置換若作成群，就叫做置換群。含有n個(gè)元素的有限群A的全體置換作成的群，叫做n次對(duì)稱群。通常記為Sn。置換群是一種特殊的變換群。換句話說，置換群就是有限集上的變換群。由于是定義在有限集上，故每個(gè)置換的表現(xiàn)形式，固有特點(diǎn)都是可揣測(cè)的。大家應(yīng)該知道什么是變換群吧？封閉性、可結(jié)合、有單位元、存在逆元舉個(gè)栗子p119關(guān)于循環(huán)置換2這個(gè)置換群在計(jì)數(shù)中到底有什么應(yīng)用等價(jià)類計(jì)數(shù)瞅一道題吧用6種不同顏色給正方體的六個(gè)面著色，每個(gè)面有6中選擇，假如給定每個(gè)面的編號(hào)，不同的著色序列有6！(=720)個(gè)，但哪些是“真正”不同的？因此：不同的著色有6!/(6+3+6+8+1)=30種

90

180

180

120

6種3種6種8種1種其實(shí)我并沒有看太明白接下來我就要介紹一種簡(jiǎn)單粗暴的方法如果不是每個(gè)面的著色都不同,比如有兩個(gè)面是紅的，如何判斷兩種著色是“真正”不同？設(shè)著色對(duì)象的集合是S，允許使用的顏色的集合是C(我們只考慮有限集)。一種著色方案就是一個(gè)函數(shù)f:S

C。f與f2被認(rèn)為“實(shí)際上”是一樣的，當(dāng)且僅當(dāng)在所允許的變換(即前面例子中的對(duì)稱旋轉(zhuǎn))下，f1能轉(zhuǎn)變?yōu)閒2或相反。而對(duì)稱旋轉(zhuǎn)即置換群的元素。我們稱“(置換)群作用于S，也作用于C。”其實(shí)我們看一下群與對(duì)稱更好額比立方體簡(jiǎn)單一點(diǎn)的例子3個(gè)黑珍珠和6個(gè)白珍珠能做出多少樣式不同的項(xiàng)鏈？

軸

翻轉(zhuǎn)順時(shí)針旋轉(zhuǎn)80

置換群誘導(dǎo)的等價(jià)關(guān)系假設(shè)G是集合X上的置換群。定義X上的關(guān)系“

”如下：

x,y

X,x

y

g

G,使得g(x)=y

“

”是等價(jià)關(guān)系自反性：置換群中的單位元素一定是恒等映射。對(duì)稱性：由群的逆元素性保證。傳遞性：由群的封閉性保證。將關(guān)系"

"所決定的等價(jià)類記為Gx:

Gx={y|y

X,且

g

G,使得g(x)=y}這樣的等價(jià)類稱為X上G的軌道。保持x不變的置換構(gòu)成子群G中所有“將x變?yōu)閥”的置換構(gòu)成的集合：

G(x

y)={g|g

G,且g(x)=y}G中所有“保持x不變”的置換的集合：

Gx={g|g

G,且g(x)=x}注意：Gx構(gòu)成子群(只需證明封閉性)。G(x

y)是Gx的右陪集：

h

G(x

y),G(x

y)=Gxh若

Gxh,令

=

h(

Gx),

則

x

X,

(x)=h(

(x))=h(x)=y,

G(x

y)若

G(x

y),

則

x

X,h-1(

(x))=h-1(y)=x,即

h-1

Gx,

Gxh

軌道的大小子群與相應(yīng)的陪集等勢(shì)，因此：若y

Gx,|G(x

y)|=|Gx|,否則|G(x

y)|=0。對(duì)任意xX,x所在的軌道的大小與保持x不變的置換的個(gè)數(shù)的乘積與x無關(guān)。給定x

X,構(gòu)造如下的矩陣：

y

g√g行y列有√表示：g(x)=y

對(duì)√計(jì)數(shù)：按行數(shù)：每行恰有1個(gè)√?？倲?shù)為|G|。按列數(shù)，若某個(gè)y

Gx,則該列恰有|G(x

y)|=|Gx|個(gè)√，否則為空列。所以：

|Gx|

|Gx|=|G|

y

Gx|Gy|值與所在軌道無關(guān)對(duì)任意的y

X,若y

Gx,則|Gx|=|Gy|實(shí)際上，G(x

y)是Gy的左陪集：即

h

G(x

y),G(x

y)=hGy若

hGy,令

=h

(

Gy),則

x

X,

(x)=

(h(x))=

(y)=y,

G(x

y)若

G(x

y),則

y

X,

(h-1(y))=

(x)=y,即h-1

Gy,

hGy所以，對(duì)每個(gè)軌道，

y

Gx|Gy|=|Gx|

|Gx|=|G|,

y

Gx|Gy|是“一個(gè)軌道中保持各元素不變的置換的總數(shù)”軌道的個(gè)數(shù)

令軌道數(shù)為t,因?yàn)槊總€(gè)軌道中保持各元素不變的置換的總數(shù)均為|G|,

x

X|Gx|=t?|G|。F(g)表示在置換g之下保持不變的x的個(gè)數(shù)。計(jì)算

g

G|F(g)|顯然比計(jì)算

x

X|Gx|容易，而且：

g

G|F(g)|=

x

X|Gx|利用下列矩陣計(jì)數(shù)：

x

g√g行x列有√表示：g(x)=x

按行算：每行√數(shù)是在置換g之下不變的x的個(gè)數(shù)。總數(shù)即

g

G|F(g)|按列算：每列√數(shù)是保持特定x不變的置換的個(gè)數(shù)，總數(shù)即

x

X|Gx|Burnside定理

x

X|Gx|=t?|G|

g

G|F(g)|=

x

X|Gx|於是：

項(xiàng)鏈問題的解3個(gè)黑珍珠和6個(gè)白珍珠能做出多少樣式不同的項(xiàng)鏈？|X|=84,即C93(Why?) |G|=189個(gè)旋轉(zhuǎn)，2個(gè)翻轉(zhuǎn)對(duì)每個(gè)翻轉(zhuǎn)g,|F(g)|=4旋轉(zhuǎn)0°的|F(g)|=84;旋轉(zhuǎn)120°和240°的|F(g)|各為3；