置换⼊门（知识点）
置换
置换：集合到⾃⾝的双射。通常只考虑有限集合。
即 f :S →S ，且对任意 y ∈S  存在唯⼀的 x ∈S  满⾜ f (x )=y 。
其实就是排列。
置换通常写成
f =
a 1a 2⋯a n
a p 1a p 2⋯a p n 也可以写成 f (a 1)=a p 1,…,f (a n )=a p n
。置换的乘法：就是复合，即
f =
a 1a 2⋯a n
a p 1a p 2⋯a p n ,g =a 1a 2⋯a n a q 1a q 2⋯a q n 则
f ∘
g =
a 1a 2⋯a n
a p q a p q ⋯a p q 轮换：形如
a j 1a j 2⋯a j k −1a j k a i 1⋯a i n −k a j 2a j 3⋯a j k a j 1a i 1⋯a i n −k 的置换。即把⼀些元素循环移位，其余元素不变。可以写成(a j 1a j 2⋯a j k )
k =2 的轮换称为对换。
任意置换都可以拆成若⼲个不相交轮换的乘积，如：
1234525431可以写成
(125)(34)
拆成的轮换个数称为置换的环数 cyc (p )。
⼀个置换可以写成若⼲对换的乘积，且对换个数的奇偶性是⼀定的，也叫做这个置换的奇偶性。根据奇偶性可以分为奇置换和偶置换。置换的奇偶性与 n −cyc (p ) 的奇偶性相同。
如果置换是
123⋯n
p 1p 2p 3⋯p n
则它的奇偶性与排列 p  的逆序对数相同。
对称
⼤⼩为 n  的置换的集合叫做对称 S n 。S n  的阶数是 n !。
字符串截取替换：若集合 S  和 S  上的⼆元运算 ∘ 构成的代数结构 (S ,∘) 满⾜：
封闭性：∀a ,b ∈S ,a ∘b ∈S 。
结合律：∀a ,b ,c ∈S ,(a ∘b )∘c =a ∘(b ∘c )。
单位元：∃e ∈S ,∀a ∈S ,a ∘e =e ∘a =a 。
逆元：∀a ∈S ,∃b ∈S ,a ∘b =b ∘a =e 。称 b  是 a  的逆元，记作 a −1。
⼤⼩为 n  的偶置换的集合叫做交错 A n 。当 n ≥2 时，A n  的阶数是 n !/2。
note：左单位元=右单位元 左逆元=右逆元
Burnside 引理令 G  是作⽤于集合 X  上的。通常 X  是所有染⾊⽅案。若 g ∈G ，记 X g  为 X  中在 g  作⽤下的不动元素。
()()()()
(
)
()
()Processing math: 100%
Burnside 引理断⾔轨道数（记作 |X/G|，也就是所谓本质不同的⽅案数）由以下公式给出：
|X/G|=
1
|G|
∑
g∈G|X g|
即 X 在 G 中每个元素作⽤下不动元素数的算术平均值。
note：
作⽤：假设G是作⽤于集合X上的，定义作⽤是g∘x
(g h)x=g(h x)
ex=x
不动元素：x^g={x\inX|gx=x} eg RGG 交换后两个还是 RGG 此时两个都是不动元素
轨道-稳定⼦定理
令 G 是作⽤于集合 X 上的。若 x∈X，则 x 的轨道 Gx 定义为
Gx={gx∣g∈G}
note：Gx 即 x 染⾊⽅案的等价类，本质相同的元素轨道相同。不同的本质⽅案数即轨道数。
x 的稳定⼦ G x 定义为
G x={g∈G∣gx=x}
note：证明是：
封闭性：若 gx=x,hx=x，则（gh)x=x 满⾜
结合律：显然
单位元：显然存在 ex=x
逆元：x=g^{-1}x
轨道-稳定⼦定理指出
|G|=|G x||Gx|
若G=(S,∘) 是⼀个，H=(T,∘) 也是⼀个，且T⊂S，则称H是G的⼦。
对某个g∈G，gH={gh∣h∈H} 是H的⼀个左陪集，Hg={hg∣h∈H} 是H的⼀个右陪集。
拉格朗⽇定理若H是有限G的⼦，则|H|整除|G|。
证明可以证明a∼b⟺a−1b∈H是⼀个等价关系，且a所在的等价类就是aH。每个等价类的元素个数都等于|H|，因此|H|整除|G|。
记 [G:H] 为H不同的左陪集个数，那么|G|=|H|[G:H]。
由拉格朗⽇定理得 |G|=|G x|[G:G x]。接下来只需证明 [G:G x]=|Gx|。考虑构造双射 φ(gx)=gG x。
若 gx=fx，则 (f−1∘g)x=x，因此 f−1∘g∈G x，因此 fG x=gG x。反过来若 fG x=gG x 则 gx=fx。因此 φ 是⼀个双射。
等价关系：⾃反性、对称性、传递性
Burnside 引理的剩余推导
∑
g∈G|X g|=∑
x∈X|G x|
=∑
x∈X
|G|
|Gx|
=|G|∑
x∈X
1
|Gx|
=|G||X/G| Pólya 定理
若 G 是 X 上的置换，则给 X 中的每个元素涂上 m 种颜⾊之⼀，在 G 作⽤下本质不同的⽅案数为
1 |G|
∑
g∈G m cyc(g)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。