第四百零五章 伯恩賽德引理（圖論）

　　1902年，伯恩賽德提出了伯恩賽德引理。

　　一個(gè)由2*2方格組成的正方形，每個(gè)格子上可以涂色或不涂色，問(wèn)共有多少種本質(zhì)不同的涂色方案。

　　每個(gè)格子可以涂色，可以不涂色，共有16種方案。將16種方案編號(hào)。

　　把本質(zhì)相同的方案合并：方案1：{1}，方案2：{2}，方案3：{3，4，5，6}，方案4：{7，8，9，10}，方案5：{11，12}，方案6：{13，14，15，16}，共6種方案。

　　旋轉(zhuǎn)可以看作是置換，所有置換組成置換群。

　　如果x通過(guò)某個(gè)置換可以變成y，說(shuō)明x和y等價(jià)。

　　與x互相等價(jià)的一組元素組成了一個(gè)集合，稱為x的等價(jià)類。

　　這個(gè)問(wèn)題中，我們要求的就是這樣的等價(jià)類有多少個(gè)。

　　我們由Burnside's lemma 可得一種公式，這個(gè)公式的意思是：等價(jià)類的個(gè)數(shù)=每個(gè)置換中不動(dòng)元的個(gè)數(shù)和÷置換群大小。|X/G|=（16+2+4+4）/4=6。

　　也可說(shuō)為等價(jià)類個(gè)數(shù)=不動(dòng)元個(gè)數(shù)的平均數(shù)