置换及其应用

今天上数学课时比较清闲(主要是感觉逻辑用语没什么好学的),于是缓缓打开了大白书…
本来想看矩阵的…发现前面的内容就只有置换没看了,一时兴起就把置换解决掉…
感觉置换简直是优美极了!!!我在数学课上差点儿没笑出来= =
不知为何,置换是如此有趣,简直像玩游戏一样。

定义

简单来说,置换是一个在正整数[1,n]到正整数[1,n]上的一一映射,将1,2,3…n变为a1,a2,a3…an,记为
$$
\begin{pmatrix}
1 & 2 & 3 & … & n \\
a1 & a2 & a3 & … & an \\
\end{pmatrix}
$$
也可用函数表示,记为$f=\{a1,a2,a3…an\}$
为了表示方便,常常将一个置换表示成几个循环乘积的形式。循环即为几个元素交替,例如(1,3,2)表示1→3,3→2,2→1.下面是一个用循环分解置换的例子。
$$
\begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\
3 & 5 & 1 & 4 & 2 \\
\end{pmatrix}
=(1\ 3)(2\ 5)(4)
$$
应该很好理解。显而易见,循环的计算满足交换律。
我们称循环的个数为循环节,如上图置换的循环节为3.

计算

置换间可定义乘法,如f={1,3,2},g={2,1,3} → fg={2,3,1}.
置换的乘法满足结合律,但不满足交换律。

应用:等价类计数问题

以下面问题为例,介绍两个定理。
给2×2的方格黑白染色,共有几种方法?答案显而易见,是如下图的16种。

但如果考虑“旋转同构”,将逆时针旋转90°,180°,或270°都相同的方案看做一种,答案就只有如下6种了

这就是等价类计数问题,也就是,题目中会定义一种等价关系,满足等价关系的所有元素被分为同一个等价类,他们共同为答案贡献1。
我们发现,等价关系满足自反性,对称性和传递性。

我们把F定义为一个置换集合,集合里元素乘积也在集合里,用它来描述等价关系。
如上面例子中,我们有F={①逆时针旋转0°,②逆时针旋转90°,③逆时针旋转180°,④逆时针旋转270°},这样我们就可以用这个集合表示所有等价关系了。
需要注意的是,①②③并不能构成一个“置换群”,因为②×③=④并不在集合里。

对一个置换f,若一个元素经过置换后不变。则称它为f的不动点。

Burnside 引理
计f的不动点数目为C(f),等价类集合数目为所有C(f)的平均值。

如上面的例子,C(①)的不动点有1-16,C(②)的不动点有1,16,10,7,C(③)的不动点有1,16,C(④)的不动点有1,16,故根据Burnside 引理,等价的方案有(16+4+2+2)/4=6个。是不是很神奇呢?

而已知一个置换,怎么快速求$C(f)$呢?
回想用循环表示置换,我们发现,若一个循环中所有元素状态相同,则一定有置换后不变。
设f分解为$m(f)$个循环的乘积,每单个元素有$k$种状态(如黑白染色是两种),有$C(f)=k^{m(f)}$,这就是Polya定理。
基础的知识就告一段落辣…

例题

[UVa 10294] Arif in Dhaka

[Description]
t种颜色的珠子中选n个串成间距相等的圆形项链。问若旋转后项链相同算一种,问有几种项链;旋转或翻转后(形态和位置)相同算一种,问有几种项链。
[Solution]
第一种较为简单。共有n种旋转的置换(旋转0~n-1个位置),旋转i个位置的循环节为gcd(i,n),所以$ans1=(\sum_{i=0}^{n-1}t^{gcd(i,n)})/n$
第二种除了旋转,还有翻转。翻转需分类讨论,若n为奇数,共有n条对称轴,每条对称轴的循环节为n/2+1,所以总不动点数$x=n×t^{n/2+1}$;若n为偶数,有n/2条对称轴串过珠子,每条对称轴的循环节为n/2-1,有n/2条对称轴不串过珠子,每条对称轴的循环节为n/2,总不动点数$x=n/2×(t^{n/2-1}+t^{n/2})$,得出$ans2=(ans1*n+x)/2n$.

[LA 3641] Leonardo’s Notebook

[Description]
给出26个字母的一个置换$B$,问是否存在一个置换$A$,满足$A^{2}=B$.
[Solution]
给出B后我们可以分循环来讨论。
对于某一个循环a,若元素数n为奇数,我们不难找到一种方案:ai->ai+n/2+1,两次置换后得到ai->ai+1,这就是B.
而若n为偶数,我们同一个循环肯定不能“开根号”,但是我们发现,若有两个长度均为n的循环a,b,它们的乘积却可以。a={a1,a2..an},b={b1,b2…bn},ab=(a1,a2..an)(b1,b2…bn)=(a1,b1,a2,b2…an,bn)×(a1,b1,a2,b2…an,bn).这样也有解。
这样,将B拆成循环进行判断即可。

[UVa 11077] Find the Permutations

[Description]
给定n,k(k≤n≤21),问有多少个n的全排列至少进行两个元素的互换操作才能变成{1,2…n}.
[Solution]
观察发现,全排列的一个循环交换有序需要循环元素个数-1次交换。
设f[i][j]表示i的全排列进行两个元素的互换操作才能变成{1,2…i}的个数,容易得到递推式
$$f[i][j]=f[i-1][j]+f[i-1][j-1]*(i-1)$$
f[i-1][j]表示直接把i放在最后,自成一个循环;f[i-1][j-1]表示把i插入任意一个循环,使这个循环得交换次数+1,因为可以插入任何一个位置,共有i-1种插法。边界为$f[1][0]=1$,其他$f[1]=\{0\}$.
很善意地不要打高精度。

[LA 3510] Pixel Suhffle

[Description]
给n*n矩阵的矩阵定义8×2种操作(具体见题),给定一串命令,有多个操作组成,求至少经过多少次命令后矩阵才能恢复。
[Solution]
以前似乎做过一道一维简化版的…
就是直接模拟一遍操作,记录所有方格移动到的位置,然后找到所有循环。
设每个循环有x个元素,所以循环内的元素要恢复,就必须完成x的倍数次操作。
所以所有循环元素个数的最小公倍数即是问题的答案。
AC此题需要耐心。