课程：组合计数第二讲排列组合拓展

讲义

有重排列（多重集的线性重排）

若一列共有个元素，其中第类相同元素有个（，且），则不同线性排列数为

要点

本质是“除法原则”：
先把相同元素临时“贴编号”得到种，再除去对每一类内部次重复。
与多项式系数统一：它就是“多项式系数” 。
极端与边界：若某一类可直接忽略；若所有元素互异，退化为。

例子 1 BALLOON 的不同重排

单词 BALLOON 中，，计数：。

解释：临时把两个编成，两个编成，共有；去掉的内部互换次、的内部互换次。

理解

“格路图像”：把次向东、次向北、… 的步子交错排列，等价于从原点走到点的“单调路径”数，恰为多项式系数。几何上是把一串不同颜色的步子混排。

多项式定理（Multinomial Theorem）

对任意，$n\in\mathbb{Z}{\ge 0} $，$ $
(x_1+\cdots+x_r)^n=\sum{\substack{k_1+\cdots+k_r=n \ k_i\ge 0}} \binom{n}{k_1,\dots,k_r}, x_1^{k_1}\cdots x_r^{k_r},\qquad
\binom{n}{k_1,\dots,k_r}=\frac{n!}{\prod_i k_i!}.
$$

要点

组合意义：从个括号中，每个括号选一个变量；恰选次的方案数即为多项式系数。
重要求和：令，得
加权恒等式（标记法）：例如

推广得

例子 1 系数抽取

中的系数为

解释：6 个括号里选两次、三次、一次，选法数即为多项式系数。

理解

“ 选 1”模型：每一步在个备选里做 1 次选择，步的路径集合与的展开同构；合并同类项就是把“无序计数”的本质显影。

圆排列（全异元素，忽略旋转）

个互不相同的元素沿圆周排列，若只把“整体旋转”视为同一方案，则不同圆排列数为

要点

破除旋转对称：固定一个元素（或固定一条直径方向），剩余个元素按线性排列。
与“翻转是否同一”无关的约定要先说清：本节默认不把镜像视为相同（即“项链”而非“手镯”）。
边界：时按习惯记为种。

例子 1 6 人围坐圆桌

6 人互异，圆排列种。
解释：固定 A 的座位，余下 5 人排座次即。

理解

“轨道计数”的极简版：旋转群作用下的轨道数等于把一个人钉住后的线性排列数。直觉上“抠掉”整体旋转这 1 个自由度。

圆排列（含相同元素，忽略旋转）

设有多重集计数、总数，不同圆排列（仅按旋转视为同一）由 Burnside 引理给出：

其中为欧拉函数，为指示（真为，否则）。

要点

旋转等价于把圆分成个相同“块”，每块长度为；能被该旋转固定当且仅当每种元素个数都能被均分到各块里（即）。
固定这类旋转后，块内是线性重排，方案数为；该旋转的不同角度个数为。
常用特例：若，则

例子 1 两红两蓝绕圆（）

。

：，贡献；
：且，贡献；
：但，贡献。
总数

直观上就是两型：（同色相邻）与（交替）。

几何解释

Burnside 的“转一圈取平均”：把所有旋转的“可见方案数”求平均，就是去掉旋转对称后的真实方案数。
周期块图景：被某个旋转固定意味着“沿圆周是一段花纹重复次”；每个颜色的总量必须能均匀切成份。

探究

Round 1

【疑问】关于“多项式系数”，我并不知道它是什么，能不能简单介绍一下（不铺开讲）

定义与两种含义

记号与公式
计数含义
- 把个位置用类标签填满，其中第类恰用次，同类内部不区分顺序。不同填法数就是上式。
代数含义
- 展开式中的系数就是它。

极短例子

“10 格涂色，红 4、蓝 3、绿 3”：方案数

Round 2

【疑问】关于有重排列的理解“格路图像”我没有看懂

二元格路直观（最清楚的版本）

有步向东 E，步向北 N，总步数。
“把 E/N 混排”的每一种方式，唯一对应一条从到的单调格路。
因为同类步子不可区分，所以不同路径数

推到多元

三类步子 E/N/U，分别走步，对应三维网格从原点到的单调路径数：
核心直觉
- “同色步子换序不变路径” ⇒ 需要除以每类的；把“有重排列”看成“多色步子交错插入”。

