跳转至

Polya计数

无限制环染色问题：例如计算不同颜色的珠子串成的项链有多少种不同的排列方式，考虑到项链旋转对称性，这个问题就可以用置换群计数理论来解决。

基础知识

建议回顾一下映射，看一下ref。

置换

一个有限集合 \(S\) 到自身的双射（一一对应，唯一性）称为 \(S\) 的一个置换。集合 \(S=\{a_1,a_2,\dots,a_n\}\) 上的置换可以表示为

\[ f=\begin{pmatrix}a_1,a_2,\dots,a_n\\ a_{p_1},a_{p_2},\dots,a_{p_n} \end{pmatrix} \]

意为将 \(a_i\) 变为 \(a_{p_i}\)，其中 \(p_1,p_2,\dots,p_n\) 是 \(1,2,\dots,n\) 的一个排列。显然 \(S\) 上所有置换的数量为 \(n!\)。连续的两次置换可以 复合 成一个置换。

置换群

置换的集合与置换复合运算构成的群。集合 \(S\) 上的 所有置换 关于其复合运算满足封闭性、结合律（类似矩阵乘法）、有单位元（恒等置换，即每个元素映射成它自己）、有逆元（交换置换表示中的上下两行），因此构成一个群。所有置换构成的群，其任意一个 子群 都是 置换群。

循环置换

也叫轮换。循环置换是一类特殊的置换，可表示为

\[ (a_1,a_2,\dots,a_m)=\begin{pmatrix}a_1,a_2,\dots,a_{m-1},a_m\\ a_2,a_3,\dots,a_m,a_1\end{pmatrix} \]

若两个循环置换不含有相同的元素，则称它们是 不相交 的。有如下定理：

任意一个置换都可以分解为若干不相交的循环置换的乘积，例如

\[ \begin{pmatrix}a_1,a_2,a_3,a_4,a_5\\ a_3,a_1,a_2,a_5,a_4\end{pmatrix}=(a_1,a_3,a_2)\circ(a_4,a_5) \]

该定理的证明也非常简单。如果把元素视为图的节点，映射关系视为有向边，则每个节点的入度和出度都为 1，因此形成的图形必定是若干个环的集合，而一个环即可用一个循环置换表示。

置换的循环节数：循环置换乘积表示中循环的个数，上例中为 2。

Burnside 引理

建议先跳过定义，先跟着例子套一遍公式。

定义

设 \(A\) 和 \(B\) 为有限集合，\(X\) 为 一些 从 \(A\) 到 \(B\) 的映射组成的集合。
\(G\) 是 \(A\) 上的置换群，且 \(X\) 中的映射在 \(G\) 中的置换作用下封闭。
\(X/G\) 表示 \(G\) 作用在 \(X\) 上产生的所有等价类的集合
（若 \(X\) 中的两个映射经过 \(G\) 中的置换作用后相等，则它们在同一等价类中），则

\[ |X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g| \]

其中 \(|S|\) 表示集合 \(S\) 中元素的个数，且

\[ X^g=\{x|x\in X,g(x)=x\} \]

证明 - OI Wiki

例子

我们以给立方体染色RGB为例子，令立方体第 1~6 个面依次为前、后、上、下、左、右，一种染色方案对应一种映射（=函数）关系，例如：

\[ (a_1,a_2,a_3,a_4,a_5,a_6)=(R,R,R,R,G,B) \]

把翻转用置换表示，比如，以左右两个面中心连线为轴，向上 \(90^\circ\) 旋转的翻转操作：

\[ \begin{pmatrix}a_1,a_2,a_3,a_4,a_5,a_6\\ a_4,a_3,a_1,a_2,a_5,a_6 \end{pmatrix} = (a_1,a_4,a_2,a_3)(a_5)(a_6) \]

这时把公式中一些符号的解释如下：

  • \(A\)：映射定义域，立方体 6 个面的集合 \(\{a_1,\cdots,a_6\}\)
  • \(B\)：包含映射值域的父集，本题中 \(B\) 恰好就是值域，即 3 种颜色的集合 \(\{R,G,B\}\)
  • \(|X/G|\)：答案，本质不同的染色方案数，本质相同的算作一个 等价类
  • \(|X|\)：不考虑等价，所有的染色方案数，\(3^6\)
  • \(G\)：所有合法的置换，这里是旋转、翻转。
  • \(|X^g|\)：对于某一步置换 \(g\)，所有染色方案中，经过 \(g\) 这种置换后染色仍然不变的方案数

例如上面的例子，则必须要满足上、下、前、后 4 个面的颜色一样，才能使旋转后不变，因此它对应的染色方案 \(|X^g|=3^3\)。本题中，底数恰是总颜色数，指数是置换的循环节数，这是巧合吗？（见：Polya计数 > Pólya 定理）

