<小记>Polya定理

Polya定理用于等价类的计数
等价类:按照一定规则视为相同的一堆东西

\cfrac {\sum_{i=1}^n m^{k_i}} n

m:颜色数量
k_i:i种置换的循环的个数
n:点(?)的个数

考虑有4个点的环,给每个点染为红黄蓝三色中一种,旋转后颜色一样视为等价,求有几种不等价的染色方案

  1. 不转: 4个循环(1\rightarrow1, 2\rightarrow2,\dots,4\rightarrow4)
  2. 顺时针转1个点: 1个循环(1\rightarrow2\rightarrow3\rightarrow4\rightarrow\underline1)
  3. 顺时针转2个点: 2个循环(1\rightarrow3\rightarrow\underline1,2\rightarrow4\rightarrow\underline2)
  4. 顺时针转1个点: 1个循环(1\rightarrow4\rightarrow3\rightarrow2\rightarrow\underline1)

\cfrac {3^4 + 3^1 + 3^2 + 3^1} 4 = 24

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注