Epi 的组合数学笔记

、
这是 Epi 的选修课之一，北科的选修课与参考书有部分出入，而本笔记基本上是跟着 ppt 走的。
另外推荐《数学女孩》（一系列数学科普小说）作为参考书，对组合数学的学习很有辅助作用。
虽然这门课没有其他的课程水简单，准备考试的时候有点痛苦，但是这门课真的是我憧憬中大学课的样子，学完了真的收获很多。

!!! note “前言”
组合数学的主要解题方法是计数的合理分类和组合模型的转换，并不高深复杂，但学好绝非易事。
本笔记多以 "问题 —— 方法 —— 结论" 为导向，这也是 Epi 在学这门课时用到的方法，故含有大量的例题，还请注意。

前言 —— 在一切开始之前

本章问题只做引入，不要求掌握

!!! question
请给出 3 - 10 阶幻方的一种构造。

奇数阶幻方有通用构造，而偶数阶幻方没有比较通用的构造方法。

!!! question
有 $1,2,3,4,5,6$ 共 $6$ 个团队，每个团队分别选出 $A,B,C,D,E,F$ 六种军衔的军官各一名，共 $36$ 名军官。
问：能否把这些军官排成 $6 \times 6$ 的方阵，使得每行及每列的 $6$ 名军官均来自不同的团队且具有不同的军衔？
6 阶拉丁方不存在。

!!! question
用三种颜色红、黄、蓝涂染平面正方形的四个顶点，若某种染色方案在正方形旋转某个角度之后与另一个方案重合，则认为这两个方案是相同的。
求：本质上不同的染色方案。
24 种方案，事实上若颜色数为 $n$ , 总方案数为 $f(n) = \displaystyle {\frac{1}{4}(n^4+n^2+2n)}$

!!! question
§ 不同身高的 26 个人随意排成一行。
求证：总能从中挑出 6 个人，让其出列后，他们的身高必然是由低到高或由高到低排列的。

这被叫做拉姆齐数 (Ramsey Number)

在组合数学上，拉姆齐 (Ramsey) 定理是要解决以下的问题：要找这样一个最小的数 $n$ ，使得 $n$ 个人中必定有 $k$ 个人相识或 $l$ 个人互不相识。如 $r(3,3)=6, r(3,4)=9$。

让我们排列组合

加法法则与乘法法则

**【加法法则】** 设事件 A 有 $m$ 种产生方式，事件 B 有 $n$ 种产生方式，则事件 A 或 B 之一有 $m+n$ 种产生方式

**【乘法法则】** 设事件 A 有 $m$ 种产生方式，事件 B 有 $n$ 种产生方式，则事件 A 与 B 有 $m·n$ 种产生方式

!!! question
某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色和条纹都用红、蓝、橙、黄四种颜色。
求：共有几种着色方案？（注意：底色和条纹不可以同色）
显然是 种

!!! question
求小于 $10000$ 的含 $1$ 的正整数的个数

减法原理：当原问题的求解较为复杂时可以考虑求解命题的反面

全部四位数有 $10^4$ 个（包含 0000）, 不含$1$ 的四位数有 $9^4$ 个，含 $1$ 的四位数为两个的差: $10^4－9^4=3439$ 个

!!! question
求小于 $10000$ 的含 $0$ 的正整数的个数
!!! warning
“含 0” 和 “含 1” 不可直接套用。0019 含 1 但不含 0。在组合的习题中有许多类似隐含的规定，要特别留神

不含 0 的 1 位数有 $9^1$ 个，2 位数有 $9^2$ 个，3 位数有$9^3$ 个，4 位数有 $9^4$ 个。$9^1+9^2+9^3+9^4=\displaystyle{\frac{9^5-1}{9-1}}=7380$，从而结果为$9999-7380=2619$ 个。

你好，排列组合

【排列】从 $n$ 个不同的元素中，取 $r$ 个不重复的元素，按次序排列，称为从 $n$ 个中取 $r$ 个的无重排列。排列的全体组成的集合用 $\mathbb{P}(n,r)$ 表示。排列的个数用 $P(n,r)$ 表示。当 $r=n$ 时称为全排列。一般不说可重即无重。可重排列的相应记号为 $\mathbb{\overline{P}}(n,r),\overline{P}(n,r)$。

