专栏文章

置换/排列

WWilliam2022
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mimxvpub
此快照首次捕获于
2025/12/01 17:20
3 个月前
此快照最后确认于
2025/12/01 17:20
3 个月前
查看原文
置换：位置调换。
123
231
理解A：位置 22 的值换到 11 位置，位置 33 的值换到 22 位置，位置 33 的值换到 11 位置。
理解B：位置 11 的值换到 22 位置，位置 22 的值换到 33 位置，位置 11 的值换到 33 位置。

建图

序列转图/KMP树 笔记。
循环节表示法，

置换/排列

排列是状态，置换是对状态的操作。

例1

环形手串有 nn 个珠子，有 mm 个颜色，问有多少本质不同的染色方案。
不要低估本题难度
高中奥数
很多选手会极度低估本题。
本质不同需要解决若干个操作。
对手串旋转任意角度
对手串对称翻转
结论（Burnside引理）
本质不同的方案计数 == 每个操作的平均不动点数

Brunside 引理证明

基础概念

群
群是特殊的集合。
且可以运算。
如果集合 GG 与二元运算 ∗*，满足以下性质，则 (G,∗)(G,*) 为一个群。
  1. 封闭性
  2. 结合律
  3. 单位元
  4. 逆元
置换群 Group
一些置换组成的群，运算 ∗* 为两置换叠加。
记 XX 为染色方案集合，GG 为置换集合。
轨道 Orbit
在置换群 (G,∗)(G,*) 作用下，xx 的轨道记作 G(x)G(x)。
G(x)={g(x)∣g∈G}G(x)=\{g(x)\mid g\in G\}
就是 “等价类”
稳定集 Stabilizer
对于 x∈Xx\in X，在置换群 (G,∗)(G,*) 作用下：
xx 的稳定集（不动置换群）记作 GxG^x。
Gx={g∣g(x)=x,g∈G}G^x = \{g\mid g(x)=x,g\in G\}
Gx⊂GG^x \subset G
不动点
对于 x∈Xx\in X，g∈Gg\in G：
若 g(x)=xg(x)=x，xx 是 gg 的不动点。
轨道-稳定集定理
∀x∈X,∣G(x)∣∣Gx∣=∣G∣\forall x\in X,\mid G(x)\mid \mid G^x\mid=\mid G\mid

正文

等价类计数 ∑x∈X1∣G(x)∣\sum\limits_{x\in X}{\frac{1}{\mid G(x)\mid}}
横看成岭侧成峰 每个方案都要贡献。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...