（組合數學筆記）Pólya計數理論_Part.4_Burnside引理

文章目錄

• ​​Burnside引理​​

• ​​Burnside引理（軌道計數定理，等價類計數定理）​​

• ​​證明​​

• ​​軌道計數示例​​

• ​​定理​​
• ​​推論​​

Burnside引理

Burnside引理（軌道計數定理，等價類計數定理）

設是元集上的置換群，表示的軌道集，則：

其中是置換的循環分解式中循環的個數，即置換的不動點的個數。

證明

（殊途同歸原理）

軌道計數示例

一般稱為由上的置換群所導出的上的置換群。

易證：（同構），映射就是群到群的同構映射。

定理

設是對象集，是顔色集，是上的置換群，是由導出的上的置換群，對于，使得

推論