Wiki › Thuật toán › Toán học › Burnside và Polya (Đếm với đối xứng)

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

huunguyen Updated Tháng sáu 1, 2026

Bổ đề Burnside và Định lý Polya giải bài toán đếm số cấu hình phân biệt khi đã tính đến đối xứng: hai cấu hình được coi là giống nhau nếu có thể biến cái này thành cái kia bằng một phép biến đổi trong nhóm đối xứng (xoay, lật, hoán vị nhãn...). Ví dụ kinh điển: đếm số vòng cổ $n$ hạt với $m$ màu, trong đó xoay vòng đi một góc không tạo ra vòng mới.

Cách ngây thơ là sinh ra tất cả $m^{n}$ cấu hình rồi gom nhóm các cấu hình tương đương — vừa tốn bộ nhớ vừa chậm theo cấp số nhân. Burnside biến bài toán thành một tổng chạy trên các phép biến đổi của nhóm (thường chỉ vài hoặc vài chục phép, hoặc $n$ phép xoay), đưa độ phức tạp về đa thức. Với vòng cổ, công thức rút gọn còn $O (n \log n)$ thay vì $O (m^{n})$ .

Ý tưởng / Trực giác

Gọi $X$ là tập tất cả cấu hình (kể cả các cấu hình tương đương nhau), và $G$ là nhóm các phép biến đổi (ví dụ nhóm xoay $ℤ_{n}$ ). Hai cấu hình "giống nhau" khi có một $g \in G$ biến cái này thành cái kia. Tập các cấu hình giống nhau gọi là một quỹ đạo (orbit). Câu hỏi đếm-có-đối-xứng chính là: có bao nhiêu quỹ đạo?

Bổ đề Burnside cho công thức:

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

trong đó $| X^{g} |$ = số cấu hình bất động (fixed) dưới $g$ , tức $g$ tác động vào nó mà nó không đổi.

Vì sao công thức này đúng? Đếm theo hai cách số cặp $(g, x)$ thoả $g \cdot x = x$ (phép $g$ giữ nguyên cấu hình $x$ ):

Gom theo $g$ : tổng $\sum_{g} | X^{g} |$ .
Gom theo $x$ : với mỗi $x$ , số $g$ giữ nguyên nó là kích thước nhóm con ổn định (stabilizer) $| G_{x} |$ . Theo định lý quỹ đạo–ổn định, $| G_{x} | = | G | / | orbit (x) |$ . Cộng trên cả một quỹ đạo gồm $| orbit |$ phần tử, mỗi phần tử đóng góp $| G | / | orbit |$ , nên một quỹ đạo đóng góp đúng $| G |$ . Vậy $\sum_{x} | G_{x} | = | G | \cdot (số quỹ đạo)$ .

Cho hai cách bằng nhau rồi chia cho $| G |$ , ta được công thức. Trực giác: trung bình số điểm bất động trên toàn nhóm chính bằng số quỹ đạo.

Trực giác cho phần $| X^{g} |$ trong tô màu. Một phép $g$ là một hoán vị các vị trí. Hoán vị này phân rã thành các chu trình (cycle). Cấu hình bất động dưới $g$ khi và chỉ khi mọi vị trí trong cùng một chu trình có cùng màu (vì $g$ luân chuyển chúng cho nhau). Mỗi chu trình tự do chọn 1 trong $m$ màu, nên nếu $g$ có $c (g)$ chu trình thì $| X^{g} | = m^{c (g)}$ . Đây là cầu nối tới Polya.

Với phép xoay $j$ vị trí trên vòng $n$ hạt, hoán vị vị trí có đúng $gcd (n, j)$ chu trình, mỗi chu trình dài $n / gcd (n, j)$ . Do đó:

$số vòng cổ = \frac{1}{n} \sum_{j = 0}^{n - 1} m^{gcd (n, j)}$

Ví dụ chạy tay

