|
|
本帖最后由 Czhang271828 于 2023-5-6 12:17 编辑 回顾 Brunside 引理:
Step 1: 将问题转化为群作用问题. 就项链计数而言, 记 $\Omega$ 为所有对象 (不考虑旋转翻转下等价, 例如两黑珠一白珠可组成 $3$ 条项链).
Step 2: 考虑旋转翻转作用, 即二面体群 $D_{n}$ 在 $\Omega$ 上的作用. $x\in \Omega$ 在旋转翻转下能生成的所有对象为轨道 $Gx:=\{gx:g\in G\}$. 两黑珠一白珠的项链在正三角形变换群下可生成三个不同的对象, 即生成大小为 $3$ 的轨道.
Step 3: 记 $\Gamma:=\{(g,x):gx=x\}$ 为不动点数量. Brunside 引理给出
$$
\sum_{g\in G}|\{x:gx=x\}|=|\Gamma|=|G|\cdot\text{所有轨道数量}.
$$
待求值即"考虑旋转翻转变换下等价的项链种数", 亦即轨道数量.
Step 4: 因此轨道数为
$$
\dfrac{1}{|G|}\sum_{g\in G}|\{x:gx=x\}|.
$$
该类计数方法的难点就是计算群中所有元素的不动点数量.
Brunside 引理继续吧
两个车的位置 $\Omega$ (不考虑旋转下等同) 共 $\dfrac{n^3(n-1)^3}{2}$ 个元素.
可以看出立方体旋转群有 $24$ 个元素: 一处顶点可变化为 $8$ 个顶点的任意一个, 同时有三种 $120^\circ$ 旋转. 其实我们可以根据直觉写出旋转群中的元素:
1. ($e$) 单位元, 即不动.
2. ($a_1\sim a_6$) 保持两个面不位移, 围绕穿越相对正方形之中心之轴线旋转 $\pi/2$.
3. ($b_1\sim b_3$) 保持两个面不位移, 围绕穿越相对正方形之中心之轴线旋转 $\pi$.
4. $(c_1\sim c_8)$ 保持顶点不动, 围绕体对角线转 $2\pi/3$.
5. $(d_1\sim d_6)$ 保持对棱不位移, 围绕对棱中点所在轴线旋转 $\pi$.
然后计算群作用下的不动点.
$n$ 为奇数时:
1. $e$ 下不动点数量为 $\dfrac{n^3(n-1)^3}{2}$.
2. 每个 $a_i$ 下不动点均为 $0$.
3. 每个 $b_i$ 下不动点均为 $n(n-1)$.
4. 每个 $c_i$ 下不动点均为 $\dfrac{n(n-1)}{2}$, 即旋转轴上的元素.
5. 每个 $d_i$ 下不动点均为 $\dfrac{n^3-n^2}{2}+\dfrac{n-1}{2}$. 实际上, 考察旋转轴所在的长宽比为 $1:\sqrt 2$ 的矩形, (立方体中) 矩形外有 $\dfrac{n^3-n^2}{2}$ 对点可取; 矩形上仅有旋转轴上的 $\dfrac{n-1}{2}$ 对点可取.
从而轨道数为
$$
\dfrac{1}{24}[\dfrac{n^3(n-1)^3}{2}+3n(n-1)+8\cdot \dfrac{n(n-1)}{2}+6\cdot (\dfrac{n^3-n^2}{2}+\dfrac{n-1}{2})]
$$
化简之, 为 $\dfrac{n-1}{48}\cdot(n^3(n-1)^2+6n^2+14n+6)$.
$n$ 为偶数时:
1. $e$ 下不动点数量为 $\dfrac{n^3(n-1)^3}{2}$.
2. 每个 $a_i$ 下不动点均为 $0$.
3. 每个 $b_i$ 下不动点均为 $n^2$.
4. 每个 $c_i$ 下不动点均为 $\dfrac{n(n-1)}{2}$, 即旋转轴上的元素.
5. 每个 $d_i$ 下不动点均为 $\dfrac{n^3-n^2}{2}+\dfrac{n}{2}$. 实际上, 考察旋转轴所在的长宽比为 $1:\sqrt 2$ 的矩形, (立方体中) 矩形外有 $\dfrac{n^3-n^2}{2}$ 对点可取; 矩形上仅有旋转轴上的 $\dfrac{n}{2}$ 对点可取.
从而轨道数为
$$
\dfrac{1}{24}[\dfrac{n^3(n-1)^3}{2}+3n^2+8\cdot \dfrac{n(n-1)}{2}+6\cdot (\dfrac{n^3-n^2}{2}+\dfrac{n}{2})]
$$
化简之, 为 $\dfrac{1}{48}\cdot(n^3(n-1)^3+6n^3+8n^2-2n)$. |
|
Czhang271828
发表于 2022-2-21 15:45
