置換群在計(jì)數(shù)中的應(yīng)用置換群在計(jì)數(shù)中的應(yīng)用11你要知道置換群是什么鬼1你要知道置換群是什么鬼2一．置換群的基本概念定義1任一集合A到自身的映射都叫做的A一個(gè)變換，如果A是有限集且變換是一一變換（雙射），那么這個(gè)變換為A的一個(gè)置換。有限集合A的若干個(gè)置換若作成群，就叫做置換群。含有n個(gè)元素的有限群A的全體置換作成的群，叫做n次對(duì)稱(chēng)群。通常記為Sn。一．置換群的基本概念3置換群是一種特殊的變換群。換句話(huà)說(shuō)，置換群就是有限集上的變換群。由于是定義在有限集上，故每個(gè)置換的表現(xiàn)形式，固有特點(diǎn)都是可揣測(cè)的。大家應(yīng)該知道什么是變換群吧？封閉性、可結(jié)合、有單位元、存在逆元置換群是一種特殊的變換群。換句話(huà)說(shuō)，置換群就是有限集上的變4置換群在計(jì)數(shù)中的應(yīng)用2021完整版課件5置換群在計(jì)數(shù)中的應(yīng)用2021完整版課件6舉個(gè)栗子舉個(gè)栗子7g√g行x列有√表示：g(x)=x傳遞性：由群的封閉性保證。將關(guān)系""所決定的等價(jià)類(lèi)記為Gx:而對(duì)稱(chēng)旋轉(zhuǎn)即置換群的元素。|X|=84,即C93(Why?)G(xy)={g|gG,且g(x)=y}x定義X上的關(guān)系“”如下：我們稱(chēng)“(置換)群作用于S，也作用于C。其實(shí)我們看一下群與對(duì)稱(chēng)更好額給定xX,構(gòu)造如下的矩陣：定義1任一集合A到自身的映射都叫做的A一個(gè)而對(duì)稱(chēng)旋轉(zhuǎn)即置換群的元素。因此：不同的著色有6!/(6+3+6+8+1)=30種x,yX,xygG,使得g(x)=y對(duì)每個(gè)翻轉(zhuǎn)g,|F(g)|=4p119g√g行x列有√8置換群在計(jì)數(shù)中的應(yīng)用2021完整版課件9關(guān)于循環(huán)置換關(guān)于循環(huán)置換102這個(gè)置換群在計(jì)數(shù)中到底有什么應(yīng)用2這個(gè)置換群在計(jì)數(shù)中到底有什么應(yīng)用11等價(jià)類(lèi)計(jì)數(shù)等價(jià)類(lèi)計(jì)數(shù)12瞅一道題吧用6種不同顏色給正方體的六個(gè)面著色，每個(gè)面有6中選擇，假如給定每個(gè)面的編號(hào)，不同的著色序列有6！(=720)個(gè)，但哪些是“真正”不同的？因此：不同的著色有6!/(6+3+6+8+1)=30種901801801206種3種6種8種1種瞅一道題吧用6種不同顏色給正方體的六個(gè)面著色，每個(gè)面有6中選13其實(shí)我并沒(méi)有看太明白其實(shí)我并沒(méi)有看太明白14接下來(lái)我就要介紹一種簡(jiǎn)單粗暴的方法接下來(lái)我就要介紹一種簡(jiǎn)單粗暴的方法15如果不是每個(gè)面的著色都不同,比如有兩個(gè)面是紅的，如何判斷兩種著色是“真正”不同？設(shè)著色對(duì)象的集合是S，允許使用的顏色的集合是C(我們只考慮有限集)。一種著色方案就是一個(gè)函數(shù)f:SC。f與f2被認(rèn)為“實(shí)際上”是一樣的，當(dāng)且僅當(dāng)在所允許的變換(即前面例子中的對(duì)稱(chēng)旋轉(zhuǎn))下，f1能轉(zhuǎn)變?yōu)閒2或相反。而對(duì)稱(chēng)旋轉(zhuǎn)即置換群的元素。我們稱(chēng)“(置換)群作用于S，也作用于C?！逼鋵?shí)我們看一下群與對(duì)稱(chēng)更好額如果不是每個(gè)面的著色都不同,比如有兩個(gè)面是紅的，如何判斷兩16比立方體簡(jiǎn)單一點(diǎn)的例子3個(gè)黑珍珠和6個(gè)白珍珠能做出多少樣式不同的項(xiàng)鏈？軸翻轉(zhuǎn)順時(shí)針旋轉(zhuǎn)80比立方體簡(jiǎn)單一點(diǎn)的例子3個(gè)黑珍珠和6個(gè)白珍珠能做出多少樣式不17置換群誘導(dǎo)的等價(jià)關(guān)系假設(shè)G是集合X上的置換群。定義X上的關(guān)系“”如下：x,yX,xy