Đếm vòng cổ $n = 4$ hạt, $m = 3$ màu, xét nhóm xoay $ℤ_{4} = {$ xoay 0, 1, 2, 3 vị trí $}$ .

Đánh số vị trí 0 1 2 3. Phép xoay $j$ đưa vị trí $i \to (i + j) mod 4$ . Ta phân rã từng phép thành chu trình và đếm $m^{c}$ :

 j=0 (đơn vị):   0->0  1->1  2->2  3->3
                 chu trình: (0)(1)(2)(3)        c = gcd(4,0)=4  -> 3^4 = 81
                 [mỗi vị trí tự do]

 j=1 (xoay 1):   0->1->2->3->0
                 chu trình: (0 1 2 3)           c = gcd(4,1)=1  -> 3^1 = 3
                 [cả 4 hạt phải cùng màu]

 j=2 (xoay 2):   0->2->0   1->3->1
                 chu trình: (0 2)(1 3)          c = gcd(4,2)=2  -> 3^2 = 9
                 [hạt đối nhau cùng màu]

 j=3 (xoay 3):   0->3->2->1->0
                 chu trình: (0 3 2 1)           c = gcd(4,3)=1  -> 3^1 = 3

Bảng tổng kết (ô đang cộng dồn đánh dấu <--):

Phép $j$	$gcd (4, j)$	số chu trình $c$	$m^{c} = 3^{c}$
0	4	4	81
1	1	1	3
2	2	2	9
3	1	1	3
		tổng	96

Áp dụng Burnside:

$| X / G | = \frac{1}{| G |} \sum_{g} | X^{g} | = \frac{81 + 3 + 9 + 3}{4} = \frac{96}{4} = 24 .$

Khớp với đáp án mẫu của bài cntnecklace (input 4 3 → 24). Lưu ý tổng $96$ luôn chia hết cho $| G | = 4$ trên số nguyên — đây là tính chất bắt buộc của Burnside, hữu ích để kiểm tra cài đặt khi chưa lấy modulo.

Cài đặt

Khung chung cho số học modulo (luỹ thừa nhanh + nghịch đảo qua định lý Fermat nhỏ, áp dụng khi $MOD$ nguyên tố):

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;

// Luỹ thừa nhanh: a^e mod MOD, O(log e)
long long power(long long a, long long e, long long mod) {
    a %= mod; if (a < 0) a += mod;          // chuẩn hoá cơ số về [0, mod)
    long long r = 1;
    while (e > 0) {
        if (e & 1) r = r * a % mod;
        a = a * a % mod;
        e >>= 1;
    }
    return r;
}

// Nghịch đảo modulo: a^(MOD-2) mod MOD, đúng khi MOD nguyên tố và gcd(a, MOD) = 1
long long inv(long long a, long long mod) { return power(a, mod - 2, mod); }

Đếm vòng cổ dưới nhóm xoay (bài cntnecklace), trực tiếp theo công thức $\frac{1}{n} \sum_{j} m^{gcd (n, j)}$ :

// Đếm số vòng cổ n hạt, m màu, phân biệt khi xoay. O(n log n).
long long count_necklace(long long n, long long m) {
    long long total = 0;
    for (long long j = 0; j < n; j++) {
        long long g = __gcd(n, j);          // chú ý: gcd(n, 0) = n, đúng cho phép đơn vị
        total = (total + power(m, g, MOD)) % MOD;
    }
    // chia cho n trong modulo = nhân nghịch đảo của n
    return total % MOD * inv(n % MOD, MOD) % MOD;
}

Tối ưu xuống $O (\sqrt{n} + d (n) \log n)$ bằng cách gom các $j$ theo giá trị $gcd$ . Số $j \in [0, n)$ có $gcd (n, j) = d$ (với $d ∣ n$ ) đúng bằng $φ (n / d)$ (Euler totient):