基于不同语境，组合数有多种表达形式 $P(n,r)=P_{n}^{r} = [n]_{r}$

$$P(n,r)=n(n-1)(n-2) \cdots (n-r+1)$$

【组合】从 $n$ 个不同的元素中，取 $r$ 个不重复的元素，组成一个子集，而不考虑其元素的顺序，称为从 $n$ 个中取 $r$ 个的无重组合。组合的全体组成的集合用 $\mathbb{C}(n,r)$ 表示。组合的个数用 $C(n,r)$ 表示。当 $r=n$ 时称为全排列。一般不说可重即无重。可重组合的相应记号为 $\mathbb{\overline{C}}(n,r),\overline{C}(n,r)$。

基于不同语境，组合数有多种表达形式 $C(n,r)=C_{n}^{r} =\displaystyle{\binom{n}{r}}$

$$C(n,r)=\frac {P(n,r)}{r!}=\frac{n!}{r!(n-r)!}$$

!!! question
求: $x_1+x_2+x_3=100$ 非负整数解的个数

使用隔板法，原问题等同于向 100 个 1 中插入两个隔板的方法数，即$C_{102}^{2}$
推广：$x_1+x_2+\cdots+x_n=m$ 的非负整数解的个数为$\displaystyle {C_{m+n-1}^{n-1}}$

!!! question
§ 有 5 本不同的日文书，7 本不同的英文书，10 本不同的中文书。求：
1) 取 2 本不同文字的书；
2) 取 2 本相同文字的书；
3) 任取两本书

!!! question
若正整数 $n$ 有如下质因数分解：$n={p_1}^{\alpha_1}{p_2}^{\alpha_2}\cdots{p_s}^{\alpha_s}$，求:
1) $n$ 的正因子个数 $\tau(n)$；
2) $n$ 的正因子之和 $\sigma(n)$；
3) $\phi (n)\overset {def}{=}\text {1 至 n 中与 n 互素的数字个数}$

这三个问题都很经典，第三个是大名鼎鼎的欧拉函数。

1. $\tau(n)=\displaystyle{\prod_{i=1}^{s} (1+\alpha_{i})}$
2. $\sigma(n)=\displaystyle{\prod_{i=1}^{s} \frac{p_{i}^{\alpha_{i}+1}-1}{p_{i}-1}}$
3. $\phi(n)=\displaystyle{n\prod_{i=1}^{s}(1-\frac{1}{p_i})}$

!!! question
从 $[1,300]$ 中取 3 个不同的数，使这 3 个数的和能被 3 整除，有多少种方案？

记 $[1,300]$ 模 3 剩余类群为 $A,B,C$,
要满足条件，有四种解法：

1. 3 个数同属于 A;
2. 3 个数同属于 B
3. 3 个数同属于 C;
4. A,B,C 各取一数.
   而前 3 种是对称情况。
   $3C_{100}^{3}+100^3=1485100$

!!! question
某车站有 6 个入口处，每个入口处每次只能进一人，一组 9 个人进站的方案有多少？

!!! warning
人有进入顺序。

隔板法，先做 14 元全排列，再针对入口数降重。$\dfrac{14!}{5!}$
隔板法，先确定位置，在针对人做排列。$C_{14}^{5}\cdot9!$

!!! question
现需用 26 个英文字母构成一个 5 个字符的串 (字母可重复)，满足如下要求的串为合法字符串。
(1). 六个母音字母 a, e, i, o, u, y 不相邻
(2). 其余的 20 个子音字母不能连续 3 相邻
(3). 相邻的子音字母不能相同
问：有多少种不同的合法字符串

这是一个需要耐心分类的问题，不妨记 $\alpha,\beta$ 为母音和子音，则所有的合法串有如下 7 种情况

• $\alpha \beta \alpha \beta \alpha$：$6 \times 20 \times 6 \times 20 \times 6$

• $\alpha \beta \alpha \beta \beta$：$6 \times 20 \times 6 \times 20 \times 19$

• $\alpha \beta \beta \alpha \beta$：$6 \times 20 \times 19 \times 6 \times 20$

