某岛

… : "…アッカリ～ン . .. . " .. .

August 18, 1453

【专题】Polya 计数定理

References:

Polya 定理再小结
 组合数学原书第 5 版
 除数函数的渐近上界？ by vfleaking

。。统计在某个置换群作用下。。计算不等价的着色方案数的问题。。。
。。可以通过 Burnside 定理。。转化为枚举每一个置换。。。统计在该置换作用下等价的着色方案数的问题。。
。。而 Polya 定理则是巧妙的利用同一循环内着色必须相同这个事实，进一步简化后者的计算。。。

——————

习题：
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=2823#overview

Burnside 定理

设 G 是 X 的置换群，而 C 是 X 中对 G 封闭的着色集合。
则 C 中非等价着色数 N(G, C) 由下式给出：

$|G| N(G, C) = \sum_{f\in g}|C(f)|$

Polya 定理

设 $f$ 是集合 $X$ 的置换。假如我们用 $k$ 种颜色对 $X$ 着色，则对 $f$ 不变的着色数与 $f$ 的循环数 $r$ 有关：

$|C(f)| = k^r$

。。。

——————

证明

引理 1：

对于每一种着色 c，c 的稳定核 G(c) 是置换群，而且对 G 中的任意置换 f 与 g。
gc = fc 当且仅当 $f^{-1} * g$ 属于 G(c)。

推论 2

设 c 为 C 中的一种着色，那么与 c 等价的着色数等于 G 中置换个数，除以 c 的稳定核中置换的个数。

$N(c) = |{f*c: f\in G}| = \frac{|G|}{|G(c)|}$

。

Burnside 定理

。。考察。。所有满足 f*c = c 的二元组 (f, c)。。双计数。。
枚举 f 。。得到 $\sum_{f\in g}|C(f)|$ 。。（通过置换 f 不变的着色几何）
枚举 c 。。得到 $\sum_{c\in C}|G(c)|$ 。。（c 关于置换群 G 的稳定核）
根据推论 2 有：

$|G(c)| N(c) = |G|$

$\sum_{c\in C} \frac{1}{N(c)} = N(G,C)$

（因为每个非等价着色对左式的贡献为 1。）

例题

HOJ 2084. The Colored Cubes

HOJ 2084. The Colored Cubes

inline LL f(DB x){
    return (pow(x, 6) + 3 * pow(x, 4) + 12 * pow(x, 3) + 8 * pow(x, 2)) / 24;
}

int main() {
    int n; while (cin >> n && n){
        cout << f(n) << endl;
    }
}

HOJ 2647. Megaminx

HOJ 2647. Megaminx

inline LL f(DB x){
    return (pow(x, 12) + 15 * pow(x, 6) + 44 * pow(x, 4)) / 60;
}

int main() {
    int n; while (cin >> n){
        cout << f(n) << endl;
    }
}

SGU 294. He’s Circles

SGU 294. He’s Circles

#include <lastweapon/bignum>
using namespace lastweapon;

const int PMAX = int(2e5) + 9;
VI P; bitset<PMAX> isP; int phi[PMAX];
void sieve(){
    phi[1] = 1; FOR(i, 2, PMAX){
        if (!isP[i]) P.PB(i), phi[i] = i-1;
        for (int j=0;j<SZ(P)&&i*P[j]<PMAX;++j){
            isP[i*P[j]]=1; if (!(i%P[j])){
                phi[i*P[j]] = phi[i] * P[j];
                break;
            } else{
                phi[i*P[j]] = phi[i] * (P[j] - 1);
            }
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
#endif

    sieve();

    int n; RD(n);
    bignum z;
    //REP_1(i, n) z += pow(bignum(2), __gcd(i, n));
    REP_1(d, n) if (n % d == 0) {
        z += pow(bignum(2), d) * phi[n/d];
    }
    z /= n;
    cout << z << endl;
}