悠闲数学娱乐论坛(第2版)'s Archiver

青青子衿 发表于 2019-4-17 18:57

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

一个\(\,n\times\,n\times\,n\,\)正方体棋盘放两个車,要求两个車既不同行也不同列还不同纵。
算出在“旋转翻转等价”下的种类数。

Czhang271828 发表于 2022-2-21 15:45

回顾 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\}|.
$$
该类计数方法的难点就是计算群中所有元素的不动点数量.

{:smile:} {:smile:} {:smile:} {:smile:} {:smile:} {:smile:} {:smile:} {:smile:} {:smile:} {:smile:} {:smile:} {:smile:} {:smile:} {:smile:} {:smile:} {:smile:} {:smile:} {:smile:} {:smile:} {:smile:}

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:47

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30874&ptid=6025]1#[/url] [i]青青子衿[/i] [/b]

翻转的定义是什么? 我只讨论日常生活中能实现的同构, 借用化学术语表达之, 即左手分子不同构于右手分子.

页: [1]

Powered by Discuz! Archiver 7.2  © 2001-2009 Comsenz Inc.