• $\beta \alpha \beta \alpha \beta$：$20 \times 6 \times 20 \times 6 \times 20$

• $\beta \alpha \beta \beta \alpha$：$20 \times 6 \times 20 \times 19 \times 6$

• $\beta \beta \alpha \beta \alpha$：$20 \times 19 \times 6 \times 20 \times 6$

• $\beta \beta \alpha \beta \beta$：$20 \times 19 \times 6 \times 20 \times 19$

共计 $2335200$ 种。

!!! question
2000 到 7000 之间的偶数，有几个是由不同数字组成的？

• 千位为偶数 (2,4,6)：$3 \times 4 \times 8 \times 7 = 672$

• 千位为奇数 (3,5)：$2 \times 5 \times 8 \times 7 = 560$

共计 $1352$ 种。

!!! question
5 女生 7 男生要组成一个 5 人小组，其中小组中不允许男生甲和女生乙同时参加
问：不同小组方案数？

减法原理，$C_{12}^{5}-C_{10}^{3}=672$

Stirling 近似公式

Stirling 近似给出了 $n!$ 的近似公式

$$n! \sim \sqrt{2 \pi n} \left( \dfrac{n}{e} \right) ^n$$

下面给出一种证明方法，其分为两部分。

夹逼 $\Large{\ln x}$ 的面积

首先我们有$\displaystyle \int_{1}^{n} \ln x \mathrm{d}x = n \ln n -n+1$，记作 $A_n$，即

$$A_n = n \ln n -n+1$$

观察下图，可以看到其整体位于 $y=\ln x$ 的曲线下方。

它的构造方法是连接 $(1,0),(2, \ln2),\cdots,(n,\ln n)$ 得到的。

不难计算出其面积 $t_n = \ln2 + \ln3 + \cdots + \ln (n-1)+ \dfrac{1}{2}\ln n$，稍加整理有

$$t_n=\ln n! - \dfrac{1}{2}\ln n$$

另一方面，我们又有下图，可以看到其整体位于 $y=\ln x$ 的曲线上方。

它的构造方法是截取 $y=\ln x$ 的部分切线构造的，特别的在$x = n$ 处不取切线。

不难计算出其面积

$$T_n = \dfrac{1}{8} + \ln2 + \ln3 + \cdots + \ln (n-1)+ \dfrac{1}{2}\ln n$$

从而有 $t_n < A_n < T_n$，进而$0<A_{n}-t_{n}<T_{n}-t_{n}=\dfrac{1}{8}$

进而 $A_{n}-t_{n}$ 单调增且有上界，极限存在，不妨记极限为 $b$。

$$\begin{align} b &= \lim_{n\rightarrow \infty} \left(n \ln n - n+1 -ln n! +\dfrac {1}{2} \ln n \right) \\\\ \ln n! &= n \ln n-n+1-b_n+\dfrac{1}{2}\ln n \\\\ n! &= \left( \dfrac{n}{e}\right)^n e^{1-b_n} \sqrt{n} \\\\ \lim_{n \rightarrow \infty} \dfrac{n!}{\left( \dfrac {n}{e}\right)^n \sqrt{n}} &=\lim_{n \rightarrow \infty}e^{1-b_n} \\\\ \color{red}{\lim_{n \rightarrow \infty} \dfrac{n!}{\left( \dfrac {n}{e}\right)^n \sqrt{n}}} &=\color{red}{ e^{1-b}} \end {align}$$

接下来同阶无穷大有了，我们接下来寻找系数，为此我们先寻找一个阶乘满足的等式。

由点火公式而来的一条等式

点火公式指的就是$I_k=\displaystyle\int _{0}^{\frac{\pi}{2}} \sin ^k x \mathrm{d}x$ 满足的递推关系：$I_k = \dfrac{k-1}{k}I_{k-2}$，从而有：

$$I_{2n} = \dfrac{(2n-1)!!}{(2n)!!} \dfrac{\pi}{2} \\\\ I_{2n-1} = \dfrac{(2n-2)!!}{(2n-1)!!}$$

显然我们有 $I_{2n+1}<I_{2n}<I_{2n-1}$

