置换群#

能拆成偶数个对换的轮换是偶置换，相当于旋转操作

能拆成奇数个对换的轮换是奇置换，相当于镜像操作

置换奇偶性和逆序数个数奇偶性相同

任何置换都能唯一分解成互不相交循环

而互不相交循环一定可交换。

相交循环则通常不可交换

轮换乘积其实是复合

\sigma \cdot \tau = \sigma(\tau(\mathrm{id}))

Burnside计数原理#

稳定子：

$\mathrm{Stab}(x)$

指：

把染色 x 保持不变的所有旋转集合。

N = \frac{1}{|G|}\sum_{g\in G}{Fix(g)}

其中 $G$ 是置换群的集合， $Fix(g)$ 是 $g$ 置换下染色固定的方案数， $N$ 是旋转对称下不等价的方案数，也就是轨道数，一个染色经过所有旋转后，能得到的一整批等价染色集合，叫一个轨道。

核心公式：

$|Gx|\cdot |\mathrm{Stab}(x)|=|G|$ ， $Gx$ 是 $x$ 的等价集合，也就是等价类

Polya计数原理#

把burnside根据旋转映射(12)(345)这种根据循环数进行了分离变成 $a_2a_3$ ，系数仍然一样，代入的都是染色数 $m$ ，但是可以拆， $a_k = m = r_k + b_k$ ，根据组合求方案数

第二类斯特林数#

将含有 $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) = 1 \qquad S(n,0) = 0 \; (n \gt 0) \qquad S(n,n) = 1

公式：

S(n,k) = \frac{1}{k!} \sum\limits_{i=0}^{k}{(-1)^iC_{k}^{i}(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)$ 种情况，其对立命题，所有部分都 $\ge2$ 的情况相当于 $p(n-r,r)$ 情况的分拆全部加上1(假如和第二类斯特林数一样每项正整数看过去，由于数值相同的分拆项没有不同，不像划分的子集之间是完全不同的，故会重复，故不能像第二类斯特林数那样转化情况)，故情况数等于 $p(n-r,r)$

边界条件：

p(0,0) = 1 \qquad p(n,0) = 0 \; (n \gt 0)

分配问题#

表摘录自《组合数学》

n个球	r个盒子（位置）	条件	分配方案数量
不同	不同	至少0个	$r^n$
不同	不同	至少1个	$r!S(n,r)$
不同	不同	至多1个	$A_{r}^{n}$
不同	相同	至少0个	$\sum\limits_{i = 1}^{r}{S(n,i)}$
不同	相同	至少1个	$S(n,r)$
不同	相同	至多1个	1
相同	不同	至少0个	$C_{n+r-1-0r}^{r-1}$
相同	不同	至少1个	$C_{n+r-1-1r}^{r-1}$
相同	不同	至少k个	$C_{n+r-1-kr}^{r-1}$
相同	不同	至多1个	$C_{r}^{n}$
相同	相同	至少0个	$\sum\limits_{i = 1}^{r}{p(n,i)}$
相同	相同	至少1个	$p(n,r)$
相同	相同	至多1个	1

排列组合本质上是置换对称下的计数问题

音乐

音乐

置换群#

Burnside计数原理#

Polya计数原理#

第二类斯特林数#

分拆数#

分配问题#

文章分享

评论区

音乐

目录

音乐

音乐

11-计数

置换群#

Burnside计数原理#

Polya计数原理#

第二类斯特林数#

分拆数#

分配问题#

文章分享

评论区

音乐

目录