免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[组合] 两个車的立方体棋盘(旋转翻转等价)

一个\(\,n\times\,n\times\,n\,\)正方体棋盘放两个車,要求两个車既不同行也不同列还不同纵。
算出在“旋转翻转等价”下的种类数。
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

回顾 Brunside 引理:

Step 1: 将问题转化为群作用问题. 就项链计数而言, 记 $\Omega$ 为所有对象 (不考虑旋转翻转下等价, 例如两黑珠一白珠可组成 $3$ 条项链).

Step 2: 考虑旋转翻转作用, 即二面体群 $D_{n}$ 在 $\Omega$ 上的作用. $x\in \Omega$ 在旋转翻转下能生成的所有对象为轨道 $Gx:=\{gx:g\in\Omega\}$. 两黑珠一白珠的项链在正三角形变换群下可生成三个不同的对象, 即生成大小为 $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)$.
无钱佮歹看、无样佮歹生、无汉草佮无文采、无学历佮无能力、无高度无速度无力度共闲无代记。(闽南话)
口号:珍爱生命,远离内卷。

TOP

回复 1# 青青子衿

翻转的定义是什么? 我只讨论日常生活中能实现的同构, 借用化学术语表达之, 即左手分子不同构于右手分子.
无钱佮歹看、无样佮歹生、无汉草佮无文采、无学历佮无能力、无高度无速度无力度共闲无代记。(闽南话)
口号:珍爱生命,远离内卷。

TOP

返回列表 回复 发帖