即$\dfrac{(2n)!!}{(2n+1)!!}<\dfrac{(2n-1)!!}{(2n)!!} \dfrac{\pi}{2} < \dfrac{(2n-2)!!}{(2n-1)!!}$

稍加整理得到$1< \dfrac{\left[(2n-1)!!\right]^2}{\left[(2n)!!\right]^2 \dfrac{1}{2n+1}} \dfrac {\pi}{2}< \dfrac{2n+1}{2n}$

夹逼立得：

$$\lim_{n \rightarrow \infty}\dfrac{\left[(2n-1)!!\right]^2}{\left[(2n)!!\right]^2 \dfrac{1}{2n+1}} \dfrac {\pi}{2}=1$$

双阶乘满足：$(2n)!! \cdot (2n-1)!! = (2n)!$

而我们又有: $(2n)!! = 2^n \cdot n!$

故进一步可以整理得到：

$$\lim_{n \rightarrow \infty} \dfrac{2^{4n}\left[n!\right]^4}{\left[(2n)!\right]^2} \dfrac{1}{2n+1}=\dfrac{\pi}{2}$$

让我们把一切综合起来

此处略去计算过程，将 $n! = \left( \dfrac{n}{e}\right)^n e^{1-b_n} \sqrt{n}$ 带入得到的等式，可以化简得到$\displaystyle \lim_{n \rightarrow \infty} \dfrac{2^{4n}\left[n!\right]^4}{\left[(2n)!\right]^2} \dfrac{1}{2n+1}= \lim_{n \rightarrow \infty}\dfrac{n}{4n+2}\dfrac{[e^{1-b_n}]^4}{[e^{1-b_{2n}}]^2} = \dfrac{1}{4}[e^{1-b}]^2 = \dfrac{\pi}{2}$

于是 $e^{1-b} = \sqrt{2\pi}$ ，证毕！

最后再来瞻仰一下 Stirling 公式

$$n! \sim \sqrt{2 \pi n} \left( \dfrac{n}{e} \right) ^n$$

全排列的生成算法

生成算法就是用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。 目标是给出排列求序号，给出序号求排列。

!!! note
序号：比当前排列更早的排列个数，所以从 0 记。在这里有一个叫做 “逆序数” 的概念，它是指数字后比本数位小的数字的个数，这个很重要不能记混了

字典序法

!!! question
求 $839647521$ 的下一个排列

$839651247$

!!! question
求 $839647521$ 的 (字典序) 序号

类型	$x$ 的取值	$y$ 排列数
$xyyyyyyyy$	$1,2,3,4,5,6,7$	$8!$
$8xyyyyyyy$	$1,2$	$7!$
$83xyyyyyy$	$1,2,4,5,6,7$	$6!$
…	…	…

故序号为 $7\times 8! + 2 \times 7! + 6 \times 6! + 4 \times 5! + 2\times 4!+ 3 \times 3! + 2 \times 2! +1 \times 1!$

将 $8!,7!,…,1!$ 前面的系数抽出，放在一起，得到 $72642321$ ，它是计算排列 $839647521$ 的序号的中间环节，我们称之为中介数

注意中介数总是比排列少了一位

已知排列求中介数

设排列$P_1,P_2,\cdots,P_n$，中介数为$a_{n-1},\cdots,a_{2},a_{1}$

$a_{n-k}$ 是 $P_k$ 之后比 $P_k$ 小的数字个数，类似线代中的逆序数。

!!! question
求 $758632914$ 的 (字典序) 中介数

$64542120$

已知中介数求序号

!!! question
已知中介数为 $(n-1,n-2,\cdots, 3,2,1)$，求序号

一般的，对于中介数 $(a_{n-1},\cdots,a_2,a_1)$，其序号为 $\displaystyle \sum_{k=1}^{n-1} a_kk!$，故磁体序号为$\displaystyle \sum_{k=1}^{n-1} k\cdot k!$

另一方面这个排列就是 $(n,n-1,\cdots,3,2,1)$ 故序号为 $n!-1$

!!! question
求 $758632914$ 的 (字典序) 序号

中介数 $64542120$ ，序号为$6 \times 8!+ \cdots + 0 \times 1!= 205738$

