Epi 的组合数学笔记
、
这是 Epi 的选修课之一，北科的选修课与参考书有部分出入，而本笔记基本上是跟着 ppt 走的。
另外推荐《数学女孩》（一系列数学科普小说）作为参考书，对组合数学的学习很有辅助作用。
虽然这门课没有其他的课程水简单，准备考试的时候有点痛苦，但是这门课真的是我憧憬中大学课的样子，学完了真的收获很多。
!!! note “前言”
组合数学的主要解题方法是计数的合理分类和组合模型的转换，并不高深复杂，但学好绝非易事。
本笔记多以 "问题 —— 方法 —— 结论" 为导向，这也是 Epi 在学这门课时用到的方法，故含有大量的例题，还请注意。
前言 —— 在一切开始之前
本章问题只做引入，不要求掌握
!!! question
请给出 3 - 10 阶幻方的一种构造。
奇数阶幻方有通用构造，而偶数阶幻方没有比较通用的构造方法。
!!! question
有
问：能否把这些军官排成
6 阶拉丁方不存在。
!!! question
用三种颜色红、黄、蓝涂染平面正方形的四个顶点，若某种染色方案在正方形旋转某个角度之后与另一个方案重合，则认为这两个方案是相同的。
求: 本质上不同的染色方案。
24 种方案，事实上若颜色数为
!!! question
§ 不同身高的 26 个人随意排成一行。
求证: 总能从中挑出 6 个人，让其出列后，他们的身高必然是由低到高或由高到低排列的。
这被叫做拉姆齐数 (Ramsey Number)
在组合数学上，拉姆齐 (Ramsey) 定理是要解决以下的问题：要找这样一个最小的数
让我们排列组合
加法法则与乘法法则
**【加法法则】** 设事件 A 有
**【乘法法则】** 设事件 A 有
!!! question
某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色和条纹都用红、蓝、橙、黄四种颜色。
求：共有几种着色方案？（注意：底色和条纹不可以同色）
显然是
!!! question
求小于
减法原理：当原问题的求解较为复杂时可以考虑求解命题的反面
全部四位数有
!!! question
求小于
!!! warning
“含 0” 和 “含 1” 不可直接套用。0019 含 1 但不含 0。在组合的习题中有许多类似隐含的规定，要特别留神
不含 0 的 1 位数有
你好，排列组合
【排列】从
基于不同语境，组合数有多种表达形式
【组合】从
基于不同语境，组合数有多种表达形式
!!! question
求:
使用隔板法，原问题等同于向 100 个 1 中插入两个隔板的方法数，即
推广：
!!! question
§ 有 5 本不同的日文书，7 本不同的英文书，10 本不同的中文书。求：
1) 取 2 本不同文字的书；
2) 取 2 本相同文字的书；
3) 任取两本书
!!! question
若正整数
1)
2)
3)
这三个问题都很经典，第三个是大名鼎鼎的欧拉函数。
!!! question
从
记
要满足条件，有四种解法：
- 3 个数同属于 A;
- 3 个数同属于 B
- 3 个数同属于 C;
- A,B,C 各取一数.
而前 3 种是对称情况。
!!! question
某车站有 6 个入口处，每个入口处每次只能进一人，一组 9 个人进站的方案有多少？
!!! warning
人有进入顺序。
隔板法，先做 14 元全排列，再针对入口数降重。
隔板法，先确定位置，在针对人做排列。
!!! question
现需用 26 个英文字母构成一个 5 个字符的串 (字母可重复)，满足如下要求的串为合法字符串。
(1). 六个母音字母 a, e, i, o, u, y 不相邻
(2). 其余的 20 个子音字母不能连续 3 相邻
(3). 相邻的子音字母不能相同
问: 有多少种不同的合法字符串
这是一个需要耐心分类的问题，不妨记
-
： -
： -
： -
： -
： -
： -
：
共计
!!! question
2000 到 7000 之间的偶数，有几个是由不同数字组成的？
-
千位为偶数 (2,4,6)：
-
千位为奇数 (3,5)：
共计
!!! question
5 女生 7 男生要组成一个 5 人小组，其中小组中不允许男生甲和女生乙同时参加
问：不同小组方案数？
减法原理，
Stirling 近似公式
Stirling 近似给出了
下面给出一种证明方法，其分为两部分。
夹逼
首先我们有
观察下图，可以看到其整体位于
它的构造方法是连接
不难计算出其面积
另一方面，我们又有下图，可以看到其整体位于
它的构造方法是截取
不难计算出其面积
从而有
进而
接下来同阶无穷大有了，我们接下来寻找系数，为此我们先寻找一个阶乘满足的等式。
由点火公式而来的一条等式
点火公式指的就是 $I_k=\displaystyle\int {0}^{\frac{\pi}{2}} \sin ^k x \mathrm{d}x
即
稍加整理得到
夹逼立得：
双阶乘满足：
而我们又有:
故进一步可以整理得到：
让我们把一切综合起来
此处略去计算过程，将
于是
最后再来瞻仰一下 Stirling 公式
全排列的生成算法
生成算法就是用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。 目标是给出排列求序号，给出序号求排列。
!!! note
序号: 比当前排列更早的排列个数，所以从 0 记。在这里有一个叫做 “逆序数” 的概念，它是指数字后比本数位小的数字的个数，这个很重要不能记混了
字典序法
!!! question
求
!!! question
求
| 类型 | ||
|---|---|---|
| … | … | … |
故序号为
将
注意中介数总是比排列少了一位
已知排列求中介数
设排列
!!! question
求
已知中介数求序号
!!! question
已知中介数为
一般的，对于中介数
另一方面这个排列就是
!!! question
求
中介数
!!! question
求
中介数
已知序号求排列
!!! question
已知序号为
逆推，首先除
从中介数
!!! question
已知 1-7 的排列，序号为
确定中介数为
邻位对换法
对每一个
!!! question
求在邻位对换算法下，
首先确定应该移动
关于
相信你也同样觉得这个算法直接求序号很麻烦，所以引入邻位对换法的中介数。
邻位对换法的中介数
对于 839647521 这样一个排列
设定
2 的方向一定是向左。
!!! note
对于每一个大于 2 的数字
如果
如果 i 为偶数，其方向性决定于
当得到方向性后，即可逆取逆序数。如此就能得到邻位对换法的中介数。这不是更麻烦了吗
| 数字 |
方向 | 逆序 |
|---|---|---|
| 2 | 一定向左 | 1 |
| 3 | 3 奇， |
0 |
| 4 | 4 偶， |
1 |
| 5 | 5 奇， |
2 |
| 6 | 6 偶， |
1 |
| 7 | 7 奇， |
3 |
| 8 | 8 偶， |
7 |
| 9 | 9 奇， |
2 |
中介数：10121372
!!! question
求在邻位对换算法下，53627184 的中介数
| 方向 | ||
|---|---|---|
| 2 | 左 | 1（奇） |
| 3 | 右 | 0（偶） |
| 4 | 右 | 3（奇） |
| 5 | 右 | 0（偶） |
| 6 | 右 | 2（偶） |
| 7 | 左 | 2（偶） |
| 8 | 左 | 1（奇） |
得中介数 1030221
已知中介数求排列
从小到大依次插入
!!! question
求在邻位对换算法下，中介数 10121372 对应的排列
| 定向 | 反向逆序数 | ||
|---|---|---|---|
| 2 | 1 | 左 | 83964752x |
| 3 | 0 | 8396475xx | |
| 4 | 1 | 8x96475xx | |
| 5 | 2 | 8x96x75xx | |
| 6 | 1 | 8x96x7xxx | |
| 7 | 3 | 8x9xx7xxx | |
| 8 | 7 | 8x9xxxxxx | |
| 9 | 2 | xx9xxxxxx |
故排列为 839647521
!!! question
求在邻位对换算法下，中介数 1030221 对应的排列
| 定向 | 排列 | ||
|---|---|---|---|
| 2 | 1 | 左 | 53627x84 |
| 3 | 0 | 右 | 536x7x84 |
| 4 | 3 | 右 | 5x6x7x84 |
| 5 | 0 | 右 | 5x6x7x8x |
| 6 | 2 | 右 | xx6x7x8x |
| 7 | 2 | 左 | xxxx7x8x |
| 8 | 1 | 左 | xxxxxx8x |
53627184
已知中介数求序号
列表折线乘
!!! question
求在邻位对换算法下，中介数 10121372 对应的排列序号
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 2 | 1 | 3 | 7 | 2 |
!!! question
求在邻位对换算法下，中介数 1011056 对应的排列序号
| 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 1 | 0 | 5 | 6 |
已知序号求中介数
!!! question
求在邻位对换算法下，排列序号 22222 对应的中介数
22222 / 8 = 2777 余 6
2777 / 7 = 396 余 5
396 / 6 = 66 余 0
66 / 5 = 13 余 1
13 / 4 = 3 余 1
3 / 3 = 1 余 0
1 / 2 = 0 余 1
中介数：1011056
可重组合
使用场景：将若干无区别球放入有区别盒子。
若干条组合恒等式
从
从
，有 种方案 ，有 种方案
由恒等式二易得
个元素取 个元素作为第一集合，剩余 个再选择 个做第二集合
- 先选两个集合全部元素
个，再从中选择 个作为第一集合。
两种选法都无遗漏, 无重复地给出可能的方案，应该相等。
二项式定理展开
-
的所有方案. 每一子集都可取 或不取。这样有 个方案. 另有 。 -
从
走 步有 种走法，都落在直线 上
二项式定理展开
这个等式叫做 Vandermonde 恒等式, 考虑
!!! note “以下内容仅供了解”
1. 李善兰恒等式
2. 若考虑
3. 通过级数展开后比较系数可以得到大量的组合恒等式，我们将在第二章学习相关内容
你学会了吗？
!!! question
某保密装置须同时使用若干把不同的钥匙才能打开。现有７人，每人持若干钥匙。须４人到场，所备钥匙才能开锁。问：
①至少有多少把不同的钥匙？
②每人至少持几把钥匙？
!!! question “一个简单一点的例子”
若４人中３人到场，即可开锁。问：
①至少有多少把不同的钥匙？
②每人至少持几把钥匙？
分析: “至少” 说明每两个人缺一把钥匙。又要三人到场全解锁。所以每个两人组缺的是不同的钥匙，于是建立起钥匙与两人组的一一映射。针对一个人来说，他应有不包含他的两人组缺的钥匙。
!!! question
有 4 个相同质点, 总能量为
1. 若能级为
2. 若能级为
就是阅读理解题
| 能量 | Bose-Einstein 分布 | Fermi-Dirac 分布 |
|---|---|---|
| 0004 | 1·1·1·17 | |
| 0013 | 1·1·2·10 | |
| 0022 | 1·1· |
|
| 0112 | 1· |
1· |
| 1111 |
!!! question
设
n 位长的 0-1 字符串共有 2n 个。但不能每个串都设为码字，否则失去纠错能力。
让我们深入一些
似曾相识又归来 —— 母函数
对于序列
算法它还在追我 —— 递推
!!! question
Hanoi 问题，试用母函数的方法求算法复杂度
显然有递推式
设母函数
!!! question
求 n 位十进制数中出现偶数个 5 的数字的个数
令
- 法 1：有递推式
分别设母函数
- 法 2：有递推式
，后略
!!! question
求斐波那契数列通项公式
!!! warning “下面一例仅供观赏”
求可重组合数
//TODO
母函数的性质
一个序列和它的母函数一一对应。给了序列便得知它的母函数；反之，求得母函数序列也随之而定。为了求满足某种递推关系的序列，关键在于要搭起从序列到母函数，从母函数到序列这两座桥。
性质 1：
$$b_k =\left{
性质 2：
性质 4：
性质 5：
性质 6：
性质 7：$\displaystyle c_n=\sum^{k}{i=0}a_ib{k-i}
线性常系数递推关系的解法
齐次式：
!!! note
定义特征多项式
- 无重根：
- 一般情况：
时
非齐次式：
!!! note
特征多项式：
!!!note
特征多项式有复根的情况：
若特征多项式有一对共轭复根
分拆数
指数型母函数
推论 1：若元素
!!! question
“红鲤鱼与绿鲤鱼” 六个字组成的不同排列总数是多少？
显然是
推论 2：若元素
!!! question
求斐波那契数列通项公式
母函数和递推关系应用举例
!!! question
10 个数字和 4 个四则运算符组成的 14 个元素。求由其中的 n 个元素的排列构成一算术表达式的个数。
递归方程：
特征方程：
解：
通解形式：
!!! question
设有 n 条封闭的曲线，两两相交于两点，任意三条封闭曲线不相交于一点。求这样的 n 条曲线把平面分割成几个部分？
- 打表：2，4，8，14，22 可猜想答案是二阶等差数列
- 欧拉公式：点数 + 域数 - 边数 = 2
实际上满足递归方程：
特征方程：
通解形式：
特解形式：
!!! question
平面上有一点
- hint：讨论
和 的颜色是否相同
满足递推式：
通解形式：
错排问题
先打表 [0, 1, 2, 9, 44, ……]
实质上，我们有这样的递推关系：
这不是我们会解的递推关系，但可以转化求解：
递推立得:
从而可解母函数
总之
Stirling 数
第一类 Stirling 数
第二类 Stirling 数：
Catalan 数
!!! question
求 n 个节点的二叉树个数
有递推关系
!!! question