置换
置换
首先说成大白话的形式：一个调换元素顺序的规则就叫置换。
现在用一个比较严谨的说法：
若 (f:A ightarrow A) 是双射的，那么我们称 (f) 为 (A) 上的一个置换。一般而言，我们都是讨论 (A) 为有限集的情况。
一般而言，如果 (A={a_1,a_2,dots,a_n})，我们会用一个比较直观的方式表示一个置换：
这表示 (f) 的映射规则为 (a_1 ightarrow b_1,a_2 ightarrow b_2,dots,a_n ightarrow b_n)。
一些比较琐碎的内容：
-
如果 (f) 为 (A) 上的一个置换，则称 (|A|=n) 为 (f) 的大小 or 长度 or 阶数；
-
由于 (f) 的双射性质，故存在 (p) 为 ({1,2,3,dots,n}) 的一个排列，使得对于任意的指标 (k)，(a_{p_k}=b_k)；
于是不难得出长度为 (n) 的置换有 (n!) 个；
-
对于置换 (f,g)，称它们两个不相交，当且仅当若 (f:A_1 ightarrow A_1,g:A_2 ightarrow A_2)，则 (A_1cup A_2=varnothing)；
置换复合/乘法
我们自然很好奇，对于一个 (A)，连续施加置换会发生肾摸事。
考虑现在有 (A) 上的两个置换 (f,g)，如果我们先对于 (A) 施加 (f)，再施加 (g)，会变成什么样？
显然可以对于每个元素单独考虑：对于元素 (a_kin A)，原先为 (a_k)，现在 (g(f(a_k)))。
不难注意到，最终 (A) 的变化仍然可以使用一个置换来表示。这意味着我们可以找出一个新的置换 (h) 表示这种变化规则：
这自然而然地引申出了置换的复合运算：
当然，需要注意运算顺序。在下文中，如果不会导致歧义，我们也会勇敢地使用 (fg) 来直接表示 (fcirc g)。
轮换
我们来看一下一类特殊的置换：
也就是每个元素都向前挪一下。
这就好比将所有元素从 1 到 (n) 顺时针排布在一个环上，再将环逆时针旋转一下，得到的就是施加轮换的结果。
所以它的名字就叫 cycle。
另一种表示法，用上了轮换的特殊性：
轮换分解
这个轮换有什么作用？比如说，轮换的结构较置换而言简单得多。
而更重要的是，任意一个置换都可以分解成若干个不相交轮换的组合。
也即，对于长度为 (n) 的置换 (f)，有：
且对于 (i ot=j)，都有 (sigma_i,sigma_j) 不相交。
这里轮换的组合意味着若 (pi=sigma ho,sigma:A_1 ightarrow A_1, ho:A_2 ightarrow A_2)，则 (pi(k)=egin{cases}sigma(k)&kin A_1\ ho(k)&kin A_2end{cases})。
这个重要性质的证明可以对长度使用归纳法，在此不赘述；
此外，也可以说明在忽略轮换之间的顺序的情况下，这种分解是唯一的；比较显然也不赘述；
一般情况下，我们用 (c(f)) 表示置换 (f) 分解后的轮换数量。
需要注意的是，由于我们常常会在轮换分解中略去一阶轮换的书写，所以使用轮换表示置换的时候，指出阶数是很有必要的。
轮换分解的好处都有啥？谁说对了就给他
可以发现，轮换分解有两个优点：
- 结构清晰，可以让人容易看出置换的具体作用；
- 独立，轮换之间互不干扰，又有相似结构，方便研究；
轮换指标
有时候我们可以忽略置换的具体结构，只关心置换的轮换的组成结构，那么一个置换可以导出它的轮换指标。
为此，我们需要用 (c_j(f)) 表示置换 (f) 拆分后，具有的长度为 (f) 的轮换数量，那么 (f) 可以被表示为：
具体的我们会放到后面来说。
群与置换群
群
对于一个集合 (G) 和一个在 (G) 上的二元运算 (circ)，如果 (G) 和 (circ) 满足如下四条性质：
- 封闭性：(forall a,bin G,acirc bin G)；
- 结合律：(forall a,b,cin G,(acirc b)circ c=acirc (bcirc c))；
- 幺元存在：(exists ein G,forall ain G,acirc e=ecirc a=a)，此时这个 (e) 被称为幺元。一般而言，也用 (e) 来表示一个群里的幺元；
- 逆元存在：(forall ain G,exists bin G,acirc b=bcirc a=e)，此时 (b) 被称为 (a) 的逆元，记作 (a^{-1}=b)；
那么，二元组 ((G,circ)) 构成一个群。一定要注意的是，一个群的集合和它的运算是有机结合的，群论研究它们两个而非其中任何单独的一个。
为什么我们需要研究群呢？
因为实际问题中，许多系统的性质和系统里具体装的什么、甚至具体是什么并不相干，它们是独立于系统之外的。
如果我们发现一个群可以被应用到一个实际的系统上，那么许多系统的性质便以不证自明了。
举个例子，有一个群，是这样的：
对于 (nin mathbb{N_+},G_n={xin mathbb{N}|x<n})，可以验证 ((G_n,+)) 构成一个群。
那么在实际生活中，我们假装你在原地转圈圈，转一次只会恰好转 (frac{2pi}{n})。
不错，这个转圈圈的问题就可以直接用 ((G_n,circ)) 来描述，自然也就可以迅速地推导出如下结论：
- 封闭性：你不会转着转着转出了 (2pi(phi-1)) 这样奇奇怪怪的朝向，事实上我们已经掌握了你所可能的全部朝向；
- 结合律：先转 (a+b) 下，最后转 (c) 下，和先转 (a) 下，再转 (b+c) 下效果相同；
- 幺元存在：如果你转了 0 下，那么你的朝向不发生改变；
- 逆元存在：如果你转了 (a) 下（(0le a<n,ain N)），那么你再转 (n-a) 下一定会回到你原来的朝向；
是吧，依靠一个已经研究透彻的群，我们已经得到了如此强的结论，近乎可以预测你的任意旋转的结果虽然这个例子看起来非常
嗯哼，但是也一定程度上反映了群论的强大，更何况我们现在仅仅是使用了群的最基本的性质。
小心一点，以下笔者似乎会使用 (G) 来同时表示一个群和一个群中元素的集合
以下是一些重要但琐碎的概念：
- 子群：对于群 ((G,circ))，和 (Hsubseteq G，H ot=varnothing)，若 ((H,circ)) 也构成一个群，那么称 ((H,circ)) 为 ((G,circ)) 的一个子群，记作 (Hle G)；
- 无限、有限与阶：如果群 ((G,circ)) 中，(G) 为无限集，此时称 ((G,circ)) 为无限群；反之称之为有限群，且称 (|G|) 为群的阶数；
置换群
根据上面对于置换的认识，我们可以发现，长度相同的置换也构成一个群。
考虑所有定义在集合 (A={a_1,a_2,dots,a_n}) 上的置换，设 (P_n) 为长度为 (n) 的置换构成的集合，设 (circ) 为置换的复合，不难验证：
-
封闭性：(forall f,gin P_n,fcirc gin P_n)；
-
结合律：(forall f,g,hin P_n,(fcirc g)circ h=fcirc (gcirc h))；
说明：(forall a_kin A,(fcirc g)circ h=h(g(f(a_k)))=fcirc(hcirc g))；
-
幺元存在：在 (P_n) 中，幺元为以下恒等置换：
[e_n=left(egin{matrix}a_1&a_2&a_3&dots&a_n\a_1&a_2&a_3&dots&a_nend{matrix} ight) ]说明：容易验证，(forall fin P_n,fcirc e_n=e_ncirc f=f)。
(n) 确定的时候，我们也可以省略 (e_n) 而写作 (e)。
-
逆元存在：对于 (fin P_n)，若有：
[f=left(egin{matrix}a_1&a_2&a_3&dots&a_n\b_1&b_2&b_3&dots&b_nend{matrix} ight) ]那么可以得到：
[f^{-1}=left(egin{matrix}b_1&b_2&b_3&dots&b_n\a_1&a_2&a_3&dots&a_nend{matrix} ight) ]容易验证 (fcirc f^{-1}=f^{-1}circ f=e)。
此时构成的群 ((P_n,circ))，也称为 (n) 阶对称群，用 (S_n) 表示。
对称群可以说是相当“自然”的一类群，因为它们很容易就与现实问题挂钩。
例如，正 (n) 边形的旋转/对称操作构成的置换群就是 (S_n) 的一个子群。
对称群下的轮换指标
我们回头再看一下轮换指标这个东西。
首先需要注意的是，其中的 (t) 是形式变元，我们并不在乎它是什么，只是这个乘法的“形式”而已。
梦回生成函数
那么，考虑 ((G,circ)) 为 (n) 元集合 (A) 上的一个置换群，则可以定义该群的轮换指标：
特别的，对于 (n) 阶对称群，我们可以计算其中任意一项 (prod_{k=1}^nt_k^{c_k}) 的系数，其中满足 (sum_k c_k=n)：
理解：先选出每个轮换的元素，再考虑轮换内部的环排列方案数，最后还要去除轮换之间的顺序。