Round 3

【理解】用当时理解二项式定理和二项式系数的“抽取”方法，可从个乘项中，每个括号选一个变量；恰选次的方案数即为多项式系数。为什么又是公式那样子？考虑固定选择顺序，选的前 k1 个属于 x1，这个其实并不影响，因为我们不在意 xi,xj 的相对顺序，所以可以自定义过程，对总的方案数为 n! 的结果不影响。但是由于对于同一种类内我们的操作带来了顺序性（n * (n - 1) 其实隐式承认 ab ba 是两种情况），而最终的结果又只关注个数，所以要除上同种内部产生的。

评价与补强

你的思路是对的：先“贴编号”得到，再除去每类内部的重复，得到

另一种同等严谨的过程（不借助“贴编号”）：

先在个位置中选出放的个位置：；
在剩余个位置中选出放的个位置：；
如此递推，连乘即

小提醒

“固定选择顺序”仅是计数过程，不会引入偏差；但要注意我们选的是“放哪一类的哪些位置”，而不是给同类“内部排序”。

Round 4

【疑问】你的加权恒等式是怎么来的？推广的那一步又是怎么来的？需要详细讲一下，就像对多项式定理本身一样详细的讲一下。

场景统一

看长度为的序列，每个位置从类中选 1 类；记为第类出现次数（）。
基本恒等式

一阶加权（总出现次数的加权和）

目标
组合法（指示变量/逐灯计数）
- 左边把每个序列按“第类出现了几次”计权。把“每一次出现”想成“给该序列的一个具体位置打标且该位置取第类”。
- 计数：先选被标记的位置（种），把它定为第类（1 种），其余个位置任选类（种）。总计。
代数法（求偏导）
- 从
  
  出发，对求偏导并令：

二阶加权（两个类的联动）

目标（）
组合法
- 统计“序列中一个位与一个位”的有序二元组。
- 先选两个不同的位置并指定它们分别为（种），其余个位置自由（种）。乘法原理得到右式。
代数法
- 对先对、再对求偏导，令即得。

同类二阶（第二矩）

拆分恒等式
- 第一部分：选两个不同位置都放（有序），计数；
- 第二部分：用一阶加权结果。
结论

心法模板

“定几盏灯（位置）→ 其余自由填”，乘法原理；与“期望线性性”的思维结构完全一致。
代数上则是“对生成式求偏导→代 ”。

【疑问】
“计数：先选被标记的位置（种），把它定为第类（1 种），其余个位置任选类（种）。总计。”
你这个不会重复计数吗？你的“标记”是什么意思？还需要再详细一点！

术语澄清：什么叫“标记”？

我们讨论的是长度为的序列，每个位置从类中选 1 类（可记作字母）。
记为“第类在序列中出现的次数”。
“标记”指的是：不仅看一个序列，还额外指定序列中的某个具体位置，并要求该位置的取值恰为第类。
于是，一个“标记序列”就是一个有序对，其中是序列，且。

直观地说：把“某个序列里‘第类’的每一次出现”都单独拎出来看，并且给这一次出现做上“这是第位”的标签。

双计数框架（形式化）

定义集合
左边（加权和）数的是：
对任意固定序列，其中“第类”的出现次数是。这恰好是与搭配的可行的个数，因此
右边（先选标记位置再自由填）也数的是：
先选有种，把固定为，其余个位置各自独立地在类中任选，故有种序列。不同的形成不相交的子集，故总数

把两种计数方式相等起来，就得到

为什么不会“重复计数”？

拆分原则：已经由不同的分成了个不相交的部分

不同的部分互不重叠，因此“对求和”不会把同一个有序对算两次。
同一内部也不重：固定后，其他个位置的填法一一对应不同的序列，因此唯一确定。
注意目标本来就是“按出现次数加权”。同一个序列若含有次第类，它确实应该被“算次”，每次对应一个不同的有序对。这正是左边求和的含义，也正是我们把“标记位置 ”纳入对象后自然而然实现的事情。

指示变量版（同义但更代数）

定义指示变量。则
交换求和次序（Fubini）
对固定的，有（只需把第位定成，其他任意），于是结论

