集合与图论学习笔记04

定理

抽屉原理

简单形式

将个物品放入个抽屉，如果，则至少有一个抽屉包含至少两个物品。

数学表述：
如果，则存在一个抽屉至少有个物品。

推广形式

将个物品放入个抽屉，则至少有一个抽屉包含至少个物品，
且至少有一个抽屉包含至多个物品。

应用例子

1.映射个数

从元集到元集的映射个数为：

2.序列选取

是由个不同实数选取的一个序列，则一定可以选取个数的严格单调递增或者单调递减的子序列

容斥原理

两个集合的情况

对于有限集和：

三个集合的情况

对于有限集,,：

一般形式（n个集合）

对于有限集：

等价地：

补集形式（计数都不在其中的元素）

设全集为，则：

应用例子

1. 错位排列

个元素的排列，没有元素在原始位置的方案数：

2. 欧拉函数

小于且与互质的正整数个数：

其中取遍的所有质因数。

3. 包含排斥问题

从到中不被整除的整数个数：

4. 满射函数计数

从元集到元集的满射函数个数：

---

递推与生成函数

母函数（生成函数）定义与分类

母函数基本思想

母函数是一种形式幂级数，其系数编码某个数列的信息，通过代数运算处理数列间的组合关系

母函数作为形式幂级数时，不考虑收敛性，只进行代数运算。在解析应用中需要考虑收敛半径

普通生成函数（OGF）

对于数列 $\{a_n\}{n\ge 0}A(x) = \sum{n=0}^{\infty} a_n x^n$

用于无标记对象的组合计数，系数通常表示大小为的对象的个数

常见OGF

• 常数序列：
• 二项式系数：
• 斐波那契数列：

指数生成函数（EGF）

对于数列 $\{a_n\}{n\ge 0}A(x) = \sum{n=0}^{\infty} a_n \frac{x^n}{n!}$

用于有标记对象的组合计数，系数表示大小为的有标记结构的个数

常见EGF

• 常数序列：
• 排列数：
• 圆排列数：

狄利克雷生成函数（DGF）

对于数列 $\{a_n\}{n\ge 1}A(s) = \sum{n=1}^{\infty} \frac{a_n}{n^s}$

用于数论函数的乘法卷积，在解析数论中应用广泛

常见DGF

• 常数函数：（黎曼ζ函数）
• 莫比乌斯函数：
• 欧拉函数：

母函数运算与组合结构

• 加法运算

有

• 乘法运算

  • OGF乘法：对应有序对或笛卡尔积即
  • EGF乘法：对应有标记对象的乘积结构即

• 复合运算

对应结构的复合，如：

• • OGF复合：序列的替换

设,，且

复合生成函数为：

• • EGF复合：结构的组合（如集合的划分）

设,（）

复合生成函数为：

母函数运算的性质

递推关系的求解

线性常系数齐次递推关系

对递推关系

其中给出初值

有递推关系对应的特征多项式

母函数

对齐，把每一列乘上对应冒号左边的数可以得到母函数减去一个多项式

把母函数放在一起，整理即：

我们定义，令

令

那么有

在复数域上有个根，设其中

则

对每一项都是次方不超过的多项式

其中为常数

那么再对每一个项做幂级数展开

对照

有

无重根的项

这部分设有个

也就是

对应有

复数根的项

这部分设有个

也有

设必定一对共轭复根

在幂级数展开的时候导致的的系数

有重根的项

展开时由二项式定理

这里出现了一个关于的次多项式

也就是

这里待定

然后通过把所有项加起来即可得到通项公式

求递推的时候就可以通过求特征多项式的根，按照上面的形式通过用初值待定系数求出相应的系数，最后求出通项

模型

模型 4.1 全排列

取个互不相同的元素的全体进行排列，称为的全排列，方案数为

模型 4.2 排列

从个元素种选取个元素按顺序排成一列，称为排列，方案数为

可以看作个球里面选取个球做上标记放入个不同的盒子中，不允许空盒，每个盒子中最多有个球的方法数

模型 4.3 组合

从个元素种选取个元素不考虑排列的顺序，称为组合，方案数为

可以看作个球里面选取个球做上标记放入个相同的盒子中，不允许空盒，每个盒子中最多有个球的方法数

另一方面，这两个模型的区别在于盒子是否相同，个球放入个不同的盒子里面的方法数为，这个方法在盒子相同时是重复的，算作种情况，得到，这里的称为组合的重复度

模型 4.4 圆排列

从个元素种选取个元素按顺序排成一个圆形，称为圆排列，方案数为

可以看作个球里面选取个球做上标记放入个不同的盒子中把盒子排成一个圈，不允许空盒，每个盒子中最多有个球的方法数

另一方面，对数量为的一个排列，不管哪一个元素为头哪一个元素为尾，这种排列在圆排列下均为种情况，得到

模型 4.5 可重排列

最基础的可重

从种元素中允许重复的选取次得到的考虑顺序的排列，方案数为

如果我们限制可以选取元素的次数，若取次并且

根据之前重复度的理论，全排列方案数为，我们记这个为多重组合数

考虑相邻元素不同

从种元素中允许重复的选取次得到的考虑顺序并且相邻的元素不同，方案数为

考虑每种元素至少出现一次

采用容斥原理解决

从种元素中允许重复的选取次得到的考虑顺序并且每种元素至少出现一次，方案数为

证明： 点击查看证明

定义坏事件为某种元素没有出现

要求的即为没有任何坏事件发生的事件，即

由容斥原理，

接下来计算