gG,使得g(x)=y

“”是等價(jià)關(guān)系自反性：置換群中的單位元素一定是恒等映射。對(duì)稱(chēng)性：由群的逆元素性保證。傳遞性：由群的封閉性保證。將關(guān)系""所決定的等價(jià)類(lèi)記為Gx:

Gx={y|yX,且gG,使得g(x)=y}這樣的等價(jià)類(lèi)稱(chēng)為X上G的軌道。置換群誘導(dǎo)的等價(jià)關(guān)系假設(shè)G是集合X上的置換群。定義X上的關(guān)18保持x不變的置換構(gòu)成子群G中所有“將x變?yōu)閥”的置換構(gòu)成的集合：

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

Gx={g|gG,且g(x)=x}注意：Gx構(gòu)成子群(只需證明封閉性)。G(xy)是Gx的右陪集：hG(xy),G(xy)=Gxh若Gxh,令=h(Gx),

則xX,(x)=h((x))=h(x)=y,G(xy)若G(xy),

則xX,h-1((x))=h-1(y)=x,即h-1Gx,Gxh

保持x不變的置換構(gòu)成子群G中所有“將x變?yōu)閥”的置換構(gòu)成的集19軌道的大小子群與相應(yīng)的陪集等勢(shì)，因此：若yGx,|G(xy)|=|Gx|,否則|G(xy)|=0。對(duì)任意xX,x所在的軌道的大小與保持x不變的置換的個(gè)數(shù)的乘積與x無(wú)關(guān)。給定xX,構(gòu)造如下的矩陣：

y

g√g行y列有√表示：g(x)=y對(duì)√計(jì)數(shù)：按行數(shù)：每行恰有1個(gè)√。總數(shù)為|G|。按列數(shù)，若某個(gè)yGx,則該列恰有|G(xy)|=|Gx|個(gè)√，否則為空列。所以：

|Gx||Gx|=|G|

軌道的大小子群與相應(yīng)的陪集等勢(shì)，因此：若yGx,|G(x20yGx|Gy|值與所在軌道無(wú)關(guān)對(duì)任意的yX,若yGx,則|Gx|=|Gy|實(shí)際上，G(xy)是Gy的左陪集：即hG(xy),G(xy)=hGy若hGy,令=h(Gy),則xX,(x)=(h(x))=(y)=y,G(xy)若G(xy),則yX,(h-1(y))=(x)=y,即h-1Gy,

hGy所以，對(duì)每個(gè)軌道，yGx|Gy|=|Gx||Gx|=|G|,

yGx|Gy|是“一個(gè)軌道中保持各元素不變的置換的總數(shù)”yGx|Gy|值與所在軌道無(wú)關(guān)對(duì)任意的yX,若yG21軌道的個(gè)數(shù)

令軌道數(shù)為t,因?yàn)槊總€(gè)軌道中保持各元素不變的置換的總數(shù)均為|G|,xX|Gx|=t?|G|。F(g)表示在置換g之下保持不變的x的個(gè)數(shù)。計(jì)算gG|F(g)|顯然比計(jì)算xX|Gx|容易，而且：

gG|F(g)|=xX|Gx|利用下列矩陣計(jì)數(shù)：

x

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

按行算：每行√數(shù)是在置換g之下不變的x的個(gè)數(shù)?？倲?shù)即gG|F(g)|按列算：每列√數(shù)是保持特定x不變的置換的個(gè)數(shù)，總數(shù)即xX|Gx|軌道的個(gè)數(shù)令軌道數(shù)為t,因?yàn)槊總€(gè)軌道中保持各元素不變的置22Burnside定理xX|Gx|=t?|G|gG|F(g)|=xX|Gx|於是：