!!! question
求 $369174285$ 序号

中介数 $24603101$，序号为$2 \times 8!+ \cdots + 1 \times 1! = 105199$

已知序号求排列

!!! question
已知序号为 $187524$ ，求排列

逆推，首先除 $8!$ 确定首位，进而一步步推出中介数：

$$\begin{aligned} 187524 &= 8! \times 4 + 26244 \\\\ 26244 &= 7! \times 5 + 1044 \\\\ 1044 &= 6! \times 1 + 324 \\\\ 324 &= 5! \times 2 + 84 \\\\ 84 &= 4! \times 3 + 12 \\\\ 12 &= 3! \times 2 + 0 \\\\ \end{aligned}$$

从中介数 $45123200$ 可以从最高位逐位推出排列为 $572486139$

!!! question
已知 1-7 的排列，序号为 $4000$ ，求排列

确定中介数为 $531220$，答案为 $6425713$

邻位对换法

对每一个 $n-1$ 位偶排列，从右到左插入 $n$ 个空档 (包括两端)，奇排列反之。如此得到 $n$ 位的排列

!!! question
求在邻位对换算法下，$839647521$ 的下一个排列

首先确定应该移动 $9$ ，然后看剩余的数是奇排列还是偶排列，$\dot 8364 \dot 75\dot 21$，奇排列，故向右移动，下一个排列是 $836947521$。

关于 $\dot 8364 \dot 75\dot 21$ 的说明：上方加点代表这个数的逆序数是奇数。

相信你也同样觉得这个算法直接求序号很麻烦，所以引入邻位对换法的中介数。

邻位对换法的中介数

对于 839647521 这样一个排列
设定 $b_2b_3b_4b_5b_6b_7b_8$ 为我们要求的中介数。
2 的方向一定是向左。$b_2$ 就是从 2 开始，背向 2 的方向所有比 2 小的数字的个数（逆取逆序数）

!!! note
$b_i$ 的递推规则如下：
对于每一个大于 2 的数字 $i$ ：
如果$i$ 为奇数，其方向性决定于$b_{i-1}$的奇偶性，奇向右、偶向左。
如果 i 为偶数，其方向性决定于 $b_{i-1}+b_{i-2}$ 的奇偶性，同样是奇向右、偶向左。

当得到方向性后，即可逆取逆序数。如此就能得到邻位对换法的中介数。这不是更麻烦了吗

数字 $i$	方向	逆序 $b_{i}$
2	一定向左	1
3	3 奇，$b_2$ 奇，向右	0
4	4 偶，$b_2+b_3$奇，向右	1
5	5 奇，$b_4$奇，向右	2
6	6 偶，$b_4+b_5$奇，向右	1
7	7 奇，$b_6$奇，向右	3
8	8 偶，$b_6+b_7$偶，向左	7
9	9 奇，$b_8$奇，向右	2

中介数：10121372

!!! question
求在邻位对换算法下，53627184 的中介数

$i$	方向	$b_i$
2	左	1（奇）
3	右	0（偶）
4	右	3（奇）
5	右	0（偶）
6	右	2（偶）
7	左	2（偶）
8	左	1（奇）

得中介数 1030221

已知中介数求排列

从小到大依次插入

!!! question
求在邻位对换算法下，中介数 10121372 对应的排列

$i$	$b_i$	定向	反向逆序数
2	1	左	83964752x
3	0	$b_2 奇$，右	8396475xx
4	1	$b_2+b_3$奇数，右	8x96475xx
5	2	$b_4$奇，右	8x96x75xx
6	1	$b_4+b_5$奇，右	8x96x7xxx
7	3	$b_6$奇，右	8x9xx7xxx
8	7	$b_6+b_7$偶，左	8x9xxxxxx
9	2	$b_8$奇，右	xx9xxxxxx

故排列为 839647521

!!! question
求在邻位对换算法下，中介数 1030221 对应的排列

$i$	$b_i$	定向	排列
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

$1\times3+0)\times4+1)\times5+2)\cdots)\times 9 +2=203393$

!!! question
求在邻位对换算法下，中介数 1011056 对应的排列序号

