Burnside và Polya (Đếm với đối xứng)

Wiki › Thuật toán › Toán học

Burnside và Polya (Đếm với đối xứng)

huunguyen · Last updated 8, Tháng 4, 2026, 16:20

Bổ đề Burnside và Định lý Polya đếm số cấu hình phân biệt về mặt đối xứng — hai cấu hình được coi là giống nhau nếu có thể chuyển từ cái này sang cái kia bằng một phép biến đổi trong nhóm đối xứng.

Bổ đề Burnside

Số quỹ đạo phân biệt (số cấu hình khác nhau) dưới tác dụng của nhóm $G$ :

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

trong đó $| X^{g} |$ là số phần tử của tập $X$ bất động (fixed) dưới phép biến đổi $g$ .

Ví dụ 1: Tô màu vòng tròn

Đếm số vòng chuỗi $n$ hạt, mỗi hạt $k$ màu, phân biệt khi không thể xoay thành nhau.

Nhóm $G$ = nhóm quay $ℤ_{n}$ (xoay $0 °, 360 ° / n, \dots$ ).

Phép quay $r^{j}$ (xoay $j$ vị trí): số hạt bất động = số chuỗi bất biến khi xoay $j$ bước.

Chuỗi bất biến khi xoay $j$ bước ⟺ chu kỳ $j$ chia $n$ ⟺ số màu $^{gcd (n, j)}$ .

Số chuỗi = \frac{1}{n} \sum_{j = 0}^{n - 1} k^{gcd (n, j)}

long long count_necklace(int n, int k, long long MOD) {
    long long ans = 0;
    for (int j = 0; j < n; j++) {
        int g = __gcd(n, j == 0 ? n : j);
        ans = (ans + power(k, g, MOD)) % MOD;
    }
    return ans * power(n, MOD - 2, MOD) % MOD;
}

Ví dụ 2: Tô màu mặt xúc xắc

Đếm số cách tô 6 mặt xúc xắc với $k$ màu, phân biệt khi không thể xoay thành nhau.

Nhóm quay khối lập phương có $| G | = 24$ phép quay. Tính $| X^{g} |$ cho từng loại phép quay:

// Nhóm quay khối lập phương: 24 phép quay
// Phân loại:
// - 1 phép đơn vị: fix k^6
// - 6 phép quay mặt 90°/270°: fix k^3
// - 3 phép quay mặt 180°: fix k^4
// - 8 phép quay đỉnh 120°/240°: fix k^2
// - 6 phép quay cạnh 180°: fix k^3

long long count_dice(int k, long long MOD) {
    long long ans = 0;
    ans = (power(k, 6, MOD)         // 1 phép đơn vị
         + 6 * power(k, 3, MOD)     // quay mặt 90°/270°
         + 3 * power(k, 4, MOD)     // quay mặt 180°
         + 8 * power(k, 2, MOD)     // quay đỉnh
         + 6 * power(k, 3, MOD))    // quay cạnh
        % MOD;
    return ans * power(24, MOD - 2, MOD) % MOD;
}

Định lý Polya (tổng quát hơn)

Polya mở rộng Burnside cho phép đếm theo trọng số. Với nhóm $G$ tác dụng lên tập vị trí $[n]$ , và tập màu $C$ :

Cycle index của $G$ :

Z (G) = \frac{1}{| G |} \sum_{g \in G} a_{1}^{c_{1} (g)} a_{2}^{c_{2} (g)} \dots a_{n}^{c_{n} (g)}

trong đó $c_{k} (g)$ = số chu trình độ dài $k$ trong hoán vị $g$ .

Số cấu hình với $m$ màu = $Z (G)$ thay $a_{i} \leftarrow m$ .

// Cycle index của Z_n (nhóm quay n vị trí)
// Z(Z_n) = (1/n) * sum_{j=0}^{n-1} prod a_{d} với d = n/gcd(n,j), số lần = gcd(n,j)
// Thay a_i = m: Z = (1/n) * sum_{j=0}^{n-1} m^{gcd(n,j)}
// (trùng với công thức Burnside ở trên)

Ví dụ 3: Vòng chuỗi có lật (Dihedral group)

Nhóm đối xứng $D_{n}$ gồm $n$ xoay + $n$ lật (flip). Cần tính thêm phần cố định của $n$ phép lật:

long long count_bracelet(int n, int k, long long MOD) {
    // n phép quay: sum k^{gcd(n,j)} / n (như trên)
    long long ans = 0;
    for (int j = 0; j < n; j++)
        ans = (ans + power(k, __gcd(n, j == 0 ? n : j), MOD)) % MOD;

    // n phép lật:
    if (n % 2 == 0) {
        // n/2 lật qua đỉnh: fix k^{n/2+1}
        // n/2 lật qua cạnh: fix k^{n/2}
        ans = (ans + n / 2 * power(k, n/2 + 1, MOD)) % MOD;
        ans = (ans + n / 2 * power(k, n/2, MOD)) % MOD;
    } else {
        // n lật qua đỉnh: fix k^{(n+1)/2}
        ans = (ans + n * power(k, (n+1)/2, MOD)) % MOD;
    }

    return ans * power(2 * n, MOD - 2, MOD) % MOD;
}

Công thức tổng quát

Nhóm	Kích thước	Ứng dụng
$ℤ_{n}$ (xoay)	$n$	Vòng chuỗi (necklace)
$D_{n}$ (xoay + lật)	$2 n$	Vòng chuỗi có lật (bracelet)
$S_{4}$ quay khối lập phương	$24$	Tô màu mặt/đỉnh xúc xắc
Hoán vị bất kỳ	$\| G \|$	Mọi bài toán đếm đối xứng

Khi nào dùng Burnside/Polya?

Đếm cấu hình "phân biệt đến đối xứng": vòng chuỗi, đồ thị không nhãn, tô màu đa giác.
Nhận ra dạng bài: "hai cấu hình giống nhau nếu có thể xoay/lật/hoán vị thành nhau".
Khi đáp án lớn → tính mod nguyên tố (cần nghịch đảo $| G |$ ).

Bình luận

Không có bình luận tại thời điểm này.