一个小例子（肉眼可查）

取（字母），令。所有个序列与：

；；；；
；；；。
求和。而，吻合。
若枚举的有序对，它们正好是一一对应“每个序列中每一个 A 的位置”，没有任何重复。

——这就是“标记”的精确定义与“不会重复”的理由。核心是：我们数的对象不是“序列本身”，而是“序列里的某一次第类出现（连同它的位置）”；用分组与双射保证每个对象恰好计一次。

Round 5

【疑问】含相同元素的圆排列还需要讲解的更细致一点，比如那个公式我有很多没有看懂的地方。

目标与约定

多重集计数，总数。把它们绕圆排列，视“旋转”为同一（不把镜像当同一）。求不同方案数。

Step 1：一个具体旋转何时“看不出变化”

设把圆周位置编号，旋转格（）把映到。
该置换把圆分成若干“循环轨道”（cycle）。记，则有条轨道，每条长度
一个排法若在这次旋转下“不变”，当且仅当每条轨道上都是同一种颜色。于是每用某颜色一次，必须整段用个。
必要且充分条件
$对所有$
成立时，把条轨道分给各颜色：给颜色分配了条轨道。方案数为多项式系数

Step 2：有多少个“轨道长度为 ”的旋转

由，等价于。
满足的的个数是。取，得到“轨道长为的旋转个数”是

Step 3：Burnside 取平均

Burnside：不同排法数各个群元（这里是个旋转）固定的方案数的平均：
$You can't use 'macro parameter character #' in math mode # = \frac{1}{n}\sum_{t=0}^{n-1} \mathrm{Fix}(t) =\frac{1}{n}\sum_{L\mid n} \Big(,[L\mid a_i\ \forall i],\cdot \varphi(L)\cdot \frac{(n/L)!}{\prod_i (a_i/L)!}\Big).$

快速特例（最常用）

若，除了，别的都不会整除所有，于是
$You can't use 'macro parameter character #' in math mode #=\frac{1}{n}\cdot \frac{n!}{\prod a_i!} =\frac{(n-1)!}{\prod a_i!}.$

两个例子（逐计算）

例 1：，，
- ：贡献；
- ：贡献；
- ： ⇒ 贡献；
- 平均： $You can't use 'macro parameter character #' in math mode#=\dfrac{1}{4}(6+2)=2$ （交替与成对两型）。
例 2：，，
- 因为，直接用特例
  $You can't use 'macro parameter character #' in math mode #=\frac{(9-1)!}{4!,3!,2!} =\frac{40320}{(24)(6)(2)}=140.$
- 若你想验证 Burnside：。
  - ：贡献；
  - ：需不成立 ⇒ 贡献；
  - ：需不成立 ⇒ 贡献；
  - 平均：。

常见易错点

“旋转同一”≠“镜像也同一”。若把镜像也视为同一（手镯），需把反射也纳入群作用，公式分的奇偶讨论，这里暂不引入。
的意义是“一个周期块的长度”，不是“可旋转的步长本身”。二者通过关联。

如果你还有具体算例或某个的分组看不顺，请继续【疑问】指出那一行，我把那一段单独拆到“Round +1”里细讲到位。

启发式问题

把单词 MISSISSIPPI（）围成圆圈，若只按旋转视为相同，有多少种不同排法？
提示：先判断，再决定用快速特例还是 Burnside 全式。

【复习】

有重排列的核心是“除法原则”与多项式系数。
圆排列（全异）为；含相同元素需用 Burnside，特例时可用。
多项式定理是二项式的全推广；系数求和与加权恒等式用“标记法/代数法”皆可到达。

【练习】

线性重排：PROBABILITY 中有，共有多少不同排列？
圆排列（全异）：8 人围坐圆桌，若把镜像也视为相同（手镯模型），共有多少种？（提示：，但注意的边界。）
圆排列（相同元素）：绕圆（只按旋转为同一），求方案数。
多项式恒等式：证明

给出组合法解释（提示：两个元集合各取与组成元集合）。
加权求和：求

并与“更多恒等式”中的结果对照（给出代数或组合两种证明之一即可）。

Do not go gentle into that good night.

课程：组合计数 第二讲 排列组合拓展

讲义