2	3	4	5	6	7	8
1	0	1	1	0	5	6

$1\times3+0)\times4+1)\times5+1)\cdots)\times 8+6=22222$

已知序号求中介数

!!! 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

可重组合

$\bar C_n^r=C_{n+r-1}^r$

使用场景：将若干无区别球放入有区别盒子。

若干条组合恒等式

$$C_n^r = C_n^{n-r}$$

从$[1,n]$ 去掉一个$r$ 子集，剩下一个$(n-r)$ 子集。由此建立一一对应

$$C_n^{r}=C_{n-1}^r+C_{n-1}^{r-1}$$

从$[1,n]$ 取$a_1,a_2,…,a_r$。设$1≤a_1＜a_2＜\cdots＜a_r≤n$, 对取法分类：

• $a_1=1$，有 $C(n-1,r-1)$ 种方案
• $a_1>1$，有 $C(n-1,r)$ 种方案

$$\binom{n}{n}+\binom{n+1}{n}+\cdots+\binom{n+r}{n}=\binom{n+r+1}{n+1}$$

由恒等式二易得

$$C_n^rC_{n-r}^{l-r} = C_n^lC_l^r$$

• $n$ 个元素取 $r$ 个元素作为第一集合，剩余 $n-r$ 个再选择 $l-r$ 个做第二集合

• 先选两个集合全部元素 $l$ 个，再从中选择 $r$ 个作为第一集合。

两种选法都无遗漏，无重复地给出可能的方案，应该相等。

$$\binom{m}{0}+\binom{m}{1}+\cdots+\binom{m}{m}=2^m$$

二项式定理展开 $(1+1)^m$ 立得，下给出两组合意义。

• $[1,m]$ 的所有方案。每一子集都可取 $k$ 或不取。这样有 $2^m$ 个方案。另有$0 - 子集 (空集),1 - 子集，…,m - 子集$。

• 从 $(0,0)$ 走 $m$ 步有 $2^m$ 种走法，都落在直线 $x+y=m$ 上

$$\sum_{k 奇} C_m^{k}=\sum_{k 偶} C_m^k=2^{m-1}$$

二项式定理展开 $(1-1)^m$ 立得

$$C_{m+n}^r=\sum_{i=0}^{m}C_m^{r-i}C_n^i$$

这个等式叫做 Vandermonde 恒等式，考虑$(0,0)$ 到 $(m+n-r,r)$ 点的路径 = $(0,0)$ 到$(m-r+i,r-i)$ 到$(m+n-r,r)$ 可证

!!! note “以下内容仅供了解”
1. 李善兰恒等式

2. 若考虑 $\alpha= \sum C_m^{3k}, \beta = \sum C_m^{3k+1},\gamma = \sum C_m^{3k+2}$，它们与$\dfrac{1}{3}2^m$ 十分相近，但不相等。
3. 通过级数展开后比较系数可以得到大量的组合恒等式，我们将在第二章学习相关内容

你学会了吗？

!!! question
某保密装置须同时使用若干把不同的钥匙才能打开。现有７人，每人持若干钥匙。须４人到场，所备钥匙才能开锁。问：
①至少有多少把不同的钥匙？
②每人至少持几把钥匙？

$C_7^3 =35$
$C_6^3=20$

!!! question “一个简单一点的例子”
若４人中３人到场，即可开锁。问：
①至少有多少把不同的钥匙？
②每人至少持几把钥匙？

分析: “至少” 说明每两个人缺一把钥匙。又要三人到场全解锁。所以每个两人组缺的是不同的钥匙，于是建立起钥匙与两人组的一一映射。针对一个人来说，他应有不包含他的两人组缺的钥匙。
$C_4^2,C_3^2$

!!! question
有 4 个相同质点，总能量为$4E_0$。每个质点所具能量为$kE_0$,$k=0,1,2,3,4$。
1. 若能级为 $kE_0$ 的质点可有 $k+1$ 种状态，而且服从 Bose-Einstein 分布，即同能级的质点可以处于相同的状态，问系统有几种不同的状态？（或图像）
2. 若能级为 $kE_0$ 的质点可有 $2(k+1)$ 种状态，而且服从 Fermi-Dirac 分布，即不允许同能级的两个质点有相同状态，问系统有几种不同状态？（或图像）

