🌑

小羊儿的心情天空

Polya置换

Oct 1, 2018 由 小羊

置换

MM 是一个非空的有限集合,MM 的一个一对一变换称为一个置换。

MM 的元素为 a1,a2,,ana_1, a_2, \cdots, a_n,则 MM 的置换 σ\sigma 可以简记为

σ=(a1a2anb1b2bn)\sigma = \left( \begin{array}{cccc} a_1 & a_2 & \cdots & a_n\\ b_1 & b_2 & \cdots & b_n \end{array} \right)

其中 bi=σ(ai)b_i = \sigma(a_i)。如果

σ=(a1a2an1ana2a3ana1)\sigma = \left( \begin{array}{cccc} a_1 & a_2 & \cdots & a_{n-1} & a_n\\ a_2 & a_3 & \cdots & a_n & a_1 \end{array} \right)

则简记 σ=(a1a2an)\sigma = (a_1 a_2 \cdots a_n)

σ\sigmaτ\tau 是两个不相杂的轮换,则其乘法适合交换律,即 στ=τσ\sigma\tau = \tau\sigma。可以证明,任意置换 σ\sigma 恰有一法写成不相交轮换的乘积。

可以分解为奇数个对换之积的置换称为奇置换,可以分解为偶数个对换之积的置换称为偶置换。

Burnside 引理

GGnn 元集 S={1,2,,n}S = \lbrace 1, 2, \cdots, n \rbrace 上的置换群 G={σ1,σ2,,σn}G = \lbrace \sigma_1, \sigma_2, \cdots, \sigma_n \rbrace,把每个 σi\sigma_i 都表示成不相杂的轮换的乘积,令 λk(σi)\lambda_k(\sigma_i) 表示置换 σi\sigma_ikk 阶轮换的个数,则 GGSS 上诱导出的等价关系将 SS 划分为不同等价类的个数为

L=1Gj=1rλ1(σj)L = \frac{1}{|G|} \sum_{j=1}^r \lambda_1(\sigma_j)

其中 λ1(σ)\lambda_1(\sigma) 为置换 σ\sigma 中的不动点(即1阶轮换)的个数。

Polya 定理

HHnn 个对象上的一个置换群,用 mm 种颜色给这 nn 个对象涂色,一个对象涂任意种颜色,则在置换群 HH 的作用下不等价的方案数为

L=1HτHmλ(τ)L = \frac{1}{|H|} \sum_{\tau \in H} m^{\lambda(\tau)}

其中 λ(τ)\lambda(\tau) 表示置换 τ\tau 表示为不相杂轮换乘积的形式中轮换的个数。

例如,对于置换群H={(1)(2)(3),(123),(132),(1)(23),(2)(13),(3)(12)}H' = \lbrace (1)(2)(3), (1 2 3), (1 3 2), (1)(2 3), (2)(1 3), (3)(1 2) \rbrace,不等价的方案数为L=16[33+2×31+3×32]L' = \frac{1}{6} \left[3^3 + 2 \times 3^1 + 3 \times 3^2 \right]。记颜色为 {r,g,b}\lbrace r, g, b \rbrace,则其生成函数为L(r,g,b)=16[(r+g+b)3+2×(r3+b3+g3)+3×(r+g+b)(r2+b2+g2)]L(r,g,b) = \frac{1}{6} \left[(r+g+b)^3 + 2 \times (r^3+b^3+g^3) + 3 \times (r+g+b)(r^2+b^2+g^2) \right],其中 rxgybzr^xg^yb^z 前的系数表示将对应颜色染对应个数时的方案数。

组合数学知识计算。

常见模型举例

圆环的旋转与反射

例题:POJ 2409 / POJ 1286

在轴对称的作用下。奇数阶环的对称轴一定通过其中的一个珠子,那么会形成 (1)(2,n)(3,n1)(1)(2, n)(3, n-1)\cdots 这样的置换,总共 nn 个,不相杂轮换 n+12\frac{n+1}{2} 个。偶数阶环的对称轴可能经过珠子,也可能不经过珠子,那么会形成 (1,n)(2,n1)(3,n2)(1,n)(2,n-1)(3,n-2)\cdots 型置换 n2\frac{n}{2} 个、(1)(2,n)(3,n1)(n2+1)(1)(2,n)(3,n-1)\cdots(\frac{n}{2}+1) 型置换 n2\frac{n}{2} 个。

在中心对称的作用下,考虑珠子旋转 k[0,n1]k\in[0,n-1] 个单位时的情况,不相杂轮换有 gcd(k,n)gcd(k,n) 个。对于同一个 kk,又可以由欧拉函数求出相似者,于是枚举 nn 所有的因子即可,对于每个因子 dd 都有 φ(nd)\varphi(\frac{n}{d}) 个共轭的置换。

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×NN\times N 的正方形,有1个 n2n^2 的恒等置换,有1个 n22\lceil \frac{n^2}{2} \rceil 的 180° 旋转,有2个 n24\lceil \frac{n^2}{4} \rceil 的 90° 旋转,有2个 n2n\lceil \frac{n}{2} \rceil n 的纵向横向反射,有2个 n(n+1)2\frac{n(n+1)}{2} 的斜反射。

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));
} // 提取 (a2+b2+c2+d2+e2+f2)^6 的某项系数