Burnside定理xX|Gx|=t?|G|23置換群在計(jì)數(shù)中的應(yīng)用2021完整版課件24項(xiàng)鏈問(wèn)題的解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；其它均為0。結(jié)果是：(4?9+84+3?2)/18=

⑦軸翻轉(zhuǎn)順時(shí)針旋轉(zhuǎn)80F(g)表示在置換g之下保持不變的x的個(gè)數(shù)項(xiàng)鏈問(wèn)題的解3個(gè)黑珍珠和6個(gè)白珍珠能做出多少樣式不同的項(xiàng)鏈？25置換群在計(jì)數(shù)中的應(yīng)用2021完整版課件26置換群在計(jì)數(shù)中的應(yīng)用2021完整版課件27置換群在計(jì)數(shù)中的應(yīng)用2021完整版課件28置換群在計(jì)數(shù)中的應(yīng)用置換群在計(jì)數(shù)中的應(yīng)用291你要知道置換群是什么鬼1你要知道置換群是什么鬼30一．置換群的基本概念定義1任一集合A到自身的映射都叫做的A一個(gè)變換，如果A是有限集且變換是一一變換（雙射），那么這個(gè)變換為A的一個(gè)置換。有限集合A的若干個(gè)置換若作成群，就叫做置換群。含有n個(gè)元素的有限群A的全體置換作成的群，叫做n次對(duì)稱(chēng)群。通常記為Sn。一．置換群的基本概念31置換群是一種特殊的變換群。換句話(huà)說(shuō)，置換群就是有限集上的變換群。由于是定義在有限集上，故每個(gè)置換的表現(xiàn)形式，固有特點(diǎn)都是可揣測(cè)的。大家應(yīng)該知道什么是變換群吧？封閉性、可結(jié)合、有單位元、存在逆元置換群是一種特殊的變換群。換句話(huà)說(shuō)，置換群就是有限集上的變32置換群在計(jì)數(shù)中的應(yīng)用2021完整版課件33置換群在計(jì)數(shù)中的應(yīng)用2021完整版課件34舉個(gè)栗子舉個(gè)栗子35g√g行x列有√表示：g(x)=x傳遞性：由群的封閉性保證。將關(guān)系""所決定的等價(jià)類(lèi)記為Gx:而對(duì)稱(chēng)旋轉(zhuǎn)即置換群的元素。|X|=84,即C93(Why?)G(xy)={g|gG,且g(x)=y}x定義X上的關(guān)系“”如下：我們稱(chēng)“(置換)群作用于S，也作用于C。其實(shí)我們看一下群與對(duì)稱(chēng)更好額給定xX,構(gòu)造如下的矩陣：定義1任一集合A到自身的映射都叫做的A一個(gè)而對(duì)稱(chēng)旋轉(zhuǎn)即置換群的元素。因此：不同的著色有6!/(6+3+6+8+1)=30種x,yX,xygG,使得g(x)=y對(duì)每個(gè)翻轉(zhuǎn)g,|F(g)|=4p119g√g行x列有√36置換群在計(jì)數(shù)中的應(yīng)用2021完整版課件37關(guān)于循環(huán)置換關(guān)于循環(huán)置換382這個(gè)置換群在計(jì)數(shù)中到底有什么應(yīng)用2這個(gè)置換群在計(jì)數(shù)中到底有什么應(yīng)用39等價(jià)類(lèi)計(jì)數(shù)等價(jià)類(lèi)計(jì)數(shù)40瞅一道題吧用6種不同顏色給正方體的六個(gè)面著色，每個(gè)面有6中選擇，假如給定每個(gè)面的編號(hào)，不同的著色序列有6！(=720)個(gè)，但哪些是“真正”不同的？因此：不同的著色有6!/(6+3+6+8+1)=30種901801801206種3種6種8種1種瞅一道題吧用6種不同顏色給正方體的六個(gè)面著色，每個(gè)面有6中選41其實(shí)我并沒(méi)有看太明白其實(shí)我并沒(méi)有看太明白42接下來(lái)我就要介紹一種簡(jiǎn)單粗暴的方法接下來(lái)我就要介紹一種簡(jiǎn)單粗暴的方法43如果不是每個(gè)面的著色都不同,比如有兩個(gè)面是紅的，如何判斷兩種著色是“真正”不同？設(shè)著色對(duì)象的集合是S，允許使用的顏色的集合是C(我們只考慮有限集)。一種著色方案就是一個(gè)函數(shù)f:SC。f與f2被認(rèn)為“實(shí)際上”是一樣的，當(dāng)且僅當(dāng)在所允許的變換(即前面例子中的對(duì)稱(chēng)旋轉(zhuǎn))下，f1能轉(zhuǎn)變?yōu)閒2或相反。而對(duì)稱(chēng)旋轉(zhuǎn)即置換群的元素。我們稱(chēng)“(置換)群作用于S，也作用于C?！逼鋵?shí)我們看一下群與對(duì)稱(chēng)更好額如果不是每個(gè)面的著色都不同,比如有兩個(gè)面是紅的，如何判斷兩44比立方體簡(jiǎn)單一點(diǎn)的例子3個(gè)黑珍珠和6個(gè)白珍珠能做出多少樣式不同的項(xiàng)鏈？軸翻轉(zhuǎn)順時(shí)針旋轉(zhuǎn)80比立方體簡(jiǎn)單一點(diǎn)的例子3個(gè)黑珍珠和6個(gè)白珍珠能做出多少樣式不45置換群誘導(dǎo)的等價(jià)關(guān)系假設(shè)G是集合X上的置換群。定義X上的關(guān)系“”如下：x,yX,xy