long long count_necklace_fast(long long n, long long m) {
    long long total = 0;
    for (long long d = 1; d * d <= n; d++) {
        if (n % d) continue;
        long long d2 = n / d;
        // ước d  -> có phi(n/d) phép xoay cho gcd = d
        total = (total + (long long)phi(n / d) % MOD * power(m, d, MOD)) % MOD;
        if (d != d2)                         // ước còn lại n/d, tránh đếm đôi khi d == n/d
            total = (total + (long long)phi(d) % MOD * power(m, d2, MOD)) % MOD;
    }
    return total % MOD * inv(n % MOD, MOD) % MOD;
}

Cấu hình tổng quát qua Polya — cycle index. Khi biết hoán vị vị trí của từng $g \in G$ , đếm số chu trình rồi cộng $m^{c (g)}$ :

// perms[g] = hoán vị vị trí của phép thứ g (perms[g][i] = ảnh của vị trí i)
long long polya_count(const vector<vector<int>>& perms, long long m) {
    int N = perms[0].size();
    long long total = 0;
    for (const auto& p : perms) {
        vector<char> seen(N, 0);
        long long cyc = 0;
        for (int i = 0; i < N; i++) if (!seen[i]) {     // đếm số chu trình
            cyc++;
            for (int j = i; !seen[j]; j = p[j]) seen[j] = 1;
        }
        total = (total + power(m, cyc, MOD)) % MOD;       // mỗi chu trình tự do 1 màu
    }
    return total % MOD * inv((long long)perms.size() % MOD, MOD) % MOD;
}

Độ phức tạp

Vòng cổ trực tiếp count_necklace: vòng lặp $n$ phép xoay, mỗi phép một power $O (\log m)$ và một __gcd $O (\log n)$ , tổng $O (n \log (n m))$ thời gian, $O (1)$ bộ nhớ. Đủ cho $n, m \leq 10^{6}$ .
Bản tối ưu count_necklace_fast: duyệt ước qua $O (\sqrt{n})$ , mỗi ước một power $O (\log m)$ và một phi. Nếu sàng/đặt totient sẵn thì gần $O (\sqrt{n} \cdot \log m)$ ; bộ nhớ $O (1)$ (hoặc $O (\sqrt{n})$ để phân tích thừa số cho $φ$ ).
Polya tổng quát polya_count: mỗi phép duyệt toàn bộ $N$ vị trí một lần để đếm chu trình ( $O (N)$ ) cộng một power. Với $| G |$ phép: $O (| G | (N + \log m))$ thời gian, $O (N)$ bộ nhớ cho mảng seen. Đây là nút thắt khi $| G |$ lớn (vd $| G | = n!$ thì không liệt kê nổi — phải dùng công thức đóng cho cycle index thay vì duyệt).

Lý do nhanh: thay vì $m^{N}$ cấu hình, ta chỉ chạy trên các phép biến đổi của nhóm; mỗi phép quy về một bài đếm chu trình rẻ tiền.

⚠️ Lỗi thường gặp

