[组合数学] 圆排列和欧拉函数为啥有关系：都是polya定理的锅

本文是一个笨比学习组合数学的学习笔记，因为是笨比，所以写的应该算是很通俗易懂了。

首先，我们考虑这么一个问题：你有无穷多的\(p\)种颜色的珠子，现在你想要的把他们中的\(n\)个以圆形的形状等间距的黏在一个可以旋转的圆盘上，求方案数。

然后，该问题的答案是 \(\frac{1}{n}\Sigma_{d|n}\phi(\frac{n}{d})p^d\) ,之中\(\phi()\)表示欧拉函数，下面解释一下为什么会出现这样一个数论函数。

首先，我们来复习一下polya定理：设一个序列上定义了一置换群\(|G|\)，则对该序列做\(p\)种颜色的染色，方案数为\(\frac{1}{|G|}\Sigma^{|G|}_{i=1}p^{c_i}\)，之中，\(|G|\)表示置换群大小（元素个数），\(c_i\)表示\(G\)中第\(i\)个置换的循环节数目。

那么在上述圆排列问题中，置换群也就是旋转变换的群了，注意这里不考虑翻转变换（这也是为什么题目里说要黏在可旋转的圆盘上的原因，这样就和翻转变换无关了）。那么显然，一个有\(n\)个珠子的圆环，一共对应了\(n\)种旋转变换，分别是从转\(1\)个单位到转\(n\)个单位（也就是不转，或者说转0个单位）的\(n\)种。因此，置换群大小\(|G|=n\)。

把\(|G|=n\)代入polya的公式里，得到\(ans=\frac{1}{n}\Sigma^{n}_{i=1}p^{c_i}\)，那么对比真正的答案，接下来要说明的就是，为什么\(\Sigma^{n}_{i=1}p^{c_i}=\Sigma_{d|n}\phi(\frac{n}{d})p^d\)。

答案其实简单的有些弱智：合并同类项

\(\Sigma^{n}_{i=1}p^{c_i}\)这一式子里，其实有\(n\)项，那么很自然的一个想法就是：\(p^{c_i}\)是不是有不少重复的呢？事实上，是的，甚至只有\(\sqrt{n}\)种不同的\(p^{c_i}\)。

下面随便假设有个指数\(d\)，那我想知道\(\Sigma^{n}_{i=1}p^{c_i}\)，有几个\(p^d\)出现，也就是有几个\(c_i=d\)。回忆一下，这里\(c_i\)指的是第\(i\)个置换循环节的数量，这个要怎么求呢？这里需要一个简单但nb的小知识：

定理：对于\(n\)个珠子组成的圆的旋转变换来说，旋转了\(x\)个单位的变换对应的循环节数量有\(gcd(n,x)\)个，特别的，\(x=0\)时的循环节数量有\(n\)个。

不是证明的证明：考虑一个青蛙跳石头的问题，也就是有\(n\)块石头圆形排列，编号从\(0~n-1\)，青蛙初始在\(pos\)的位置，每次青蛙会跳x步，那么青蛙跳一步就相当于\(pos=(pos+x)%k\)，现在，请问青蛙一直跳下去，能踩到多少块石头。例如，\(n=6,x=4,pos=2\)时，青蛙就只能跳到编号为\(0,2,4\)的三块儿石头上。该问题的答案是\(\frac{n}{gcd(n,x)}\)，这个证明略了，这是个比较好理解但不太好表述的数论结论。

那么，如果我们把旋转\(x\)个单位的置换群理解成每步跳\(x\)格的青蛙的话，就有循环节长度 = 青蛙能跳到的石头个数 = \(\frac{n}{gcd(n,x)}\) 。又因为从青蛙的例子里可以看出，该长度和青蛙初始的\(pos\)无关，所以所有的循环节长度都是\(\frac{n}{gcd(n,x)}\)。

进而，由于 n=循环节长度*循环节数量，就可以解得循环节数量为\(gcd(n,x)\)，这就是旋转\(x\)对应置换的循环节数量。

书归正传，我们现在想知道的是，给定一个整数\(d\)，有几个\(p^d\)出现在\(\Sigma^{n}_{i=1}p^{c_i}\)中，或者说多少个\(c_i=d\)。\(c_i\)的含义是循环节数量，也就是对于\(x\in [1,n]\)，有多少个\(x\)对应的循环节数量是\(d\)。废话不多说，按刚才的结论，这也就是问有多少个\(x\)满足\(gcd(n,x)=d\)。

有多少个\(x\)满足\(gcd(n,x)=d\)：这又是个数论问题，首先，变换成\(gcd(\frac{n}{d},\frac{x}{d})=1\)，这个变换是科学的，因为\(gcd(n,x)=d\)中\(n\)和\(x\)一定是\(d\)的倍数。那么，有多少个\(x\)满足\(gcd(\frac{n}{d},\frac{x}{d})=1\)呢？由于满足\(gcd(\frac{n}{d},狗)=1\)的狗有\(\phi(n/d)\)个（根据欧拉函数的定义），而狗和\(x\)显然是一一对应的，所以这样的\(x\)就也有\(\phi(n/d)\)个。

所以，\(ans=\frac{1}{n}\Sigma^{n}_{i=1}p^{c_i}=\frac{1}{n}\Sigma_{d|n}\phi(\frac{n}{d})p^d\)，这里\(d|n\)是因为根据上面推导，循环节数量\(d\)显然一定是\(n\)的因子。

巴特西

[组合数学] 圆排列和欧拉函数为啥有关系：都是polya定理的锅

最新文章

热门文章