发布于

Polya置换

置换

设 M 是一个非空的有限集合，M 的一个一对一变换称为一个置换。

设 M 的元素为 a_1, a_2, \cdots, a_n，则 M 的置换 \sigma 可以简记为

\sigma = \left(
\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)。如果

\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)

则简记 \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 划分为不同等价类的个数为

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

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

Polya 定理

设 H 是 n 个对象上的一个置换群，用 m 种颜色给这 n 个对象涂色，一个对象涂任意种颜色，则在置换群 H 的作用下不等价的方案数为

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

其中 \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 的某项系数