Tràn số khi nhân/luỹ thừa. $m^{gcd}$ rất lớn; phải lấy modulo sau mỗi phép nhân và dùng long long. Trong power, bỏ quên % mod ở bước a = a * a sẽ tràn long long ngay khi $a \approx 10^{9}$ .
Chia cho $| G |$ trực tiếp. Trong số học modulo không được viết total / n. Phải nhân nghịch đảo inv(n). Quên điều này cho kết quả sai hoàn toàn dù tổng đúng.
Nghịch đảo khi MOD không nguyên tố / không nguyên tố cùng nhau. inv qua Fermat chỉ đúng khi $MOD$ nguyên tố và $gcd (| G |, MOD) = 1$ . Nếu $| G |$ là bội của MOD (hiếm nhưng có thể với $n$ lớn) thì nghịch đảo không tồn tại — khi đó tổng (chưa modulo) vẫn chia hết cho $| G |$ trên $ℤ$ , nên hãy chia trước khi lấy modulo bằng số học lớn, hoặc dùng MOD khác.
$gcd (n, 0)$ cho phép đơn vị. Phép xoay $j = 0$ có $gcd (n, 0) = n$ (mọi vị trí là chu trình riêng → $m^{n}$ ). __gcd(n, 0) trả về $n$ là đúng; đừng "sửa" thành 1 — nhiều cài đặt cũ ép j==0 ? n : j là thừa và dễ gây nhầm.
Quên một loại phép trong nhóm. Với nhóm hai mặt (dihedral) $D_{n}$ phải cộng cả $n$ phép xoay và $n$ phép lật, rồi chia cho $2 n$ . Tô màu mặt khối lập phương phải đủ 24 phép quay (1 đơn vị + 6 + 3 + 8 + 6). Thiếu một lớp phép → đáp án sai.
Lật của đa giác chẵn vs lẻ khác nhau. Với $D_{n}$ : $n$ lẻ thì mỗi trục lật qua 1 đỉnh và 1 cạnh giữa, fix $m^{(n + 1) / 2}$ ; $n$ chẵn có hai loại trục (qua 2 đỉnh → $m^{n / 2 + 1}$ , qua 2 cạnh → $m^{n / 2}$ ). Dùng nhầm công thức cho parity sai là bẫy phổ biến.
Modulo âm. Sau các phép trừ (vd trong biến thể trọng số), kết quả có thể âm; luôn chuẩn hoá (x % MOD + MOD) % MOD.

Biến thể / Mở rộng

Nhóm hai mặt $D_{n}$ (vòng cổ có lật, bracelet): $| G | = 2 n$ gồm $n$ xoay + $n$ lật. Phần xoay như trên; phần lật phụ thuộc parity của $n$ như mục lỗi.
Tô màu vật thể 3D: nhóm quay khối lập phương $| G | = 24$ , khối tứ diện $| G | = 12$ ... mỗi lớp phép quay có số chu trình riêng trên mặt/đỉnh/cạnh.
Polya có trọng số: thay vì mỗi màu đếm như nhau, gán biến cho từng màu và thay $a_{i} \leftarrow \sum_{c} w_{c}^{i}$ vào cycle index $Z (G) = \frac{1}{| G |} \sum_{g} \prod_{i} a_{i}^{c_{i} (g)}$ để đếm số cấu hình có chính xác số lượng mỗi màu cho trước.
Đếm đồ thị/cây không nhãn: nhóm là $S_{n}$ tác động lên các cặp đỉnh; cycle index của tác động trên cạnh cho công thức đếm đồ thị không đẳng cấu.
Kiến thức nền hữu ích: nghịch đảo modulo, hàm Euler $φ$ — xem thêm trang Toán học.

Bài tập luyện

Đếm hoán vị phân biệt (cntperms) — (Amateur) làm quen số học modulo, giai thừa và nghịch đảo modulo — bộ công cụ bắt buộc trước khi chia cho $| G |$ trong Burnside.
Số vòng hoán vị (permrounds) — (Intermediate) phân rã hoán vị thành chu trình và lấy LCM độ dài; đúng cấu trúc chu trình quyết định số điểm bất động $m^{c (g)}$ trong Burnside/Polya.
Đếm cặp nguyên tố cùng nhau (cntcopair) — (Advanced) rèn kỹ thuật đếm theo $gcd$ và sàng/totient — chính là cơ chế gom $gcd (n, j)$ giúp tối ưu công thức vòng cổ.
Đếm vòng cổ (cntnecklace) — (Advanced) áp dụng trực tiếp Burnside: đếm vòng $n$ hạt $m$ màu phân biệt khi xoay, đúng công thức $\frac{1}{n} \sum_{j} m^{gcd (n, j)}$ với $n, m \leq 10^{6}$ .