CPC 算法笔记——置换和 Polya 定理

1 min168 words

置换即 [ ⁣[1,n] ⁣]≜{1,2,…,n}[\![1, n]\!] \triangleq \{1, 2, \dots, n\} 到自身的 1-1 变换:[ ⁣[1,n] ⁣]→[ ⁣[1,n] ⁣][\![1, n]\!] \rightarrow [\![1, n]\!]

p:i→ai,(ai≠aj,i≠j)p: i \rightarrow a_i, (a_i \neq a_j, i \neq j),

其中 a1,a2,…,ana_1, a_2, \dots, a_n 是 [ ⁣[1,n] ⁣][\![1, n]\!] 的一个全排列,

nn 阶置换共有 n!n! 个。