gG,使得g(x)=y

“”是等價(jià)關(guān)系自反性：置換群中的單位元素一定是恒等映射。對(duì)稱(chēng)性：由群的逆元素性保證。傳遞性：由群的封閉性保證。將關(guān)系""所決定的等價(jià)類(lèi)記為Gx:

Gx={y|yX,且gG,使得g(x)=y}這樣的等價(jià)類(lèi)稱(chēng)為X上G的軌道。置換群誘導(dǎo)的等價(jià)關(guān)系假設(shè)G是集合X上的置換群。定義X上的關(guān)46保持x不變的置換構(gòu)成子群G中所有“將x變?yōu)閥”的置換構(gòu)成的集合：

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

Gx={g|gG,且g(x)=x}注意：Gx構(gòu)成子群(只需證明封閉性)。G(xy)是Gx的右陪集：hG(xy),G(xy)=Gxh若Gxh,令=h(Gx),

則xX,(x)=h((x))=h(x)=y,G(xy)若G(xy),

則xX,h-1((x))=h-1(y)=x,即h-1Gx,Gxh

保持x不變的置換構(gòu)成子群G中所有“將x變?yōu)閥”的置換構(gòu)成的集47軌道的大小子群與相應(yīng)的陪集等勢(shì)，因此：若yGx,|G(xy)|=|Gx|,否則|G(xy)|=0。對(duì)任意xX,x所在的軌道的大小與保持x不變的置換的個(gè)數(shù)的乘積與x無(wú)關(guān)。給定xX,構(gòu)造如下的矩陣：

y

g√g行y列有√表示：g(x)=y對(duì)√計(jì)數(shù)：按行數(shù)：每行恰有1個(gè)√?？倲?shù)為|G|。按列數(shù)，若某個(gè)yGx,則該列恰有|G(xy)|=|Gx|個(gè)√，否則為空列。所以：

|Gx||Gx|=|G|

軌道的大小子群與相應(yīng)的陪集等勢(shì)，因此：若yGx,|G(x48yGx|Gy|值與所在軌道無(wú)關(guān)對(duì)任意的yX,若yGx,則|Gx|=|Gy|實(shí)際上，G(xy)是Gy的左陪集：即hG(xy),G(xy)=hGy若hGy,令=h(Gy),則xX,(x)=(h(x))=(y)=y,G(xy)若G(xy),則yX,(h-1(y))=(x)=y,即h-1Gy,

hGy所以，對(duì)每個(gè)軌道，yGx|Gy|=|Gx||Gx|=|G|,

yGx|Gy|是“一個(gè)軌道中保持各元素不變的置換的總數(shù)”yGx|Gy|值與所在軌道無(wú)關(guān)對(duì)任意的yX,若yG49軌道的個(gè)數(shù)

令軌道數(shù)為t,因?yàn)槊總€(gè)軌道中保持各元素不變的置換的總數(shù)均為|G|,xX|Gx|=t?|G|。F(g)表示在置換g之下保持不變的x的個(gè)數(shù)。計(jì)算gG|F(g)|