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

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

90

180

180

120

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

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

軸

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

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

”如下：

x,y

X,x

y

g

G,使得g(x)=y

“

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

"所決定的等價類記為Gx:

Gx={y|y

X,且

g

G,使得g(x)=y}這樣的等價類稱為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)的陪集等勢，因此：若y

Gx,|G(x

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

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

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

y

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

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

Gx,則該列恰有|G(x

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

|Gx|

|Gx|=|G|

y

Gx|Gy|值與所在軌道無關(guān)對任意的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所以，對每個軌道，

y

Gx|Gy|=|Gx|

|Gx|=|G|,

y

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

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

x

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

g

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

x

X|Gx|容易，而且：

g

G|F(g)|=

x

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

x

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

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

g

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

x

X|Gx|Burnside定理

x

X|Gx|=t?|G|

g

G|F(g)|=

x

X|Gx|於是：

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