Polya置换
Oct 1, 2018 由 小羊
置换
设 M 是一个非空的有限集合,M 的一个一对一变换称为一个置换。
设 M 的元素为 a1,a2,⋯,an,则 M 的置换 σ 可以简记为
σ=(a1b1a2b2⋯⋯anbn)
其中 bi=σ(ai)。如果
σ=(a1a2a2a3⋯⋯an−1anana1)
则简记 σ=(a1a2⋯an)。
若 σ 和 τ 是两个不相杂的轮换,则其乘法适合交换律,即 στ=τσ。可以证明,任意置换 σ 恰有一法写成不相交轮换的乘积。
可以分解为奇数个对换之积的置换称为奇置换,可以分解为偶数个对换之积的置换称为偶置换。
Burnside 引理
设 G 是 n 元集 S={1,2,⋯,n} 上的置换群 G={σ1,σ2,⋯,σn},把每个 σi 都表示成不相杂的轮换的乘积,令 λk(σi) 表示置换 σi 中 k 阶轮换的个数,则 G 在 S 上诱导出的等价关系将 S 划分为不同等价类的个数为
L=∣G∣1j=1∑rλ1(σj)
其中 λ1(σ) 为置换 σ 中的不动点(即1阶轮换)的个数。
Polya 定理
设 H 是 n 个对象上的一个置换群,用 m 种颜色给这 n 个对象涂色,一个对象涂任意种颜色,则在置换群 H 的作用下不等价的方案数为
L=∣H∣1τ∈H∑mλ(τ)
其中 λ(τ) 表示置换 τ 表示为不相杂轮换乘积的形式中轮换的个数。
例如,对于置换群H′={(1)(2)(3),(123),(132),(1)(23),(2)(13),(3)(12)},不等价的方案数为L′=61[33+2×31+3×32]。记颜色为 {r,g,b},则其生成函数为L(r,g,b)=61[(r+g+b)3+2×(r3+b3+g3)+3×(r+g+b)(r2+b2+g2)],其中 rxgybz 前的系数表示将对应颜色染对应个数时的方案数。
组合数学知识计算。
常见模型举例
圆环的旋转与反射
例题:POJ 2409 / POJ 1286
在轴对称的作用下。奇数阶环的对称轴一定通过其中的一个珠子,那么会形成 (1)(2,n)(3,n−1)⋯ 这样的置换,总共 n 个,不相杂轮换 2n+1 个。偶数阶环的对称轴可能经过珠子,也可能不经过珠子,那么会形成 (1,n)(2,n−1)(3,n−2)⋯ 型置换 2n 个、(1)(2,n)(3,n−1)⋯(2n+1) 型置换 2n 个。
在中心对称的作用下,考虑珠子旋转 k∈[0,n−1] 个单位时的情况,不相杂轮换有 gcd(k,n) 个。对于同一个 k,又可以由欧拉函数求出相似者,于是枚举 n 所有的因子即可,对于每个因子 d 都有 φ(dn) 个共轭的置换。
while (!factors.empty()) {
int d = factors.back();
sum += phi[n/d] * fpow(c, d);
factors.pop_back();
}
if (n & 1) {
sum += n * fpow(c, (n+1)>>1);
} else {
sum += (n>>1) * fpow(c, n>>1);
sum += (n>>1) * fpow(c, 1+(n>>1));
}
sum /= n*2;
正方形的旋转与反射
例题:HDU 1812
对于 N×N 的正方形,有1个 n2 的恒等置换,有1个 ⌈2n2⌉ 的 180° 旋转,有2个 ⌈4n2⌉ 的 90° 旋转,有2个 ⌈2n⌉n 的纵向横向反射,有2个 2n(n+1) 的斜反射。
BigInteger sum = BigInteger.valueOf(0);
sum = sum.add(colors.pow(n*n));
sum = sum.add(colors.pow((n*n+1)/2));
sum = sum.add(colors.pow((n*n+3)/4).shiftLeft(1));
sum = sum.add(colors.pow((n+1)/2*n).shiftLeft(1));
sum = sum.add(colors.pow(n*(n+1)/2).shiftLeft(1));
System.out.println(sum.shiftRight(3));
正方体的旋转
1x静止、4x2x体对角线、6x对棱中心连线、3x3x对立面中心连线
lld solve2(int i = 0, int s = 6) {
if (i >= 6) return 1;
if (cnt[i] % 2) return 0;
return C[s][cnt[i]/2] * solve2(i+1, s-(cnt[i]/2));
}