【浅谈系列】Necklace problem

2 minute read

Published:

代数基础的第一节课上,老师讲了经典的项链问题,简单总结一下。

代数基础的第一节课上,老师讲了经典的项链问题,简单总结一下。由于这个问题非常经典,网络上有很多相关资料,已经给出了证明和推导,因此本文只是简单总结,给出参考链接与我自己的看法,以及相关题目,具体推导证明不再赘述。

关于本文涉及的两个定理,仅给出证明和我自己的看法,至于当时相关学者如何想到这种方法,如何探索得出这个结论的历史,可以自己查找相关资料。最近时间有限,我也没去了解。

0. 参考资料

1. 问题与简单分析

学习近世代数时,第一节课老师们往往会讲一些近世代数起源相关的知识。对于图形对称性的研究,与群论有着莫大的联系。比如说晶体,晶体的对称性对晶体的种类有很强的约束,而对于晶体的研究自然涉及到群论的知识。从十九世纪后半叶起,科学家们在研究中逐渐发现了晶体外形的全部对称形式,也就是使单位格点保持不动的对称群,并且相关科学家于 1914 年和 1915 年获得了诺奖。此外,课上老师讲的项链问题,也是非常经典的一个例子。

问题描述如下:

如果一条项链由 $n$ 个宝石串成,且宝石除了颜色以外不存在任何区别,每种颜色的宝石数量均为无穷,总共有 $m$ 种颜色,问能串出多少种不同的项链。

我们可以简单分析。简单来想,$n$ 个位置,每个位置 $m$ 种选择,总共 $m^n$ 种。但这并不是一条直线排列,项链是一个圈,因此这里面肯定存在着重复,问题就是怎么来定义这些重复,以及如何把重复的个数从总数中去除。

仔细想想,怎样项链会产生重复?直观上来看,让项链旋转 rotation 或者翻转 flip 是产生重复的唯二途径。因此,我们所要做的下一步就是如何用数学语言描述它。

2. 变换群、置换群、对称群与二面体群

那么如何用数学语言描述我们的分析呢?首先来了解几个概念。

  • 变换群 $\text{A}$ 是非空集合,$f:\text{A} \longleftarrow \text{A}$ 称为 $\text{A}$ 上的一个变换。集合 $A$ 上的一一变换关于变换乘法构成的群称为变换群。

  • 置换群 一个置换群 $G$,其元素是一个有限集合 $S$ 上的置换。

  • 对称群 有限集合 $S$ 上的所有置换一定构成群,称为对称群,记为 $S_n$,其中 $n$ 是 $S$ 的阶数。 置换群是变换群的特例,对称群是置换群的特例。

  • 二面体群 dihedral group 二面体群 $D_{2n}$ 是正 $n$ 边形的对称群,有 $2n$ 个元素,有的地方也记作 $D_{n}$。二面体群属于对称群的一种。

显然,我们可以将项链视作一个正 $n$ 边形,那么对于一条项链,所要做的一是着色,一是置换。

项链的置换群去除重复的,可以变为项链的二面体群,其中元素就表示了所有的对称变换,包括旋转变换和反射变换。

着色可以看做是对一个排列的运算,它使得排列中每一个元素具有一个颜色。项链的着色集则是所有着色的集合。

那我们要研究的问题,就是在既要着色,又要考虑置换的情况下,求出不重复的着色方案个数。

而在历史上这个问题被一个引理和一个定理所解答,一个是 Burnside Lemma,一个是 Pólya Theorem

3. Burnside 引理

Burnside 定理表述如下:

Let $G$ be a finite group acting on a set $X$.

Let $X / G$ be the set of orbits under this action.

For $x \in X$, let $\text{Stab}(x)$ be the stabilizer of $x$ by $G$.

For $g \in G$, let $X^g$ denotes the set of all elements in $X$ which is fixed by $g$, that is:

\[X^g := \{x \in X: g x = x \}\]

Then:

\[\mid X / G \mid = \frac 1 {\mid G \mid} \sum_{g \mathop \in G} \mid X^g \mid\]

In words, the number of orbits equals the average number of fixed elements.

证明详见 Burnside’s Lemma - ProofWiki,需要先证一个 Orbit-Stabilizer Theorem

Burnside Lemma 的公式中我们可以看出,它是对着色集作用上置换,也就是对每一个置换关于着色集的不动点数进行求和,手算的话是需要先列出着色集,也就是所有的着色,然后对其尝试每一种置换,看整个着色集能被划分为多少个等价类。

Burnside Lemma 的一个计算示例可以参考 对Burnside引理与Polya定理的理解 - Bill Yang’s Blog

4. Pólya 定理

Pólya 定理表述如下:

Let $G$ be a group and $X,Y$ be finite sets, where $\mid X \mid = n$.

Then for any group action $\phi$ of $G$ on $X$, the number of distinct configurations in $Y^X$ is

\[\mid C \mid = \frac{1}{\mid G \mid} \sum_{g \in G} {\mid Y \mid}^{c(g)}\]

where $c(g)$ denotes the number of cycles in the cycle decomposition of $p_g \in Sym(X)$, the permutation of $X$ associated with the action of $g$ on $X$.

证明即为将我们之前对着色的分析代入 Burnside Lemma,显而易见。

Pólya Theorem 的公式中我们可以看出它和 Burnside Lemma 的区别。它是先对原来的位置集合做置换,再对置换尝试着色。根据它的推导可知,当写成轮换乘积形式时,每一个轮换里必然是染同一种颜色。

因此在不同轮换间颜色选择不互相影响时,它相当于求出二面体群的所有元素,然后写出轮换乘积形式,拆分出的不相交轮换的个数作为幂,底数为颜色的个数,因为一个轮换必然染同种颜色,从这个角度来说表达式很好理解。

Pólya Theorem 的一个计算示例可以参考 对Burnside引理与Polya定理的理解 - Bill Yang’s Blog

Pólya Theorem 的方法比 Burnside Lemma 好在哪里呢?因为现实中,往往着色集较大,先算着色集需要花费很多时间,而且不动点也比较难以计算,相比之下比如说二面体群就比较好算,这就是 Pólya Theorem 的优势所在。

5. 相关题目

一个相关题目是 PE 281

题目如下:

显然这和上面说的项链问题是一类问题,用两个定理任意一个即可推导求解。

推导可得:

\[f(m, n) = \frac{1}{mn} \sum_{d|n} \frac{(dm)!}{(d!)^m} \varphi(n/d).\]

显然,当函数中一个自变量固定时,函数随另一个自变量单调递增。因此简单试一下前几个即可。

SageMath 9.2 代码如下:

def function_f(m, n):
    cnt = 0
    for d in divisors(n):
        cnt += euler_phi(n//d)*factorial(d*m)//(factorial(d))^m
    cnt /= m*n
    return cnt


upper = 10^15
result = 0
m = 2

while function_f(m, 1) <= upper:
    n = 1
    while function_f(m, n) <= upper:
        result += function_f(m, n)
        n += 1
    m += 1

print (result)

结果如下:

1485776387445623

6. 更多

由于本人才疏学浅,对组合数学知之甚少,虽然在项链问题的相关链接看到不少有意思的东西,但无奈没时间也没能力去深入学习,因此列在这里,感兴趣可自行阅读。


声明:本文采用 CC BY-NC-SA 4.0 授权。

This work is licensed under a CC BY-NC-SA 4.0.