置换群#
能拆成偶数个对换的轮换是偶置换，相当于旋转操作
能拆成奇数个对换的轮换是奇置换，相当于镜像操作
置换奇偶性和逆序数个数奇偶性相同
任何置换都能唯一分解成互不相交循环
而互不相交循环一定可交换。
相交循环则通常不可交换
轮换乘积其实是复合
σ⋅τ=σ(τ(id))
Burnside计数原理#
稳定子：
Stab(x)
指：
把染色 x 保持不变的所有旋转集合。
N=∣G∣1g∈G∑Fix(g)其中G是置换群的集合，Fix(g)是g置换下染色固定的方案数，N是旋转对称下不等价的方案数，也就是轨道数，一个染色经过所有旋转后，能得到的一整批等价染色集合，叫一个轨道。
核心公式：
∣Gx∣⋅∣Stab(x)∣=∣G∣，Gx是x的等价集合，也就是等价类
Polya计数原理#
把burnside根据旋转映射(12)(345)这种根据循环数进行了分离变成a2a3，系数仍然一样，代入的都是染色数m，但是可以拆，ak=m=rk+bk，根据组合求方案数
第二类斯特林数#
将含有n个元素的集合划分到r个非空无标号子集的分配方案数量为S(n,r)
满足
S(n,r)=S(n−1,r−1)+rS(n−1,r)至少有1个元素单独组成子集的情况数量有S(n−1,r−1)种情况，其对立命题所有元素形成的集合大小都大于2的情况相当于，对S(n−1,r)每种划分情况，S(n,r)新增的那个元素可以划入到里面的r个子集里的其中之一，故要乘上r
边界条件：
S(0,0)=1S(n,0)=0(n>0)S(n,n)=1公式：
S(n,k)=k!1i=0∑k(−1)iCki(k−i)n
分拆数#
将正整数 n 表示为 r 个正整数之和，且不计顺序的方法数为p(n,r)
满足
p(n,r)=p(n−1,r−1)+p(n−r,r)至少有一个部分等于1的情况有p(n−1,r−1)种情况，其对立命题，所有部分都≥2的情况相当于p(n−r,r)情况的分拆全部加上1(假如和第二类斯特林数一样每项正整数看过去，由于数值相同的分拆项没有不同，不像划分的子集之间是完全不同的，故会重复，故不能像第二类斯特林数那样转化情况)，故情况数等于p(n−r,r)
边界条件：
p(0,0)=1p(n,0)=0(n>0)
分配问题#
表摘录自《组合数学》
| n个球 | r个盒子（位置） | 条件 | 分配方案数量 |
|---|
| 不同 | 不同 | 至少0个 | rn |
| 不同 | 不同 | 至少1个 | r!S(n,r) |
| 不同 | 不同 | 至多1个 | Arn |
| 不同 | 相同 | 至少0个 | i=1∑rS(n,i) |
| 不同 | 相同 | 至少1个 | S(n,r) |
| 不同 | 相同 | 至多1个 | 1 |
| 相同 | 不同 | 至少0个 | Cn+r−1−0rr−1 |
| 相同 | 不同 | 至少k个 | Cn+r−1−krr−1 |
| 相同 | 不同 | 至多1个 | Crn |
| 相同 | 相同 | 至少0个 | i=1∑rp(n,i) |
| 相同 | 相同 | 至少1个 | p(n,r) |
| 相同 | 相同 | 至多1个 | 1 |
排列组合本质上是置换对称下的计数问题