进一步的，也是最核心的，我们对所有置换进行分析，请有条理地考虑所有的一步置换！置换操作不能分步，而是一步到位，然后考虑变换前后不动的颜色

  • 不动：即恒等变换，因为所有直接染色方案经过恒等变换都不变，因此它对应的 \(|X^g|=3^6\)
  • 以两个相对面的中心连线为轴的 \(90^\circ\) 旋转：我们选取正反 \(90^\circ\) 旋转、选取左右、上下、前后为轴，不变的染色方案数 \(|X^g|=3^3\) 相同，故可以统一计算，共 \(2\times3=6\) 种。
  • 以两个相对面的中心连线为轴的 \(180^\circ\) 旋转：相对面有 3 种选择，旋转方向的选择对置换不再有影响，因此这类共有 3 个置换。假设选择了前、后两个面中心的连线为轴，则必须要满足上、下两个面的颜色一样，左、右两个面的颜色一样，才能使旋转后不变，因此它对应的 \(|X^g|=3^4\)
  • 以两条相对棱的中点连线为轴的 \(180^\circ\) 旋转：相对棱有 6 种选择，旋转方向对置换依然没有影响，因此这类共有 6 个置换。假设选择了前、上两个面的边界和下、后两个面的边界作为相对棱，则必须要满足前、上两个面的颜色一样，下、后两个面的颜色一样，左、右两个面的颜色一样，才能使旋转后不变，因此它对应的 \(|X^g|=3^3\)
  • 以两个相对顶点的连线为轴的 \(120^\circ\) 旋转：相对顶点有 4 种选择，旋转的方向有两种选择，因此这类共有 8 个置换。假设选择了前面的右上角和后面的左下角作为相对顶点，则必须满足前、上、右三个面的颜色一样，后、下、左三个面的颜色一样，才能使旋转后不变，因此它对应的 \(|X^g|=3^2\)

会不会有置换没有考虑全呢？确实可能。但是我们可以通过最基本的几个置换的复合，得出完整的置换群来检验一下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>

using LL = long long;
using ull = unsigned long long;
using std::cin;
using std::cout;

std::vector<int> operator*(const std::vector<int>& a,
                           const std::vector<int>& b) {
    std::vector<int> ans(a.size(), 0);
    for (int i = 1; i < ans.size(); i++) { ans[i] = b[a[i]]; }
    return ans;
}

struct Perm_Counter {
    std::vector<std::vector<int>> perms;
    std::set<std::vector<int>> s;
    Perm_Counter(std::initializer_list<std::vector<int>> lst) : perms(lst) {}
    void count() {
        std::vector<int> id(1, 0);
        for (int i = 1; i < perms[0].size(); i++) id.push_back(i);
        _count(0, id);
        cout << s.size() << std::endl;
    }
    void _count(int siz, std::vector<int> perm) {
        if (siz == perms.size()) {
            s.insert(perm);
            return;
        }
        auto x = perms[siz];
        for (int i = 1; i < perm.size(); i++) {
            _count(siz + 1, perm * x);
            x = x * perms[siz];
        }
    }
};

int main() {
    Perm_Counter s{
        {0, 4, 3, 1, 2, 5, 6}, {0, 5, 6, 3, 4, 2, 1}, {0, 1, 2, 6, 5, 3, 4}};
    s.count();
    return 0;
}

套公式，所有本质不同的方案数为

\[ \frac{1}{1+6+3+6+8}(1\times3^6+6\times3^3+3\times3^4+6\times3^3+8\times3^2)=57 \]

Pólya 定理

定义

特殊的 Burnside 引理。若 \(X\) 为 所有 从 \(A\) 到 \(B\) 的映射，公式可变形为

\[ |X/G|=\frac{1}{|G|}\sum_{g\in G}|B|^{c(g)} \]

其中 \(c(g)\) 表示置换 \(g\) 能拆分成的不相交的循环置换（循环节数）的数量。

由于每个面涂颜色没有任何限制，也就说 \(A\) 到 \(B\) 的所有映射（所有染色方案）都可以合法，故每个循环节涂同一种颜色即可，每个置换对应的涂色方案 \(|X^g|=|B|^{c(g)}\)。

手环计数

6个珠子的手环涂3种颜色，有多少种本质不同的结构？

References

置换和轮换（新姿势，摘自黑书）-CSDN博客

【组合数学】Pólya 计数理论_polya计数-CSDN博客

高中数学必修一告诉我们，映射=函数。集合 \(A,B\) 的元素个数为 \(m,n\)，那么，所有 \(f:A\rightarrow B\) 的个数为 \(n^m\)，这里面包含了不满的映射。