先从种元素中任取种，讨论这种都不存在，方法数即为

根据容斥原理，最终方法数为

考虑每种选取的元素存在上限

记为表示至多取次，若所有，平凡的，方案数为

考虑至少存在一个，采用容斥原理解决

从种元素中选个（可重复，有序），每种元素最多选次，且至少存在一个，并且，方法数为

其中多组合数

证明： 点击查看证明

定义坏事件为某种元素被选了超过次

要求的即为没有任何坏事件发生的事件，即

由容斥原理，

接下来计算

考虑先分配个位置给，再分配个位置给…最后剩下的元素给以下的选取方式：从种元素中无上限选取个元素

方法数为

根据容斥原理，方法数即为

考虑相邻元素不同且每种元素至少出现一次

从种元素中选个（可重复，有序），相同元素不能相邻，且每种元素至少出现一次，方法数为

证明： 点击查看证明

设全集为相邻不同的排列数：。

定义坏事件表示”元素没有出现”

由容斥原理：

其中= 用种颜色染个位置且相邻不同的排列数 =（当且）。

因此：

考虑相邻元素不同并且每种选取的元素有上限

从种元素中选个（可重复，有序），每种元素最多选次，且相同元素不能相邻，方法数为

其中表示用种颜色涂长度为的路径图，相邻顶点颜色不同，且颜色最多用次的方案数，可用动态规划计算。

证明： 点击查看证明

设是相邻相同的相邻位置对的集合（位置,,,共对）

设表示第对相邻位置是相同元素的事件

由容斥原理：

强制中相邻相同后，排列变成个块，相邻块颜色不同

设= 用种颜色涂个块的路径图（相邻块颜色不同），且颜色最多用次的方案数

于是：

考虑每种元素至少出现一次并且每种选取的元素有上限

从种元素中选个（可重复，有序），每种元素最多选次，且每种元素至少出现一次，方法数为

其中表示使用颜色集合，排列长度，颜色最多用次的排列数。

证明： 点击查看证明

设全集为满足数量上限但允许某些元素不出现的排列集合

定义坏事件表示”元素没有出现”

由容斥原理：

其中表示不使用中元素的排列数。

换元，则，得到：

考虑相邻元素不同并且每种元素至少出现一次并且每种选取的元素有上限

从种元素中选个（可重复，有序），每种元素最多选次，相同元素不能相邻，且每种元素至少出现一次，方法数为

其中表示用颜色集合涂长度为的路径图，相邻顶点颜色不同，且颜色最多用次的方案数。

证明： 点击查看证明

结合前几个问题的结果

先考虑”相邻不同且每种至少一次”的容斥：

其中是使用颜色集合，排列长度，相邻不同，颜色最多用次的排列数。

由问题1的结果：

代入得：

模型 4.6 可重组合

最基础的可重

从种元素中允许重复的选取次得到的不考虑顺序的组合，方案数为

可以看作个相同的球放入个不同的盒子中，允许空盒，允许每个盒子多于个球的方法数

证明： 点击查看证明

我们从中选可重组合有序关系

做映射有序关系，得到这个数不同，得知

从中选可重组合对应 从中选不可重组合

反过来 从中选不可重组合有序关系

做映射有序关系，得到这个数可能相同，得知

从中选不可重组合对应 从中选不可重组合

这是一个一一对应，所以它们方法数相同均为

考虑每种元素至少出现一次

从种元素中允许重复的选取次得到的不考虑顺序并且每种元素至少出现一次的组合，方案数为

证明： 点击查看证明

我们从中先选一组不重复的，接着就变成了从个元素中选取个可重元素，根据上面的结论，应该为

考虑每种选取的元素存在上限

此外，如果限制可以选取元素的次数并且假定结论是相同的

如果存在一个则需要采用容斥原理解决

从种元素中选个（可重复，无序），每种元素最多选次，且至少存在一个，方法数为

其中表示强制让中每个元素至少选个时的方案数

有

即最终方法数为

证明： 点击查看证明

由上面知道，如果没有限制，设无约束的所有方案集合，

定义坏事件为某种元素被选了超过次

要求的即为没有任何坏事件发生的事件，即

由容斥原理，

这里记

先选个元素再从种元素中无上限选取个元素即可，就有

考虑存在上限的同时每种元素至少出现一次

继续考虑每种元素至少出现一次，方法数为

证明： 点击查看证明

前部分使用容斥原理和上一个相同，只是对计算不同，套用的公式变为了

拆分数

设正整数。定义为的拆分数，即将表示为若干正整数之和的不同方式的个数。我们约定拆分的顺序不计

母函数

固定拆分项个数的母函数

若要求拆分恰含个拆分项，设为拆分数。母函数为：

其中表示取系数。该方法可进一步推广到多重限制拆分：拆分项个数属于集合时：

拆分项奇偶或模约束

• 奇数拆分：

• 偶数拆分：

• 模拆分：拆分项满足的母函数：

Euler 公式及不重复拆分

Euler 证明：

说明奇数拆分数等于不重复拆分数

拆分为最多 m 个数的母函数

设正整数，要求拆分为最多个正整数之和，记拆分数为。引入变量记录拆分项数：

取的系数并对求和，即得到最多项的拆分数：

等价关系

根据母函数对称性可知：

即 “拆分为最多个数” 与 “拆分中最大数不超过” 的拆分数相等：

q-系列与递推公式

引入-系列展开：

递推关系为：

其中当。

带权拆分与加权母函数

若对拆分项赋权，母函数为：

特例：

• → q-加权拆分
• 限制多重出现 → 不重复拆分