就是阅读理解题

能量	Bose-Einstein 分布	Fermi-Dirac 分布
0004	1·1·1·17	$C_2^3$·34
0013	1·1·2·10	$C_2^2$·4·20
0022	1·1·$\overline{C_5^2}=C_6^2$	$C_2^2,C_{10}^2$
0112	1·$\overline{C_2^2}=C_3^2$·5	1·$C_4^2$·10
1111	$\overline{C_2^4}=C_5^1$	$C_4^4$

!!! question
设 $n$ 位长能纠 $r$ 个错的码字的个数为 $M$ ，则

n 位长的 0-1 字符串共有 2n 个。但不能每个串都设为码字，否则失去纠错能力。

让我们深入一些

似曾相识又归来 —— 母函数

对于序列 ${a_n}$， $G(x)=\sum a_nx^n$

算法它还在追我 —— 递推

!!! question
Hanoi 问题，试用母函数的方法求算法复杂度

显然有递推式 $h(n)=2h(n-1)+1$

设母函数 $H(x)=h(1)x+h(2)x^2+\cdots$

$$\begin{aligned} (1-2x)H(x)&=x+x^2+\cdots \\\\ &=\dfrac{x}{1-x} \\\\ H(x)&=\frac{x}{(1-x)(1-2x)} \\\\ &= \frac{1}{1-2x} -\frac{1}{1-x} \\\\ &= \sum(2^k-1)x^k \end{aligned}$$

!!! question
求 n 位十进制数中出现偶数个 5 的数字的个数

令 $a_n$ 为 n 位十进制数中出现偶数个 5 的数字的个数，$b_n$为 n 位十进制数中出现奇数个 5 的数字的个数

$p_1p_2\cdots p_{n-1} \rightarrow p_1p_2 \cdots p_n$

• 法 1：有递推式 $a_n=9a_{n-1}+b_{n-1},b_n=9b_{n-1}+a_{n-1}$

分别设母函数 $A(x),B(x)$ 则有 $A(x)-9xA(x)-xB(x)=8, B(x)-9xB(x)-xA(x)=1$

$$\begin{aligned} A(x)= \frac{-71x+8}{(1-8x)(1-10x)} = \frac{1}{2}(\frac{7}{1-8x}+\frac{9}{1-10x})=\frac{1}{2}\sum (7\cdot 8^k+9 \cdot 10^k)x^k\\ \end{aligned}$$

• 法 2：有递推式 $a_n=9a_{n-1}+(9 \times 10^{n-2}-a_{n-1})$，后略

!!! question
求斐波那契数列通项公式

$F_n=F_{n-1}+F_{n-2}$，设母函数 $G(x)$

$$(1-x-x^2)G(x)=x \\\\ G(x)=\frac{x}{1-x-x^2} =\frac{1}{\sqrt{5}}$$

!!! warning “下面一例仅供观赏”
求可重组合数 $\bar C(n,r)$
//TODO

母函数的性质

一个序列和它的母函数一一对应。给了序列便得知它的母函数；反之，求得母函数序列也随之而定。为了求满足某种递推关系的序列，关键在于要搭起从序列到母函数，从母函数到序列这两座桥。

性质 1：

b_k =\left\{ \right.$$ ，则 性质 2： ，则 性质 3：，则 性质 4：，则 性质 5： ，则 性质 6： ，则 性质 7：，则 ### 线性常系数递推关系的解法 齐次式： !!! note 定义特征多项式 - 无重根： - 一般情况：时

a_n=\sum(b_{i0}+b_{i1}n+\cdots+b_{i,k_i-1}n^{k_i-1})\alpha_i^n

非齐次式： !!! note 特征多项式：的通解结构为

a_n^*=(d_0+d_1n+\cdots+d_rn^r) n^s\alpha^n \ (\alpha \text {是} s\text {重根})

!!!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 数： 个有区别的球放到 个相同的盒子，要求无空盒子，其不同的方案数 成为第二类 Stirling 数 ### Catalan 数 !!! question 求 n 个节点的二叉树个数 有递推关系，不难看出 !!! question