置换
设 M 是一个非空的有限集合,M 的一个一对一变换称为一个置换。
设 M 的元素为 a_1, a_2, \cdots, a_n,则 M 的置换 \sigma 可以简记为
\begin{array}{cccc}
a_1 & a_2 & \cdots & a_n\\
b_1 & b_2 & \cdots & b_n
\end{array}
\right)
其中 b_i = \sigma(a_i)。如果
\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)
则简记 \sigma = (a_1 a_2 \cdots a_n)。
若 \sigma 和 \tau 是两个不相杂的轮换,则其乘法适合交换律,即 \sigma\tau = \tau\sigma。可以证明,任意置换 \sigma 恰有一法写成不相交轮换的乘积。
可以分解为奇数个对换之积的置换称为奇置换,可以分解为偶数个对换之积的置换称为偶置换。
Burnside 引理
设 G 是 n 元集 S = \lbrace 1, 2, \cdots, n \rbrace 上的置换群 G = \lbrace \sigma_1, \sigma_2, \cdots, \sigma_n \rbrace,把每个 \sigma_i 都表示成不相杂的轮换的乘积,令 \lambda_k(\sigma_i) 表示置换 \sigma_i 中 k 阶轮换的个数,则 G 在 S 上诱导出的等价关系将 S 划分为不同等价类的个数为
其中 \lambda_1(\sigma) 为置换 \sigma 中的不动点(即1阶轮换)的个数。
Polya 定理
设 H 是 n 个对象上的一个置换群,用 m 种颜色给这 n 个对象涂色,一个对象涂任意种颜色,则在置换群 H 的作用下不等价的方案数为
其中 \lambda(\tau) 表示置换 \tau 表示为不相杂轮换乘积的形式中轮换的个数。
例如,对于置换群H’ = \lbrace (1)(2)(3), (1 2 3), (1 3 2), (1)(2 3), (2)(1 3), (3)(1 2) \rbrace,不等价的方案数为L’ = \frac{1}{6} \left[3^3 + 2 \times 3^1 + 3 \times 3^2 \right]。记颜色为 \lbrace r, g, b \rbrace,则其生成函数为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],其中 r^xg^yb^z 前的系数表示将对应颜色染对应个数时的方案数。
组合数学知识计算。
常见模型举例
圆环的旋转与反射
例题:POJ 2409 / POJ 1286
在轴对称的作用下。奇数阶环的对称轴一定通过其中的一个珠子,那么会形成 (1)(2, n)(3, n-1)\cdots 这样的置换,总共 n 个,不相杂轮换 \frac{n+1}{2} 个。偶数阶环的对称轴可能经过珠子,也可能不经过珠子,那么会形成 (1,n)(2,n-1)(3,n-2)\cdots 型置换 \frac{n}{2} 个、(1)(2,n)(3,n-1)\cdots(\frac{n}{2}+1) 型置换 \frac{n}{2} 个。
在中心对称的作用下,考虑珠子旋转 k\in[0,n-1] 个单位时的情况,不相杂轮换有 gcd(k,n) 个。对于同一个 k,又可以由欧拉函数求出相似者,于是枚举 n 所有的因子即可,对于每个因子 d 都有 \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\times N 的正方形,有1个 n^2 的恒等置换,有1个 \lceil \frac{n^2}{2} \rceil 的 180° 旋转,有2个 \lceil \frac{n^2}{4} \rceil 的 90° 旋转,有2个 \lceil \frac{n}{2} \rceil n 的纵向横向反射,有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 的某项系数