组合数学笔记

2023 春组合数学笔记，全部资料参见我的 Github Click here to see the remote repository)

总思路：存在 $\rightarrow$ 计数 $\rightarrow$ 算法 $\rightarrow$ 优化

TimeLine

Created: 2023.05.09

Maximum change: 2023.06.09

Finish: 2023.06.13

第1章引论

例1：幻方

$2$ 阶幻方不存在，对于任意 $n > 3 $ 的整数 $n$，都存在一个 $n$ 阶幻方

例2：$36$ 军官问题

例3：完美覆盖问题

一般化：

$ m n $ 棋盘被 $b$ - 牌完美覆盖，当且仅当 $b$ 是 $m$ 或 $n$ 的一个因子

延伸问题：断层线 (Fault Line)

$4 \times 4$ 棋盘用 $8$ 张多米诺牌完美覆盖，证明：总可以将这个棋盘横向或纵向分成非空两个部分，且没有牌被切断

例4：相互重叠的圆（递推公式）

设这 $h_n$ 个圆将平面分为 $m$ 个区域，当加入第 $n$ 个圆时，这个圆与前面 $n-1$ 个圆交于 $2(n-1)$ 个点，这 $2(n-1)$ 个点把第 $n$ 个圆分成 $2(n-1)$ 条弧，每条弧将其经过的区域分成 $2$ 个区域（在前面的 $n-1$ 个圆分成的区域中），故新加入的第 $n$ 个圆使区域数增加了 $2(n-1)$

建立递推关系如下： \[ h_n = h_{n-1} + 2(n-1) (n \geq 2) \\ h_1 = 2 \]

解决问题的一般顺序：求通项 $\rightarrow$ 求递推公式 $\rightarrow$ 诉诸生成函数

例5：$Nim$ 取子游戏

有 $k(\geq 1)$ 堆石子，分别含有 $n_1,n_2,\dots, n_k$ 个子

游戏规则:

游戏人 $A$ 和 $B$ 交替从这些堆里取一定数量石子
取子时，只能选择其中一堆，并且取至少一个石子
最后取完子的人为胜者

定义：$n_1, n_2, \dots, n_k$ 是正整数，若它们的二进制数码的异或值为 $0$，则称它们处于平衡状态，否则处于非平衡状态

结论：$A$ 能在非平衡的 $Nim$ 取子中获胜，而 $B$ 能在平衡的 $Nim$ 取子中获胜

第2章排列与组合

2.1：4个基本的计数原理

加法原理、乘法原理、减法原理、除法原理
- 例：确定数 $3^4 \times 5^2 \times 11^7 \times 13^8$ 的正整数因子的个数（注意每个因子取 $0$ 次！！！因为 $1$ 也是因子）
- 解：由乘法原理，$5 \times 3 \times 8 \times 9$

2.2：集合的排列

从 $n$ 个不同元素取出 $r$ 个元素有序摆放，称 $n$ 元素集合的 $r$ - 排列。用 $P(n, r)$ 表示 $n$ 元素集合的全部 $r$ - 排列数。
全排列：列出全部元素的排列
$P(n, r) = \dfrac{n!}{(n-r)!}$
分步递推：$P(n, r)=n \times P(n-1,r-1)$
- 选择 $1$ 号盒子，放入 $1$ 个乒乓球
- 从 $n-1$ 个球中选出 $r-1$ 个放入 $r-1$ 个盒子排列
分类递推：$P(n, r)=P(n-1,r)+rP(n-1,r-1)$
- 不选第 $1$ 个球
- 选择第 $1$ 个球
循环排列：只考虑元素间的相对顺序
定理2.2.2： $n$ 个元素集合的循环 $r$ 排列个数为： \[ \dfrac{P(n, r)}{r} \]
- 例：$10$ 个人围坐圆桌，$2$ 人不彼此相邻，求总排列方法数
- $(10 - 1)! - 2 \times (9 - 1)!$
- 先固定一个人 $P_1$，然后 $P_2$ 可选位置为 $7$，余下 $8$ 人任意坐，共 $7 \times 8!$
若是项链排列，为上式除以 $2$，考虑正反翻转 $2$ 种情况

2.3：集合的组合

从 $n$ 个元素中无序地取出 $r$ 个元素，称 $n$ 元素集合的 $r$ - 组合。用 $\left( \begin{matrix} n \\ r \end{matrix}\right)$ 表示 $n$ 元素集合的全部 $r$ - 组合数。
约定：
- $\left( \begin{matrix}0\\0\end{matrix}\right)=1$
- 当 $r > n$ 时，$\left( \begin{matrix}n\\r\end{matrix}\right)=1$
  
  选择的个数多于总个数时计数为 $0$
选班委公式：$C(n,r)C(r,k)=C(n,k)C(n-k, r-k)$。
- 选出 $r$ 个班委、$k$ 个常委
- 先选出 $k$ 个常委，再选出 $r-k$ 个其他班委
定理2.3.3（Pascal公式）：对于满足 $1 \le k \le n - 1$ 的整数 $k$ 和 $n$，有
- \[ \left( \begin{matrix}n\\k\end{matrix}\right) = \left( \begin{matrix}n - 1\\k\end{matrix}\right) + \left( \begin{matrix}n - 1\\k - 1\end{matrix}\right) \]
- 组合证明：
- 不包含某个元素 $x$ 的 $k$ 子集 $\left( \begin{matrix}n-1\\k\end{matrix}\right)$ 个
- 包含这个元素 $x$ 的 $k$ 子集 $\left( \begin{matrix}n-1\\k-1\end{matrix}\right)$ 个
公式：$\left( \begin{matrix}n\\0\end{matrix}\right)+\left( \begin{matrix}n\\1\end{matrix}\right)+\left( \begin{matrix}n\\2\end{matrix}\right)+...+\left( \begin{matrix}n\\n\end{matrix}\right)=2^n$ （用子集数量组合计数证明）

2.4：多重集的排列

主要分无限重复和有限重复

定义：$M = \{a,a,b,c,c,c\} = \{2 \cdot a, 1 \cdot b, 3 \cdot c\}$，称 $2, 1, 3$ 是重复集的重数
- 允许元素重复
- 允许无限重数
定理2.4.2：令 $S$ 是多重集，它有 $k$ 种不同的元素，每种元素的重复数分别为 $n_1，n_2，…，n_k$，那么，$S$ 的排列数等于 \[ \dfrac{n!}{n_1!n_2!...n_k!} \]
- 证明：依次摆放，约去多余项
- 例如：数字 $1,1,1, 3, 8$ 可以构造出多少个不同的 $5$ 位数？即
\[ \dfrac{5!}{3!1!1!}=20 \]
定理2.4.3：设 $n = n_1 + n_2 + \dots + n_k$，将 $n$ 个元素集合划分为做了标签的 $k$ 个盒子 $B_1, B_2, \dots ,B_k$，其中 $B_i$ 盒子含有 $n_i$ 个元素，方法数为 \[ \dfrac{n!}{n_1!n_2! \dots n_k!} \] 若盒子无标号且 $n_1 = n_2 = \dots = n_k$，则划分数为 \[ \dfrac{n!}{k!n_1!n_2! \dots n_k!} \]

多重集的另一种解释：集合划分

如果不是所有的划分数都相等，就需要相同个数的划分去重
- 例：将 $7$ 个不同颜色的球放入 $3$ 个无区别的盒子中，要求每盒球数目不少于 $2$，求解放置方案数。
- 解：放置方法必为 $223$，故方案数为（第一个 $2!$ 为划分去重） \[ \dfrac{7!}{2!2!2!3!} = 105 \]
定理2.4.4（非攻击性车摆放）：有 $n$ 个车共 $k$ 种颜色，其中第一种颜色的车有 $n_1$ 个，第二种颜色的车有 $n_2$ 个，$\dots$，第 $k$ 种颜色的车有 $n_k$ 个，那么，把这些车放到 $n \times n$ 的棋盘上，使得没有车能相互攻击的摆放方法数为： \[ \dfrac{n!}{n_1!n_2!...n_k!}\cdot n! = \dfrac{(n!)^2}{n_1!n_2!...n_k!} \]
- 例如：当 $8$ 个车，$1$ 个红车，$3$ 个蓝车和 $4$ 个黄车。非攻击车摆放的方法数：
\[ 8! \times \dfrac{8!}{1!3!4!} = \dfrac{(8!)^2}{3!4!} \]

先排车，再给车排颜色

2.5：多重集的组合

相当于将 $r$ 个相同元素分成 $k$ 个不同区域，每个区域对应一种元素——隔板法

多重集组合 $\Leftrightarrow$ 不定方程解集 $\Leftrightarrow$ 多重集排列

多重集 $S$ 的 $r$ - 组合数等于多重集 $T$ 的排列数

定理2.5.1：令 $S$ 是多重集，它有 $k$ 个不同的元素，每个元素都有无限重复次数，那么，$S$ 的 $r$ - 组合个数为： \[ \left( \begin{matrix} r+k-1 \\ r \end{matrix} \right) = \left( \begin{matrix} r+k-1 \\ k-1 \end{matrix} \right) \]
- 例：令 $S＝\{12 \cdot a, 12\cdot b, 12\cdot c\}$，求 $S$ 的 $12$ - 组合个数： \[ \left( \begin{matrix} 12+3-1 \\ 12 \end{matrix} \right)=\dfrac{14!}{12!2!} \]
- 例：方程 $x_1+x_2+x_3+x_4=20$ 的整数解的个数是多少？其中 $x_1\geq 3, x_2\geq 1, x_3\geq 0, x_4\geq 5$
  
  作变量代换：$y_1=x_1-3， y_2=x_2-1， y_3=x_3，y_4=x_4-5$，那么，得到方程：$ y_1+y_2+y_3+y_4=11$ \[ \left( \begin{matrix} 11+4-1 \\ 11 \end{matrix} \right)= \left( \begin{matrix} 14 \\ 11 \end{matrix} \right) \]
- 例（出现次数下界约束）：令 $S＝{12 \cdot a, 12 \cdot b, 12 \cdot c }$。求 $S$ 的使得 $3$ 个元素都至少出现一次的 $12$ - 组合个数。
  - 令 $y_i = x_i - 1$，求非负整数解，套用公式
- 上界约束：用其他方法做就行，不必拘泥这一章知识

2.x：其它，一些题目

把 $2n$ 个人分成 $n$ 组，每组 $2$ 人，有多少分法？

等价为分组问题，相当于将 $2n$ 个不同球投入 $n $ 个相同的盒子中，每个盒子 $2$ 个。【有点像定理2.4.2除以 $n!$ 的变体】 \[ \dfrac{2n!}{(2!)^n \cdot n!}=\dfrac{2n!}{2^n \cdot n!} \]
不相邻选取问题：从 $\{1, 2, \dots, n\}$ 中取出 $r$ 个不相邻的数，这样的组合有多少种？

$\left( \begin{matrix} n-r+1 \\ r \end{matrix} \right)$ 种，相当于往 $n-r $ 个数的 $n-r+1$ 个间隔里插入 $r$ 个被选取的数作为“隔板”

第3章鸽巢原理

证明存在性的一种主要手段

3.1 鸽巢原理的简单形式

例：证明，如果从 ${1, 2, …, 2n}$ 中任意选择 $n+1$ 个不同的整数，那么一定存在两个整数，它们之间差为 $ 1$。

将集合 $\{1, 2, \dots ,2n\}$ 划分成 $n$ 个子集 $S_1, S_2, \dots , S_n$，其中 $S_n = \{2i-1, 2i\}, i = 1, 2, \dots ,n$

设选择的 $n+1$ 个整数为 $ a_1< a_2 <…<a_{n+1}$。令 $b_1=a_1+1, b_2=a_2+1, …, b_{n+1} = a_{n+1} +1$。此 $ 2n+2$ 个数中至少有一对数相等，由于 $a_1, \dots, a_n$ 互不相等，且 $b_1, \dots ,b_n$ 互不相等。因此存在一对 $b_j = a_j + 1$ 与 $a_k$ 相等 $(j \ne k)$
- 扩展：从 $1,2, \dots, kn$ 中任意选择 $n+1$ 个，则存在差为 $k-1$
例：证明，在 $m$ 个正整数 $a_1, a_2, …, a_m$ 中，存在 $0\leq k< l \leq m$，使得 $a_{k+1}+ a_{k+2}+ …+a_l$ 能够被 $m$ 整除。

证：考虑 $m$ 个和（$s_m$ 是正整数的前 $n$ 项和）： \[ s_1=a_1, s_2=a_1+a_2, s_3=a_1+a_2+a_3, …, s_m=a_1+a_2+…+a_m \]
- 若以上和中有一个能被 $m$ 整除，则结论成立；
  
  这是从头开始的部分和
- 否则设 $r_1, r_2, \dots ,r_n$ 为 $s_1, s_2, \dots ,s_n$ 除以 $m$ 的非零余数，则 $1 \leq r_i \leq m-1, i = 1, \dots ,m$。由鸽巢原理，存在 $r_l = r_k, l > k$，则 $a_{k+1} + a_{k+2} + \dots + a_l$ 能被 $m$ 整除
  
  这是从中间开始的部分和
例：从整数 $1, 2, …，200$ 中选取 $101$ 个整数。证明所选的数中存在两个整数，使得其中一个是另一个的因子。

证：对于 $1$ 到 $200$ 间的整数 $n$，$n$ 可写作以下形式：$n=2^k \times a$（其中 $a$ 是 $1, 2, …, 200$ 内的奇数）

由于要选取 $101$ 个整数，而 $200$ 内只有 $100$ 个奇数，由鸽巢原理知必存在两个整数 $n_1$ 与 $n_2$ 写作上式形式后，两数中的奇数因子相等，均为 $b$。假设 $n_1=2^{k1} \times b, n_2=2^{k2} \times b$，其中 $b$ 是 $1, 2, …, 200$ 内的奇数。显然，当 $k_1 \geq k_2$ 时，$n_2$ 整除 $n_1$；否则 $n_1$ 整除 $n_2$。
例：某厂在五年期间的每一个月里至少试制一种新产品，每年最多试制 $19$ 种新产品。试证明：一定存在连续几个月，恰好试制 $24$ 种新产品。

证：设五年间每个月新产品数分别为 $a_1, a_2, \dots , a_{59}, a_{60}$。构造出数列 $a_n$ 的前 $n$ 项和的数列 $s_1, s_2, \dots , s_{59}, s_{60}$，则有： \[ 1≤a_1=s_1<s_2<…<s_{59}<s_{60} \leq 19 \times 5=95 \] 而序列 $s_1+24, s_2+24, \dots , s\_{59}+24, s_{60}+24$ 也是一个严格递增序列： \[ 25≤s_1+24<s_2+24< \dots <s_{59}+24<s-{60}+24 ≤95+24=119 \] 这 $120$ 个数都在区间 $[1,119]$ 内，根据鸽巢原理，必定存在两个数相等

由于 $s_1, s_2, \dots, s_{60}$ 与 $s_1 + 24, s_2 + 24, \dots, s_{60} + 24$ 均为严格单调的，因此必然存在一个 $i$ 和 $j$，使得 $s_i = s_j + 24$ ，因此在第 $j+1$ 个月到第 $i$ 个月的几个月时间里恰好试制了 $24$ 种新产品（解释含义）

几何问题：

例：确定一个整数 $n_k$，使得如果在边长为 $1$ 的等边三角形中任意选择 $n_k$ 个点，一定存在 $2$ 个点，其距离至多为 $\dfrac{1}{k}$
- 解：$n_k = k^2 + 1$
- 证：将每边均分为 $k$ 份，共有 $k^2$ 个区域，落在任意一个部分中的两点之间的距离至多为 $\dfrac{1}{k}$，由鸽巢原理知 $n_k = k^2 + 1$
例（一道数值计算题，比较暴力，估计不会考）：在直径为 $5$ 的圆内任意给定 $10$ 个点，证明存在两点距离小于 $2$
- 证：
例：将一个矩形分成 $4$ 行 $19$ 列的网格，每个单元格涂 $3$ 种颜色当中的 $1$ 种颜色，证明：无论怎样涂色，必有一个由单元格构成的矩形的 $4$ 个角上的格子颜色相同
- 思路：两次鸽巢原理
- 每一列 $4$ 行但只有 $3$ 个颜色，由鸽巢原理，必有两个单元格颜色相同，其位置组合共 $\left( \begin{matrix} 4 \\ 2 \end{matrix} \right) = 6$ 种，$3$ 种颜色下共 $18$ 种，由鸽巢原理，得证
例：证明在 $n+2$ 个任选的正整数中，存在两个数，或者其差能被 $2n$ 整除，或者其和能被 $2n$ 整除。

证明：已知所有正整数除以 $2n$ 的余数只能取值 $0, 1, 2, …, 2n-1$。

把以上余数构造以下 $n+1$ 个子集：$\{1, 2n-1\}, \{2, 2n-2\}, …, \{n-1, n+1\}, \{n, n\}, \{0, 0\}$。

任选 $n+2$ 个正整数，由鸽巢原理知，一定存在两个数，其除以 $2n$ 的余数来自同一个子集 $A$。
- 若 $A$ 是前 $n-2$ 个子集中一个，则这两个数的和能被 $2n$ 整除；
- 若 $A$ 是最后 $2$ 个子集中一个，则这两个数的差能被 $2n$ 整除。
例：一间房屋内有 $10$ 个人，他们当中没有人超过 $60$ 岁（年龄只能以整数给出)，但又至少不低于 $1$ 岁。证明：总能找出两组人（两组人中不含相同的人），使得年龄和相同。

证：$10$ 个人构成的子集一共是 $2^{10}=1024$ 个，去除掉空集与全集，一共 $1022$ 个子集可以是找出的两组人中的一组。由于这些子集的年龄和最小为 $1$ 岁，且不超过 $60 \times 9= 540$ 岁。因此，由鸽巢原理知，至少有两组人的年龄和相同，去除这两组人的相同人后，所得的两组人满足题目要求
- 如果改成 $9$ 个人，则下面记得改成 $480$
其他问题和作业题整理——todo

3.2 鸽巢原理的加强形式

定理3.2.1 ：令 $q_1, q_2 , \dots, q_n$ 为正整数。若将 $q_1+q_2+ \dots +q_n - n+1$ 个物体放进 $n$ 个盒子内，那么，

或者第 $1$ 个盒子至少含有 $q_1$ 个物体，

或者第 $2$ 个盒子至少含有 $q_2$ 个物体，

…，

或者第 $n$ 个盒子至少含有 $q_n$ 个物体

当然，也就是说不会出现每个盒子的物体数少于上述数字的情况

令 $q_1 = q_2 = \dots = q_n = 2$，即为鸽巢原理的简单形式
平均原理：如果 $m$ 个物体放入 $n$ 个盒子，则至少有一个盒子含有 $\lceil m/n\rceil$ 个或更多的物体
例（判断满足条件的最小物品总数）：一篮水果装有苹果、梨和桔子。为了保证或者至少 $8$ 个苹果，或者至少 $6$ 个梨或者至少 $9$ 个桔子，则放入篮子中的水果的最少件数是多少？

$8+6+9-3+1=21$ 件

（尽量说明下反面）：当放入篮子的水果数为 $20$ 时，可能出现 $7$ 个苹果，$5$ 个香蕉和 $8$ 个桔子的情形，不满足题目要求
例：证明从任意给出的 $5$ 个正整数中必能选出 $3$ 个数，它们的和能被 $3$ 整除。

任意正整数除以 $3$ 的余数只能为 $0,1,2$。

设 $A$ 为任意给出的 $5$ 个正整数的集合。设 $t_0, t_1, t_2$ 为 $A$ 中除以 $3$ 余数分别为 $0, 1, 2$ 的数的个数。
- 若 $t_0, t_1, t_2$ 均不为 $0$，则一定有三个数除以 $3$ 的余数分别为 $0, 1, 2$，则这三个数的和能被 $3$ 整除。
- 若 $t_0, t_1, t_2$ 中至少有一个为 $0$，不妨设 $t_0=0$，则 $t_1+t_2=5$。由平均原理知，至少有 $\lceil 5/2\rceil = 3$ 个数除以 $3$ 的余数相同（全为 $1$ 或全为 $2$），则这三个数的和能被 $3$ 整除。
例：证明每个由$n^2+1$个实数构成的序列：$a_1, a_2, \dots a_{n^2 + 1}$，或者含有长度为 $n+1$ 的递增子序列，或者含有长度为 $n+1$ 的递减子序列。

证：假设不存在长度为 $n+1$ 的递增子序列，只需构造一个长度为 $n+1$ 的递减子序列。设 $l_k$ 是以 $a_k$ 为起始的最长递增子序列长度，$k =1, 2, …，n^2+1$，则对 $\forall k$ 有 $1 \leq l_k \leq n$。对序列 $l_1, l_2, …,l_{n^2 + 1}$ 运用鸽巢原理加强形式，一定存在 $\lceil (n^2+1)/n \rceil =n+1$ 个 $l_i$ 相等。设 \[ l_{k_1}=l_{k_2}= \dots =l_{k_{n+1}} \] 其中 $1 \leq k_1< k_2<…< k_{n+1} \leq n^2+1$

(下面证明 $a_{k_1},a_{k_2}, \dots ,a_{k_{n+1}}$ 是长度为 $n+1$ 的递减序列) 反证：假设存在 $k_i, k_{i+1}$，使得 $a_{k_i}<a_{k_{i+1}}$，把 $a_{k_i}$ 加到以 $a_{k_{i+1}}$ 开始的最长递增子序列，则构成了以 $a_{k_i}$ 开始的递增子序列，得 $l_{k_i}>l_{k_{i+1}}$，与 $l_{k_i} = l_{k_{i+1}}$ 矛盾！

证明不是递增就是递减

todo 方阵排队问题

3.3 $Ramsey$ 定理

$Ramsey$ 定理：
- 通俗实例：在 $6$ 个人中，或者有 $ 3$ 个人，他们中每两个人都互相认识；或者有 $3$ 个人，他们中的每两个人都彼此不认识。
- 给图 $K_6$ 的边任意着红色、蓝色后，一定存在一个红色 $K_3$ 或蓝色$K_3$，记为$K_6 \rightarrow K_3,K_3$
- $n$ 阶完全图：用 $K_n$ 表示平面上没有 $3$ 点共线的 $n$ 个顶点构成的一个完全图。
证明：给图 $K_6$ 的边任意着红色、蓝色，一定存在一个红色 $K_3$ 或蓝色 $K_3$，记为 $K_6 \rightarrow K_3, K_3$
定理 3.3.1 ($Ramsey$ 定理) ：如果两个整数 $m ≥ 2, n ≥ 2$，则存在正整数 $p$，使得 $K_p \rightarrow K_m,K_n$
$Ramsey$ 数：$Ramsey$ 数 $r(m, n)$ 是使 $K_p \rightarrow K_m,K_n$ 成立的最小整数 $p$
- 一定存在
- 对称性：$r(m,n) = r(n,m)$
- 平凡的 $Ramsey$ 数：$r(2, n)=n, r(m,2)=m$
  
  或者存在一条边是红色，或者所有边是蓝色
- 推论：$r(m, n) ≤ r(m-1, n) + r(m, n-1)$。
$Ramsey$ 定理推广：如果$n_1, n_2,\dots, n_l$ 都是大于或等于 $2$ 的整数，则一定存在正整数 $p$，使得 \[ K_p \rightarrow K_{n_1},K_{n_2},\dots,K_{n_l} \] 满足以上条件的最小整数 $p$ 称为 $Ramsey$ 数。例如：$K_{17} \rightarrow K_3,K_3,\dots,K_3$
例：证明 $r(3, 3, 3) \le 17$ todo

第4章生成排列和组合

排列生成算法：

递归生成算法

邻位对换算法

从逆序生成排列算法

逆序相关知识

从最大数或最小数

组合生成算法：

字典序

反射 $Gray$ 码

递归法

逐次法

基于字典序的 $r$ - 组合生成算法

4.1 生成排列

递归生成算法
邻位对换算法：
- 可活动：箭头指向与其相邻但比它小的整数
两种算法生成的排列顺序一致

4.2 排序中的逆序

逆序：令 $i_1,i_2,\dots,i_n$ 是集合 $\{1, 2,\dots, n\}$ 的一个排列，如果 $0\leq k < l \leq n$，且 $i_k > i_l$ , 称数对 $(i_k, i_l)$ 是排列的一个逆序。
- 如，排列 $31524$ 的逆序为 $(3,1), (3,2), (5,2), (5,4)$
- 唯一没有逆序的排列为 $1 2 3 \dots n$
逆序数：对于 $\{1, 2,\dots, n\}$ 上的一个排列，逆序数 $a_j$ 是第二元是 $j$ 的逆序的数量，也即排列中先于整数 $j$ 并大于 $j$ 的整数的个数，度量 $j$ 的反序程度。
逆序列：令 $a_j$ 表示排列 $i_1i_2,\dots,i_n$ 中数 $j$ 的逆序数，称$a_1,a_2,\dots,a_n$为排列 $i_1i_2,\dots,i_n$ 的逆序列

例如，排列 $361245$。

逆序：$(3, 1) ,(3, 2), (6, 1),(6, 2), (6, 4) ,(6, 5)$。

逆序数：$a_1=2, a_2=2, a_3=0, a_4=1, a_5=1, a_6=0$

逆序列：$2 2 0 1 1 0$

从逆序生成排列算法：

从最大数开始。已知 $\{1, 2, …, 8\}$ 的一个排列的逆序列为 $5 3 4 0 2 1 1 0$，确定此排列。【每个数放在第“逆序数”个位置上】
- 特点：相对位置固定，但是每个整数的位置要到最后才能确定
当前放置数当前排列逆序数

8： 8 0

7： 8 7 1

6： 8 6 7 1

5： 8 6 5 7 2

4： 4 8 6 5 7 0

3： 4 8 6 5 3 7 4

2： 4 8 6 2 5 3 7 3

1： 4 8 6 2 5 1 3 7 5

当前放置数	当前排列	逆序数
8：	8	0
7：	8 7	1
6：	8 6 7	1
5：	8 6 5 7	2
4：	4 8 6 5 7	0
3：	4 8 6 5 3 7	4
2：	4 8 6 2 5 3 7	3
1：	4 8 6 2 5 1 3 7	5

从最小数开始。仍上例。【每个数放在第“逆序数+1”个空位置上】

当前放置数	当前排列	逆序数
1：	X X X X X 1 X X	5
2：	X X X 2 X 1 X X	3
3：	X X X 2 X 1 3 X	4
4：	4 X X 2 X 1 3 X	0
5：	4 X X 2 5 1 3 X	2
6：	4 X 6 2 5 1 3 X	1
7：	4 X 6 2 5 1 3 7	1
8：	4 8 6 2 5 1 3 7	0

逆序个数为奇数的排列称为奇排列；逆序个数为偶数的排列称为偶排列。
$15 Puzzles$：用逆序数证明无解：左右移动逆序数的和不变，上下移动逆序数的和 $+3$

4.3 生成组合

$n$ 元集合 $S=\{x_{n-1},x_{n-2}, \dots, x_0\}$ 的组合与长度为 $n$ 的二进制数一一对应（注意到两者个数均为 $2^n$）
- 对应方法：这个整数的二进制表示 $1$ 所在的位置的元素包含在组合中
- 如：$29 \in [1, 2^7]$ 的二进制表示 $0011101$，则 $29$ 对应的组合为 $\{x_4, x_3, x_2, x_0\}$
字典序生成算法
- 初始：$a_{n-1} \dots a_1a_0 = 0 \dots 00$
- 当 $a_{n-1} \dots a_1a_0 \neq 1 \dots 11$ 时，求出使得 $a_j = 0$ 的最小整数 $j$，用 $1$ 替换 $a_j$ 并用 $0$ 替换每个 $a_{j-1}, \dots a_1, a_0$
  
  把最小的 $1$ 找出来，后面的全换成 $0$
- 例1：求组合 $\{x_6, x_4, x_2, x_1, x_0\}$ 的下一个组合
  - $1010111 + 1 = 1011000$，对应组合为 $\{x_6, x_4, x_3\}$
- 例2：$S = \{x_6, x_5, \dots, x_1, x_0\}$ 的哪个子集是子集列表中的第 $108$ 个子集？
  - 注：位置从 $0$ 开始，第 $108$ 个子集对应 $108$，$108$ 二进制数为 $1101100$，则对应子集为 $\{x_6, x_5, x_3, x_2\}$
反射 $Gray$ 码序生成算法：特点为相邻的组合间仅相差一个元素。生成方法：前面补0，1；之后折叠

对应 $n$ 维空间点坐标
- 递归生成：见图
- 逐次生成：整体思路——每次改变 $\sigma$ 的奇偶性
  - 初始：$a_{n-1} \dots a_1a_0 = 0 \dots 00$
  - 当 $a_{n-1} \dots a_1a_0 \neq 1 \dots 00$ 时，计算 $\sigma(a_{n-1} \dots a_1 a_0) = a_{n-1} + \dots + a_1 + a_0$，如果结果为偶数，则改变 $a_0$；否则确定使得 $a_j = 1$ 且对于所有 $i < j$$， $$a_i = 0$ 的最小整数 $j$，改变 $a_{j+1}$
可由归纳法证明二者生成相同顺序的 $n$ 阶反射 $Gray$ 码
确定 $n$ 元组在 $Gray$ 码序表中的准确位置：

4.4 生成 $r$ - 组合

先于：若 $A \cup B \setminus A \cap B$ 中的最小整数属于 $A$，则称 $A$ 先于 $B$

属于 $A \cup B$，但不同时属于 $A \cap B$
直接后继求解算法：找出满足 $a_i<n$，且 $a_i+1$ 不在 $\{a_1,…, a_r\}$ 中的最大的 $i$，记为 $k$，在字典序中 $a_1a_2…a_r$ 的直接后继是$a_1a_2…a_{k-1} (a_k+1) (a_k+2)…(a_k+r – k +1)$
$r$ 子集的生成算法：从 $12 \dots r$ 开始，逐个列出直接后继，直到得到 $(n-r+1)(n-r+2) \dots n$

第5章二项式系数

讨论二项式系数相关等式和性质

5.1 $Pascal$ 三角形

定理5.1.1($Pascal$ 公式)：对于满足 $1 \leq k \leq n$ 的所有整数 $k$ 和 $n$，有： \[ \left(\begin{matrix} n \\ k \end{matrix}\right)= \left(\begin{matrix} n-1 \\ k \end{matrix}\right)+ \left(\begin{matrix} n-1 \\ k-1 \end{matrix}\right) \]
- 组合证明同前，此处从略
- $Pascal$ 三角形：
- 行列套用定义即可，没有很强的几何直观性
- 另一种解释：路径移动
- 可以证明若干项求和的等式

5.2 二项式定理

定理5.2.1：令 $n$ 是一个正整数, 那么对于所有的 $x, y$ 有： \[ (x+y)^n=\sum_{k=0}^n \left( \begin{matrix} n \\ k \end{matrix} \right) x^{n-k} y^k \]
- 可以对换 $x, y$，对换 $n$ 和 $n-k$ 得到等价形式
二项式系数的其它等式： \[ k \left( \begin{matrix} n \\ k \end{matrix} \right) = n \left( \begin{matrix} n-1 \\ k-1 \end{matrix} \right) \]
- $n$ 个人中选 $k$ 人组成足球队，其中 $1$ 人为队长，有多少种不同选法？
  
  1、先选足球队，然后从足球队中选队长；
  
  2、先选队长，再在剩下的 $n-1$ 人中选 $k-1$ 个足球队员。
\[ \sum_{k=0}^n \left( \begin{matrix} n \\ k \end{matrix} \right)^2 = \left( \begin{matrix} 2n \\ n \end{matrix} \right) (n \geq 0) \]
- 设 $A={1, 2, …, n}, B={n+1, n+2, …, 2n}$，$A \cup B={1, 2, …, 2n}$。令 $S＝A\cup B$，$A$ 和 $B$ 是两个不相交的 $n$ 个元素集合.
  - $S$ 的 $n$ - 组合数是$\left(\begin{matrix} 2n \\ n \end{matrix}\right)$
  - 设 $S$ 的一个 $n$ - 组合含有 $A$ 的元素为 $k$ 个，含有 $B$ 的元素为 $n-k$ 个，$k=0,1,…, n$。令 $C_k$ 是含有 $k$ 个 $A$ 的元素的 $n$ - 组合，则 $S$ 的所有 $n$ - 组合可划分为：$C_0, C_1,…, C_n$。有：
  \[ \left(\begin{matrix} 2n \\ n \end{matrix}\right) = \left| C_0 \right| + \left| C_1 \right| + \dots + \left| C_n \right| \]
  
  \[ \left| C_k \right| = \left(\begin{matrix} n \\ k \end{matrix}\right) \left(\begin{matrix} n \\ n-k \end{matrix}\right) = \left(\begin{matrix} n \\ k \end{matrix}\right) ^2 \]
  
  得证。 \[ \left(\begin{matrix} n \\ 0 \end{matrix}\right)- \left(\begin{matrix} n \\ 1 \end{matrix}\right)+ \left(\begin{matrix} n \\ 2 \end{matrix}\right)+ \dots + (-1)^n\left(\begin{matrix} n \\ n \end{matrix}\right)+ \dots = 0 \]
- 证明：
  - 方法一：令二项式公式中 $x = 1, y = -1$
  - 方法二：奇偶子集之和之差

\[ \left(\begin{matrix} n \\ 0 \end{matrix}\right)+ \left(\begin{matrix} n \\ 2 \end{matrix}\right)+ \dots = \left(\begin{matrix} n \\ 1 \end{matrix}\right)+ \left(\begin{matrix} n \\ 3 \end{matrix}\right)+ \dots = 2^{n-1} \]

证明
- 方法一：偶数个元素的子集的个数 = 奇数个元素的子集的个数 = $\dfrac{1}{2}$总子集数。
- 方法二：$x_1,…, x_{n-1}$ 每个有两种选择，但前面的奇偶性决定了 $x_n$ 只有一种选择（使得总元素个数为奇数或偶数）
例：证明以下等式： \[ 1 \left(\begin{matrix} n \\ 1 \end{matrix}\right)+ 2 \left(\begin{matrix} n \\ 2 \end{matrix}\right)+ \dots + n \left(\begin{matrix} n \\ n \end{matrix}\right) = n 2^{n-1} \]
- 利用选队长公式 $k \left( \begin{matrix} n \\ k \end{matrix} \right) = n \left( \begin{matrix} n-1 \\ k-1 \end{matrix} \right)$ \[ 1 \left(\begin{matrix} n \\ 1 \end{matrix}\right) + 2 \left(\begin{matrix} n \\ 2 \end{matrix}\right) + \dots + n \left(\begin{matrix} n \\ n \end{matrix}\right) = n \left(\begin{matrix} n-1 \\ 0 \end{matrix}\right) + n \left(\begin{matrix} n-1 \\ 1 \end{matrix}\right) + \dots + n \left(\begin{matrix} n-1 \\ n-1 \end{matrix}\right) = n2^{n-1} \]
- 求导法：对 $(1+x)^n = 1 + \left(\begin{matrix} n \\ 1 \end{matrix}\right)x + \left(\begin{matrix} n \\ 2 \end{matrix}\right)x^2 + \dots + \left(\begin{matrix} n \\ k \end{matrix}\right)x^k + \dots + \left(\begin{matrix} n \\ n \end{matrix}\right)x^n$，左右同求导数，取 $x = 1$
例：
组合定义扩展

5.3 二项式系数的单峰性

定理5.3.1：对 $n$ 是奇数偶数的单峰性讨论
- 证明：考虑相邻两项的商
链与反链：令 $S$ 是 $n$ 个元素的集合，$C$ 是 $S$ 的子集的集合
- 链：若 $C$ 中任意两个不同的子集都存在包含关系，则称 $C$ 是 $S$ 的一个链。
  - 对 $\forall S_1, S_2 \in C$，且 $S_1 \ne S_2$，则 $S_1 \subset S_2$ 或 $S_2 \subset S_1$
- 反链：若 $C$ 中任意一个子集都不包含在其他子集内，即任意两个不同的子集都不存在包含关系，则称 $C$ 是 $S$ 的一个反链。
  - 一个构造反链的方法：取 $A_k$ 为 $S$ 所有的 $k$ 子集的集合
- 链与反链的关系：
  - $S$ 上的一条链最多只能包含 $S$ 的任意一条反链中的一个子集
  - $S$ 上的一条反链最多只能包含 $S$ 的任意一条链中的一个子集
    
    可以有 $0$ 或 $1$ 个公共元素
  - 反证法：设 $C$ 是 $S$ 的一条链，$A$ 是 $S$ 的一条反链。若 $C$ 包含 $A$ 中两个子集 $S_1, S_2$，则 $S_1, S_2$ 不存在包含关系，与 $C$ 是 $S$ 的一条链矛盾
- 链与反链的推广：
  - 极大元、极小元
- 一些证明题：todo
定理 5.3.3：设 $S$ 为 $n$ 个元素的集合，则 $S$ 的一个反链最多包含$\left(\begin{matrix} n \\ \lfloor n/2 \rfloor \end{matrix}\right)$个集合。
最大链：
- $A_0 = \emptyset \subset A_1 \subset A_2 \dots \subset A_n$
- $|A_i| = i(i = 1, \dots , n)$
- $S$ 的最大链与 $S$ 的排列一一对应，相应地，最大链的数目为 $n!$
- 构造方法：
  - $A_0 = \emptyset$
  - 从 $S$ 中选择元素 $i_1$，$A_1 = \{i_1\}$
  - 从 $S$ 中选择元素 $i_2 \ne i_1$，$A_2 = \{i_1, i_2\}$
  - $\dots$
  - 从 $S$ 中选择元素 $i_k \ne i_1, i_2, \dots, i_{k-1}$，$A_k = \{i_1, i_2 \dots, i_k\}$
  - $\dots$
  - 从 $S$ 中选择元素 $i_n \ne i_1, i_2, \dots, i_{n-1}$，$A_n = \{i_1, i_2 \dots, i_n\}$
对称链划分：
- $S$ 的幂集 $\mathcal{P}(S)$ 的一个链划分
  - 链中每一个子集比它前面的子集的元素个数多 $1$
  - 链中第一个子集与最后一个子集的大小和等于 $n$
  - 如果只含一个子集，那么既是第一个又是最后一个，大小为 $\dfrac{n}{2}$
  - 每一个链中必须含有一个 $\lfloor n/2 \rfloor$ 的子集和一个 $\lceil n/2 \rceil$ 的子集
  - 链的个数为 $\left(\begin{matrix} n \\ \lfloor n/2 \rfloor \end{matrix}\right)$
- 构造方法：对于 $n=k$ 时的每一个含多个子集的链 $E$，可构造 $n=k+1$ 时的两个链
  - 在 $E$ 的最后一个子集中增加 $k+1$，并加入这个新子集
  - 在 $E$ 的除最后一个子集外的所有子集中加入 $k+1$，并删除最后一个子集

5.4 多项式定理

把二项式定理 $(x+y)^n$ 扩展到$(x_1+x_2+ \dots + x_t)^n$。其中，多项式系数： \[ \left(\begin{matrix} n \\ n_1 n_2 \dots n_t \end{matrix}\right) = \dfrac{n!}{n_1! n_2! \dots n_t!} \]
定理5.4.1：设 $n$ 是正整数，对于所有的 $x_1, x_2, \dots, x_t$，有 \[ (x_1+x_2+...+x_t)^n=\sum\binom{n}{n_1n_1...n_t}{x_1}^{n_1}{x_2}^{n_2}...{x_t}^{n_t} \]

5.5 牛顿二项式定理

把二项式定理的指数扩展到实数

第6章容斥原理及应用

解决具有重叠集合的并集的计数原理

6.1 容斥原理

定理6.1.1（容斥原理计数）：集合 $S$ 不具有性质 $P_1,P_2, \dots ,P_m$ 的物体的个数： \[ | \overline{A_1} \cap \overline{A_2} \cap \dots \cap \overline{A_n}|= |S| - \sum|A_i| + \sum|A_i \cap A_j| - \sum |A_i \cap A_j \cap A_k| + \dots + (-1)^m \sum |A_1 \cap A_2 \cap \dots \cap A_m| \]
- 例：求 $1$ 到 $1000$ 不能被 $5, 6, 8$ 整除的数的个数。
  
  设 $A_1, A_2 ,A_3$ 分别是 $1$ 到 $1000$ 中能被 $5, 6, 8$ 整除的数集合，那么 $1$ 到 $1000$ 不能被 $5, 6, 8$ 整除的数的个数为 $|\overline{A_1} \cap \overline{A_2} \cap \overline{A_3}|$ \[ \begin{aligned} |A_1| &= \lfloor 1000/5 \rfloor = 200 \\ |A_2| &= \lfloor 1000/6 \rfloor = 166 \\ |A_3| &= \lfloor 1000/8 \rfloor = 125 \\ |A_1 \cap A_2| &= \lfloor 1000/30 \rfloor = 33 \\ |A_1 \cap A_3| &= \lfloor 1000/40 \rfloor = 25 \\ |A_2 \cap A_3| &= \lfloor 1000/24 \rfloor = 41 \\ |A_1 \cap A_2 \cap A_3| &= \lfloor 1000/120 \rfloor = 8 \\ \end{aligned} \] 由容斥原理，原式 $=1000-(200+166+125)+(33+25+41)-8=600$
- 例：从 $0$ 到 $99999$ 中有多少同时含有数字 $2, 5, 8$ 的整数。
  
  设 $A_1, A2, A_3$ 分别是不包含数字 $2, 5, 8$ 的集合。 \[ \alpha_1 = |A_1| = |A_2| = |A_3| = 9^5 \\ \alpha_2 = |A_1 \cap A_2| = 8^5 \\ \alpha_3 = |A_1 \cap A_2 \cap A_3| = 7^5 \] 满足题意的整数个数为 $10^5 - 3 \times 9^5 + 3 \times 8^5 -7^5$
推论6.1.2（容斥原理计数）：集合 $S$ 至少具有性质 $P_1,P_2, \dots ,P_m$ 之一的物体的个数： \[ | A_1 \cup {A_2} \cup \dots \cup A_n|= \sum|A_i| - \sum|A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| + \dots + (-1)^{m+1} \sum |A_1 \cap A_2 \cap \dots \cap A_m| \]

用总数 - 6.1.1

6.2 带重复的组合

例：确定多重集 $T=\{3 \cdot a, 4 \cdot b, 5 \cdot c\}$ 的 $10$ 子集的个数。
- 令多重集 $T^*=\{\infty \cdot a, \infty \cdot b, \infty \cdot c\}$ 的所有 $10$ 子集的集合为 $S$。
  
  用于下文无穷集取方案表述方便
  
  $A_1$ 是 $S$ 中包含多于 $3$ 个 $a$ 的 $10$ 子集的集合；$A_2$ 是 $S$ 中包含多于 $4$ 个 $b$ 的 $10$ 子集的集合；$A_3$ 是 $S$ 中包含多于 $5$ 个 $c$ 的 $10$子集的集合。
  
  那么，$T$ 的 $10$ - 组合数等于 $|\overline{A_1} \cap \overline{A_2} \cap \overline{A_3}|$。
  - $A_1$ 中的每个子集中 $a$ 至少出现 $4$ 次，剩下 $6$ 个元素可以是 $T*$ 的任何 $6$ - 组合，因此：（其余类推）
  \[ |A_1| = \left( \begin{matrix} 6+3-1 \\ 6 \end{matrix} \right) = \left( \begin{matrix} 8 \\ 6 \end{matrix} \right) = 28 \]
  - $A_1 \cap A_2$ 中的每个子集中 $a$ 至少出现 $4$ 次同时 $b$ 至少出现 $5$ 次，剩下 $1$ 个元素可以是 $T*$ 的任何 $1$ 组合，因此：
  \[ |A_1 \cap A_2| = \left( \begin{matrix} 1+3-1 \\ 1 \end{matrix} \right) = \left( \begin{matrix} 3 \\ 1 \end{matrix} \right) = 3 \]
  
  这个地方先取 $4$ 个 $a$，后面仍可以从无穷集 $T^*$ 中取 $a$，保证了情况是完备的
例：求满足 $1 \leq x_1 \leq 5, -2 \leq x_2 \leq 4, 0 \leq x_3 \leq 5, 3 \leq x_4 \leq 9$ 的方程 $x_1+x_2+x_3+x_4 =18$的整数解个数。
- 转化为“确定多重集 $T=\{4 \cdot a, 6 \cdot b, 5 \cdot c, 6 \cdot d\}$ 的 $16$ 子集的个数”，解法与上类似

6.3 错位排列 Derangement

错位排列： 设 $X={1,2, \dots ,n}$，它的排列用 $i_1 i_2 \dots i_n$ 表示, 错位排列是使得 $i_1 \neq 1, i_2 \neq 2,\dots, i_n \neq n$ 的排列。用$D_n$表示错位排列个数。
- 前几项：$D_1 = 0，D_2 = 1，D_3 = 2，D_4 = 9$
定理6.3.1： 对 $n \geq 1$，（应用容斥原理） \[ D_n=n!-\binom{n}{1}(n-1)!+\binom{n}{2}(n-2)!+...+(-1)^n\binom{n}{n}0! \]

\[ D_n = n! \ (1 - \dfrac{1}{1!} + \dfrac{1}{2!} - \dfrac{1}{3!} + \dots + (-1)^n \dfrac{1}{n!}) \]
- 计算可得：$D_5=44, D_6=265, D_7=1854, D_8=14833$
例：确定 ${1, 2,…, 8}$ 的排列中恰有四个整数在它们的自然位置上的排列数。
- 解：任选四个整数在自然位置上：$\begin{pmatrix} 8 \\ 4 \end{pmatrix}$
  
  剩下四个整数不在其自然位置上： $D_4$
  
  因此，恰有四个整数在它们的自然位置上的排列数为$\begin{pmatrix} 8 \\ 4 \end{pmatrix} D_4$
错位排列的递推关系1：$D_n$ 满足如下递推关系： \[ D_n = (n-1)(D_{n-2} + D_{n-1}), (n=3,4,\dots) \\ D_2 = 1; D_1 = 0 \] 计算用的递推关系2： \[ D_n = nD_{n-1} + (-1)^n \]

6.4 带有禁止位置的排列

带禁止位置的“非攻击型车”：$\{1,2,…, n\}$ 的排列 $i_1 i_2 \dots i_n$ 对应于棋盘上以方格 $(1, i_1), (2, i_2),\dots, (n, i_n)$ 为坐标的 $n$ 个车的位置。一些位置禁止。
定理6.4.1： 将 $n$ 个非攻击型不可区分的车放到带有禁止位置的 $n \times n$ 的棋盘中，放法总数等于： \[ n! - r_1 (n-1)! + r_2 (n-2)! - \dots + (-1)^k r_k (n-k)! + \dots + (-1)^n r_n \]
- $r_k$：所有的 $k$ 个车放置在其禁止位置上的放置方法数，$k=1,2,…, n$，且其计算不考虑剩下的 $n-k$ 个车的放置
- 应满足：任意两个车不在同一行或同一列

6.5 另一个禁止位置问题

相对禁止位置排列计数：$Q_n$：$\{1, 2, \dots , n\}$ 的排列中没有 $12, 23, \dots , (n-1)n$ 这些模式出现的排列的个数
- 前几项：$Q_1= 1， Q_2 = 1, Q_3 = 3, Q_4 = 11$
用容斥原理计算 $Q_n$：令 $A_i$ 是 $i(i+1)$ 出现的排列的集合，$i=1,2,\dots,n-1$
- 计算 $A_i$ : $A_1$ 可看作 $1,2, 3,\dots, n$ 的所有排列的集合，因此 $|A_1|=(n-1)!$。显然，由于对称性，对任意 $i$，都有$|A_i|=(n-1)!$
- 计算$|A_i \cap A_j|$：讨论两种情况：
  1. $A_i \cap A_{i+1}$。可看作 $1, 2, …, (i, i+1, i+2), i+3, …, n$ 的所有排列的集合，因此$|A_i \cap A_{i+1}|=(n-2)!$
  2. $A_i \cap A_j$，其中 $j>i+1$。可看作 $1,2,…, (i, i+1), i+2, …, ( j, j+1), …, n$ 的所有排列的集合，因此$|A_i \cap A_j|=(n-2)!$
  所以，对任意 $i, j$，都有$|A_i \cap A_j|=(n-2)!$
- 同理可证，对于每个 $k$ 子集 $\{i_1,…, i_k\}$，有 $|A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_k}|=(n-k)!$
- 由此推出下面公式。
定理6.5.1：对于 $n \ge 1$ \[ \begin{align} Q_n &= n! + \sum_{k=1}^{n-1} (-1)^k \left( \begin{matrix} n-1 \\ k \end{matrix} \right) (n-k)! \\ &= n! - \left( \begin{matrix} n-1 \\ 1 \end{matrix} \right) (n-1)! + \left( \begin{matrix} n-1 \\ 2 \end{matrix} \right) (n-2)! + \dots + (-1)^{n-1} \left( \begin{matrix} n-1 \\ n-1 \end{matrix} \right) 1! \end{align} \]
例：旋转木马有 $8$ 个座，每个座位都代表一种不同的动物。$8$ 个男孩脸朝里围坐在旋转木马上，使得每一个男孩都面对到另一个男孩。他们能够有多少种方法改变座位使得每人面对的男孩都不同于之前面对的男孩？
- 假设 $8$ 个男孩分成了四对：$(1,5), (2,6), (3,7), (4,8)$。假设 $A_1, A_2, A_3, A_4$ 分别表示仍然有 $(1,5), (2,6), (3,7), (4,8)$ 出现的坐法的集合。则使得每人面对的男孩都不同的坐法的数目为：$|\overline{A_1} \cap \overline{A_2} \cap \overline{A_3} \cap \overline{A_4}|$
\[ |A_1| = |A_i| = 8 * 6! \\ |A_1 \cap A_2| = 8 * 6 * 4! \\ |A_1 \cap A_2 \cap A_3| = 8 * 6 * 4*2! \\ |A_1 \cap A_2 \cap A_3 \cap A_4| = 8 * 6 * 4 * 2 \]
相对禁止位置 $Q_n$ 与错位排列 $D_n$ 的关系： \[ Q_n = D_n + D_{n-1} \]

第7章递推关系和生成函数

生成函数核心思想：

把离散数列和幂级数一一对应起来

把离散数列间的相互结合关系对应成为幂级数间的运算关系

由幂级数形式确定离散数列的构造

7.1 若干数列

例：设 $h_n$ 是 $1$ 行 $n$ 列棋盘用红黄蓝三种颜色着色并使得没有着成红色的方格相邻的着色方法数。求 $h_n$ 满足的递推关系。
- 末尾为红：必须前面再放黄色or蓝色保证不相邻 $2h_{n-2}$
- 末尾为蓝or黄：直接拼接即可 $2h_{n-1}$
例：确定 $2 \times n$ 棋盘用多米诺牌完全覆盖的方法数 $h_n$
例：确定用单牌和多米诺牌完美覆盖 $1 \times n$ 棋盘的方法数 $b_n$
$Fibonacci$ 数列：
- 部分和：$s_n = f_0+f_1+ \dots +f_n = f_{n+2}-1$
  - 证明：数学归纳法
- $f_n$ 是偶数当且仅当 $n$ 被 $3$ 整除
  - 每三项都是偶奇奇
定理7.1.2：沿 $Pascal$ 三角形从左下到右上的对角线上的二项式系数和是斐波那契数，即 \[ f_n = \left( \begin{matrix} n-1 \\ 0 \end{matrix} \right) + \left( \begin{matrix} n-2 \\ 1 \end{matrix} \right) + \left( \begin{matrix} n-3 \\ 2 \end{matrix} \right) + \dots + \left( \begin{matrix} n-k \\ k-1 \end{matrix} \right) \] 其中，$k=\lfloor (n+1)/2 \rfloor$

7.2 生成函数

令 $h_0, h_1, \dots ,h_n \dots$ 为一无穷数列，其生成函数定义为：

\[ g(x)=h_0 +h_1x+h_2x^2+\dots+h_nx^n+\dots \]

例：设 $k$ 是正整数，$h_n$ 等于方程 $e_1+e_2+ \dots +e_k =n$ 的非负整数解个数，即 $h_n$ 为多重集 $S={a_1, a_2, , a_k} $的 $n$ - 组合个数，求数列 $h_0, h_1,…, h_n…$ 的生成函数 $g(x)$。
- 由于$h_n = \left( \begin{matrix} n+k-1 \\ n \end{matrix} \right)$。因此，
\[ \begin{aligned} g(x) &= \sum_{n=0}^\infty \left( \begin{matrix} n+k-1 \\ n \end{matrix} \right) x^n = \dfrac{1}{(1-x)^k} \ (|x|<1) \\ &= (\sum_{e_1=0}^\infty x^{e_1}) (\sum_{e_2=0}^\infty x^{e_2}) \dots (\sum_{e_k=0}^\infty x^{e_k}) \end{aligned} \]
例：设 $S$ 是多重集合${a_1, a_2, a_3 , a_4} $。确定数列 $h_0, h_1,…, h_n, …$ 的生成函数，其中 $h_n$ 是满足以下约束的 $S$ 的 $n$ 组合数。 (1) $a_1$ 出现奇数次，$a_2$ 出现偶数次。 (2) 元素 $a_1$ 不会出现，$a_2$ 至多出现 $1$ 次。 (3) 每个 $a_i$ 出现的次数是 $3$ 的倍数。
- 解: (1) 生成函数 \[ \begin{align} g(x) &=(x+x^3+x^5+...+x^{2n+1}+...) (1+x^2+x^4+...+x^{2n}+...) (1+x+x^2+...+x^n+...)^2 \\ &=x(1+x^2+x^4+...+x^{2n}+...)^2 (1+x+x^2+...+x^n+...)^2 \\ &= x(\dfrac{1}{1-x^2})^2 (\dfrac{1}{1-x})^2 \end{align} \]
  1. 生成函数 $g(x) =1 (1+x)(1+x+x^2+…+x^n+…)^2= (1+x)/(1-x)^2$
  2. 生成函数 $g(x) = (1+x^3+x^6+…x^{3n}+…)^4 = 1/(1-x^3)^4$
例：由生成函数求通项 $h_n$
几个常见的展开式： \[ (1-x)^n = \sum_{k=0}^\infty \left( \begin{matrix} n \\ k \end{matrix} \right) x^k \\ \dfrac{1}{(1-x)^n} = \sum_{k=0}^\infty \left( \begin{matrix} n+k-1 \\ k \end{matrix} \right) x^k \]
- $+x$ 用 $-x$ 带入 $x$ 即可
例：求装有苹果、香蕉、桔子和梨的果篮的数量 $h_n$，其中每个果篮中，苹果的个数是偶数，香蕉的个数是 $5$ 的倍数, 桔子不超过 $4$ 个，而且至多只有一个梨. \[ \begin{align} g(x) &=(1+x^2+x^4+…)( 1+x^5+x^{10}+x^{15}+…)(1+x+x^2+x^3+x^4)( 1+x) \\ &= \dfrac{1}{1-x^2} \cdot \dfrac{1}{1-x^5} \cdot \dfrac{1-x^5}{1-x} \cdot (1+x) \\ &= \dfrac{1}{(1-x)^2} \\ &= \sum_{n=0}^\infty \left( \begin{matrix} n+1 \\ n \end{matrix} \right) x^n \\ &= \sum_{n=0}^\infty (n+1) x^n \end{align} \] 因此，满足条件的 $n$ 组合个数为 $h_n =n+1$。
例（带系数）：设 $h_n$ 是方程 $3e_1+4e_2+2e_3+5e_4=n$ 的非负整数解的个数，求序列 $h_0, h_1, …,h_n,…$ 的生成函数.

生成函数针对的是系数为 $1$ 的情况，所以化归一下，化成系数为 $1$ 即可

作变量替换 $f_1=3e_1, f_2=4e_2, f_3=2e_3, f_4=5e_4$ 得到 $f_1+f_2+f_3+f_4=n \quad (1)$

因此，$h_n$ 等于方程 $(1)$ 的非负整数解的个数，满足 $f_1$ 是 $3$ 的倍数，$f_2$ 是 $4$ 的倍数，$f_3$ 是 $2$ 的倍数，$f_4$ 是 $5$ 的倍数。

因此，生成函数为 \[ \begin{align} g(x) &=(1+x^3+x^6+…)(1+x^4+x^8+…)(1+x^2+x^4+…)(1+x^5+x^{10}+…) \\ &=\dfrac{1}{1-x^3}\cdot\dfrac{1}{1-x^4}\cdot\dfrac{1}{1-x^2}\cdot\dfrac{1}{1-x^5} \end{align} \]

7.3 指数生成函数

数列 $h_0,h_1,h_2, \dots ,h_n$ 的指数生成函数定义为： \[ g^{(e)}(x) = h_0 + \dfrac{h_1}{1!} x + \dfrac{h_2}{2!} x^2 + \dfrac{h_3}{3!} x^3 + \dots + \dfrac{h_k}{k!} x^k + \dots \]
带有附加限制的多重集合 $n$ 排列数列：
- 例：用红、蓝、黄三种颜色给 $1 \times n$ 的棋盘着色，如果要求被着成红色的方格数是偶数，确定给这个棋盘着色的方法数 $h_n$。
  
  设 $h_n$ 表示着色的方法数，定义 $h_0=1$。显然，$h_n$ 等于 $3$ 种颜色的多重集合的 $n$ 排列数，其中每种颜色的重数是无穷的，且要求红色出现的次数是偶数。因此，指数生成函数为 \[ \begin{align} g^{(e)}(x) &= (1 + \dfrac{x^2}{2!} + \dfrac{x^4}{4!} + \dots) (1 + \dfrac{x^1}{1!} + \dfrac{x^2}{2!} + \dots) (1 + \dfrac{x^1}{1!} + \dfrac{x^2}{2!} + \dots) \\ &= \dfrac{1}{2}(e^x+e^{-x})e^x e^x = \dfrac{1}{2} (e^{3x}+e^x) \\ &= \dfrac{1}{2} (\sum_{n=0}^\infty 3^n \dfrac{x^n}{n!} + \sum_{n=0}^\infty \dfrac{x^n}{n!}) = \dfrac{1}{2} \sum_{n=0}^\infty (3^n+1) \dfrac{x^n}{n!} \end{align} \] 得$ h_n=(3^n+1)/2$。
常见展开 \[ e^x = \sum_{n=0}^\infty \dfrac{x^n}{n!} = 1 + x + \dfrac{x^2}{2!} + \dots + \dfrac{x^n}{n!} + \dots \\ \dfrac{1}{2} (e^x+e^{-x}) = 1 + \dfrac{x^2}{2!} + \dfrac{x^4}{4!} + \dots + \dfrac{x^{2n}}{2n!} + \dots \\ \dfrac{1}{2} (e^x-e^{-x}) = x + \dfrac{x^3}{3!} + \dfrac{x^5}{5!} + \dots + \dfrac{x^{2n+1}}{(2n+1)!} + \dots \]

7.4 求解线性齐次递推关系

（齐次）线性递推关系：令 $h_0, h_1, h_2,…, h_n,…$ 是一个数列，若存在量 $a_1, a_2,…,a_k$ 和量 $b_n$（每个量是常数或依赖于 $n$ 的数）使得： \[ h_n = a_1 h_{n-1} + a_2 h_{n-2} + \dots + a_k h_{n-k} +b_n \ (n \geq k) \] 则称该数列满足 $k$ 阶线性递推关系

若 $b_n =0$，则称该数列是 $k$ 阶线性齐次递推关系

若 $a_1, a_2, \dots, a_k$ 都为常数，则称该数列是 $k$ 阶常系数线性递推关系
解法：
- 特征方程法
- 生成函数法
定理7.4.1（特征方程与原递推关系同解）：令 $q$ 为一个非零数，则 $h_n =q_n$ 是常系数线性齐次递推关系 \[ h_n = a_1 h_{n-1} + a_2 h_{n-2} + \dots + a_k h_{n-k} +b_n \ (a_k \neq 0, n \geq k) \] 的解当且仅当 $q$（特征根）是多项式方程 \[ x^k - a_1 x_{k-1} - a_2 x_{k-2} - \dots - a_{k-1} x -a_k = 0 \] 的一个根。

若特征根多项式方程有 $k$ 个不同的根 $q_1, q_2,…, q_k$，则 \[ h_n = c_1 q_1 ^n + c_2 q_2 ^n + \dots + c_k q_k ^n \] 是下述意义下原递推关系的通解：任意给定初始值 $h_0, h_1, …,h_{k-1}$，都存在 $c_1, c_2,…, c_k$ 使得上式是满足原递推关系式和初始条件的唯一的数列.

线性组合的意思
例：确定由 $0, 1, 2$ 组成的长度为 $n$ 且不包含两个连续的 $0$ 或两个连续的 $1$ 的三进制串的个数 $a_n$ 的递推关系，然后求出 $a_n$ 的公式。
- 解: 当 $n=0$ 时，为空串，此时 $a_0=1$；
  
  当 $n=1$ 时, 满足条件的三进制串为 $0, 1, 2$，得 $a_1=3$
  
  当 $n>1$ 时，设以 $0，1，2$ 开头的长度为三进制串的个数分别为 $b_n, c_n, d_n$，则 $a_n =b_n+c_n+d_n$。
  1. 当以 $0$ 开头时，$b_n=c_{n-1}+d_{n-1} \quad (1)$
  2. 当以 $1$ 开头时，$c_n=b_{n-1}+d_{n-1} \quad (2)$
  3. 当以 $2$ 开头时，$d_n=b_{n-1}+c_{n-1}+d_{n-1}=a_{n-1} \quad (3)$
  把 $(1), (2), (3)$ 式左右两边分别相加得：$a_n = b_n+c_n+d_n = c_{n-1}+d_{n-1}+b_{n-1}+d_{n-1}+a_{n-1} = a_{n-1}+a_{n-2}+a_{n-1} = 2a_{n-1} + a_{n-2}$
例：利用生成函数求解 $h_n=h_{n-1}+9h_{n-2}-9h_{n-3} (n>2), h_0=0, h_1=1, h_2=2$。（配凑递推式的系数）
- 令生成函数为 $g(x)=h_0+h_1x+h_2x^2+…+h_nx^n+… \quad (1)$
  
  $(1)$ 式两边分别同乘 $–x, -9x^2, 9x^3$ , 得 \[ \begin{aligned} &(1-x-9x^2+9x^3) g(x) \\ &= h_0 + (h_1-h_0)x+(h_2-h_1-9h_0)x^2+(h_3-h_2-9h_1+9h_0)x +… \\ &= h_0 + (h_1-h_0)x+(h_2-h_1-9h_0)x^2 \\ &= x+x^2 \end{aligned} \] 得$g(x) =(x+x^2)/(1-x-9x^2+9x^3) = (x+x^2)/(1-x)(1-3x)(1+3x)$，再求得 $h_n$
例：求解递推关系 $h_n+h_{n-1}-16h_{n-2}+20h_{n-3}=0 (n \ge 3)$ 其中 $h_0=0, h_1=1, h_2= -1$.
- 1. 求数列的生成函数。$g(x)=x/(1+x-16x^2+20x^3)$
- 1. 将 $g(x)$ 表示成代数分式和。由于 $(1+x-16x^2+20x^3)=(1-2x)^2(1+5x)$，得到 \[ \begin{align} g(x)& = \dfrac{x}{(1-2x)^2(1+5x)} \\ &= \dfrac{c_1}{1-2x} + \dfrac{c_2}{(1-2x)^2} + \dfrac{c_3}{1+5x} \\ &= -\dfrac{2/49}{1-2x} + \dfrac{7/49}{(1-2x)^2} - \dfrac{5/49}{1+5x} \end{align} \]
- 1. 利用牛顿二项式定理展开。 \[ \dfrac{1}{1-2x} = \sum_{k=0}^\infty 2^k x^k \\ \dfrac{1}{(1-2x)^2} = \sum_{k=0}^\infty \left( \begin{matrix} k+1 \\ k \end{matrix} \right) 2^k x^k = \sum_{k=0}^\infty (k+1) 2^k x^k \\ \dfrac{1}{1+5x} = \sum_{k=0}^\infty (-5)^k x^k \] 于是得到： \[ g(x) = \sum_{k=0}^\infty [-\dfrac{2}{49}2^k + \dfrac{7}{49} (k+1) 2^k - \dfrac{5}{49}(-5)^k] x^k \\ h_n = -\dfrac{2}{49}2^n + \dfrac{7}{49} (n+1) 2^n - \dfrac{5}{49}(-5)^n \]

7.5 非齐次递推关系

一般非齐次递推关系的通解：假设有非齐次递推关系 $h_n = a_1 h_{n-1} + a_2 h_{n-2} + \dots + a_k h_{n-k} +b_n$

若 $f_n$ 是对应齐次递推关系 $h_n' = h_n - b_n = a_1 h_{n-1} + a_2 h_{n-2} + \dots + a_k h_{n-k}$ 的通解，而 $c_n$ 是原非齐次递推关系 $(1)$ 的一个特解，那么 $h_n = c f_n + c_n$ 是原非齐次递推关系 $(1)$ 的通解。
例：求递推关系 $h_n=3h_{n-1}-4n, h_0=2$.
- （1）首先求解对应的齐次递推关系 $h_n=3h_{n-1}$ 的通解。特征方程为 $x-3=0$，特征根为 $x=3$，因此通解为 $h_n =c3^n$
- （2）求 $h_n=3h_{n-1}-4n$ 的一个特解：猜测解的形式 $h_n =r_n+s$，代入递推关系得到：$r_n+s = 3(r_{n-1}+s)-4n= (3r-4)n+(-3r+3s)$ 得到：$r=3r-4, s=-3r+3s$ 因此，$r=2$ 和$ s=3$, 从而 $h_n=2n+3$ 是递推关系的一个特解。
- 代入。从而问题的解为：$h_n= -3^n+2n+3$
尝试特解的一些方法：
- 1. 如果 $b_n$ 是 $n$ 的 $k$ 次多项式，那么尝试 $h_n$ 也是 $n$ 的 $k$ 次多项式
  - ① 若 $b_n =d$ (常数)，尝试 $h_n =r$ (常数);
  - ② 若 $b_n =d_n+c$ ($d, c$ 是常数)，尝试 $h_n = r_n+s$ ($r,s$ 是常数);
  - ③ 若 $b_n = a_n^2+dn+c$ ($a,d,c$ 是常数)，尝试 $h_n = r_n^2+s_n+t$ ($r,s,t$ 是常数);
- 1. 若 $b_n =d^n$ ($d$ 是常数)是指数形式，尝试 $h_n = pd^n$ ($p$ 是常数)也是指数形式。
  - 如果失败了可以尝试 $h_n = pnd^n$

7.6 一个几何例子

定理7.6.1（凸多边形三角形剖分方法计数）：设 $h_n$ 表示用下面方法把凸多边形区域分成三角形区域的方法数：在有 $n+1$ 条边的凸多边形区域内通过插入不相交的对角线，而把它分成三角形区域。定义 $h_1 =1$。则 $h_n$ 满足如下递推关系: \[ \begin{align} h_n &= h_1 h_{n-1} + h_2 h_{n-2} + \dots + h_{n-1} h_1 \\ &= \sum_{k=1}^{n-1} h_k h_{n-k} \ (n \geq 2) \end{align} \] 该递推关系解为： \[ h_n = \dfrac{1}{n} \left( \begin{matrix} 2n-2 \\ n-1 \end{matrix} \right),(n=1,2,3,\dots) \] 前几项：$h_1 = 1, h_2 = 1, h_3 = 2, h_4 = 5$

第8章特殊计数序列

8.1 $Catalan$ 数

（接上文）$Catalan$ 数列： $Catalan$ 数列是序列 $C_0, C_1,…, C_n,…,$ 其中 \[ C_n = \dfrac{1}{n+1} \left( \begin{matrix} 2n \\ n \end{matrix} \right),(n=0,1,2,\dots) \] 是第 $n$ 个 $Catalan$ 数。

记法：重要的组合部分是 $n$ 相关，外面的分子不太重要

前几项：$C_1 = 1, C_2 = 2, C_3 = 5, C_4 = 14$

千万注意是第 $n$ 个还是第 $n+1$ 个

且 $C_{n-1}$ 对应凸 $n+1$ 多边形，相差 $2$
例（括号化问题）：矩阵连乘 $P= A_1×A_2×…×A_n$，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？
- 分别计算两个部分，然后对两个部分分别括号化
- $h_n = h_1h_{n-1} + h_2h_{n-2} + h_3h_{n-3} + \dots + h_{n-1}h_1$
- $h_n=C_{n-1}$
例（出栈次序问题）：一个栈(无穷大)的进栈序列为 $1, 2, 3, …, n$，有多少个不同的出栈序列? （后进先出）
- 记出栈序列数目为 $h_n$
- 假设一个出栈序列的最后一个出栈元素为 $k (1≤k ≤n)$，则有
  
  （1）元素 $1, 2, …, k-1$ 的进栈与出栈在 $k$ 入栈前全部完成;
  
  （2）元素 $k+1,…, n$ 的进栈与出栈在 $k$ 入栈后直至 $k$ 出栈前全部完成。
  
  因此，由乘法原理，最后一个出栈元素为 $k$ 的出栈序列的个数为 $h_{k-1} h_{n-k}$
- 由递推关系知 $h_n=C_n$
例（二叉树数目）：$n$ 个节点构成的二叉树的情况有 $h_n = C_n$ 种
定理8.1.1：考虑由 $n$ 个 $+1$ 和 $n$ 个 $-1$ 构成的 $2n$ 项序列 $a_1,a_2,\dots,a_{2n}$，其部分和满足：$a_1 + a_2 + \dots + a_k \geq 0 \ (k=1,2,…,2n)$ 的序列的个数等于第 $n$ 个 $Catalan$ 数 \[ C_n = \dfrac{1}{n+1} \left( \begin{matrix} 2n \\ n \end{matrix} \right) (n \geq 0) \]
- 例（找零）：有 $2n$ 个人排成一对进电影院，门票 $50$ 元，$2n$ 个人中的 $n$ 个人有 $50$ 元纸币，$n$ 个人有 $100$ 元纸币。电影院设置售票点，假设未备有零钱，有多少种排队方法使得只要有 $100$ 元的人买票，售票处就有 $50$ 元的纸币找零？
  
  （1）情况 $1$：若把 $2n$ 个人看成不可区分的，将 $50$ 元用 $+1$ 表示，$100$ 元用 $-1$ 表示。答案 $C_n$
  
  （2）情况 $2$：若把 $2n$ 个人看成可区分的。则需要考虑 $n$ 个有 $50$ 元纸币的人的排列，以及 $n$ 个有 $100$ 元纸币的人的排列。因此排队方法数为： \[ (n!\ n!)\dfrac{1}{n+1} \ \left( \begin{matrix} 2n \\ n \end{matrix} \right) (n \geq 0) \]
- 例：一位大城市的律师在她住所以北 $n$ 个街区和以东 $n$ 个街区处工作。每天她走 $2n$ 个街区上班。如果她不穿越从家到办公室的对角线，有多少可能的道路？
  
  用 $+1$ 表示向东，$-1$ 表示向北。则每条路径对应一个 $+1, -1$ 的序列 $a_1,a_2,\dots,a_{2n}$
$Catalan$ 序列递推关系和初始条件为： \[ C_n = \dfrac{4n-2}{n+1} C_{n-1} (n \geq 1) ,C_0 = 1 \]

8.2 差分序列和 $Stirling$ 数

差分序列：设 $h_0, h_1, h_2, …, h_n, …$ 是一个序列。定义新序列: $h_0, h_1, h_2, , h_n, $称为 $h_0, h_1, h_2, …, h_n, …$ 的（一阶）差分序列，其中 $\Delta h_n = h_{n+1} - h_n (n \geq 0)$，是序列的相邻项的差。
定理8.2.2：差分表的第 $0$ 条对角线等于 $c_0, c_1, c_2, …, c_p, 0, 0, 0, …$，其中 $c_p≠ 0$ 的序列的通项满足： \[ h_n = c_0 \left( \begin{matrix} n \\ 0 \end{matrix} \right) + c_1 \left( \begin{matrix} n \\ 1 \end{matrix} \right) + c_2 \left( \begin{matrix} n \\ 2 \end{matrix} \right) + \dots + c_p \left( \begin{matrix} n \\ p \end{matrix} \right) \] 的关于 $n$ 的 $p$ 次多项式。
定理 8.2.3：假设序列 $h_0, h_1, h_2, …, h_n, …$ 的差分表的第 $0$ 条对角线等于 $c_0, c_1, …, c_p, 0, 0,…$ 那么 \[ \sum_{k=0}^n h_k = c_0 \left( \begin{matrix} n+1 \\ 1 \end{matrix} \right) + c_1 \left( \begin{matrix} n+1 \\ 2 \end{matrix} \right) + c_2 \left( \begin{matrix} n+1 \\ 3 \end{matrix} \right) + \dots + c_p \left( \begin{matrix} n+1 \\ p+1 \end{matrix} \right) \]

其中差分表中第 $0$ 条对角线上的第 $k$ 个元素，记为 $c(p, k)$。
第二类 $Stirling$ 数： \[ h_n = n^p = \sum_{k=0}^n \dfrac{c(p,k)}{k!} [n]_k = \sum_{k=0}^n S(p,k) [n]_k \] $[n]_k$ = $n$ 个不同元素中取 $k$ 个元素的排列数 $P(n, k)$
定理8.2.4（第二类 $Stirling$ 数的递推公式）：如果 $1 ≤ k ≤ p-1$ 则 $S(p, k) = kS(p-1,k) + S(p-1, k-1)$
定理8.2.5（第二类 $Stirling$ 数的组合解释）： 第二类 $Stirling$ 数 $S(p, k)$ 计数的是把 $p$ 个物品的集合划分到 $k$ 个不可区分的盒子且没有空盒子的划分的个数。
- 1. 当 $p$ 独占一个盒子时，当把 $p$ 从盒子中拿走时，得到剩下的 $\{1,2,…, p-1\}$ 划分到 $k-1$ 个非空且不可区分的盒子的划分。因此，存在 $S(p-1, k-1)$ 种对 $\{1, 2, …, p\}$ 的满足条件的划分。
- 1. 当 $p$ 不独占一个盒子时，相当于先将 $\{1, 2,…, p-1\}$ 放到 $k$ 个盒子，不允许空盒，共有 $S(p-1, k)$ 种方案，然后将 $p$ 放进其中一盒，由乘法原理得方案数为 $ kS(p-1, k)$ 。
常见的几个关系：
- $S(p,1) = 1$
- $S(p,2) = 2^{p-1} -1$
- $S(p,p-1) = \left( \begin{matrix} p \\ 2 \end{matrix} \right)$
- $S(p, p-2) = \left( \begin{matrix} p \\ 3 \end{matrix} \right) + 3 \left( \begin{matrix} p \\ 4 \end{matrix} \right) (p \geq 2)$
$Bell$ 数：$Bell$ 数是将 $p$ 个元素的集合分成非空、不可区分的盒子的划分数，记为 $B_p$，则：（至少一个盒子，最多 $p$ 个盒子） \[ B_p = S(p,0)+S(p,1)+\dots+S(p,p) \]
定理8.2.8（第一类 $Stirling$ 数的递推公式）：如果 $1≤ k ≤ p-1$ 则： \[ s(p, k) = (p-1)s(p-1, k) + s(p-1, k-1) \]
定理8.2.9（第一类 $Stirling$ 数的组合解释）：第一类 $Stirling$ 数 $s(p, k)$ 是将 $p$ 个物品排成 $k$ 个非空的循环排列的方法数。
- 设 $p$ 个物品记为 $1, 2, 3, …, p$。将 $1, 2, 3, …, p$ 排成 $k$ 个圆圈有两种类型：
  1. 有一个循环排列中只有 $p$ 自己，则共有 $s(p-1, k-1)$种;
  2. $p$ 至少和另一个物品在一个循环排列中，则可以通过把 $1, 2, …, p-1$ 排成 $k$ 个循环排列，并把 $p$ 放在 $1, 2, …, p-1$ 任何一个物品的左边得到，因此共有 $(p-1) s(p-1, k)$ 种。

8.3 分拆数

设一个正整数 $n$，若存在正整数集 $\{n_1, n_2,…, n_k\} ( 1≤ k ≤ n，n_i ≤ n)$，使得 $n_1+n_2+…+n_k=n$ ，则称 $\{n_1, n_2,…, n_k\}$ 是 $n$ 的一个分拆(或拆分)。称每个 $n_i$ 为 $n$ 的一个部分（或类）。记 $n$ 的所有包含 $k$ 个部分的不同分拆的个数为 $p_n^k$，$n$ 的所有不同分拆的个数记为 $p_n$，称为 $n$ 的分拆数。
- 二者的关系为：$p_n^1 + p_n^2 + \dots + p_n^n = p_n$
- 拆分中部分的顺序并不重要
$n = na_n + (n-1)a_{n-1} + \dots + 2a_2 + a_1 = n$ 对应 $n$ 的一个分拆记作：$\lambda = n^{a_n} \dots 2^{a_2}1^{a_1}$
分拆数的递推关系：$\sum_{j=1}^{k}p_n^j = p_{n+k}^k, p_n^1 = p_n^n = 1$
求 $p_n^k$：$p_n^k = p_{n-k+k}^k = \sum_{j=1}^kp_{n-k}^j$
定理8.3.1（转换关系）：设 $p_n(r)$ 是最大部分为 $r$ 的 $n$ 的分拆的个数，$q_n(r)$ 是满足分拆各部分不大于 $r$ 的 $n-r$ 的分拆数量，$p_n(r) = q_n(r)$
$Ferrers$ 图：$k$ 行，第 $i$ 行有 $n_i$ 点的左对齐点组
共轭分拆：将分拆 $\lambda$ 的 $Fereers$ 图转置，记为 $\lambda^*$
- 原分拆的行数对应共轭分拆的最大部分
拆分数定理：正整数 $n$ 分成 $k$ 个部分的拆分个数，等于 $n$ 分成以 $k$ 为最大部分的拆分个数
自共轭分拆：$\lambda = \lambda*$
定理8.3.2 设 $n$ 是正整数，设 $p_n^s$ 等于 $n$ 的自共轭分拆数，而 $p_n^t$ 等于分拆成互不相同的若干奇数和的分拆数，则有 \[ p_n^s = p_n^t \]
- 利用 $Ferrers$ 图建立两种分拆的一一对应
定理8.3.3（欧拉恒等式）：设 $n$ 是正整数，设 $p_n^o$ 是把 $n$ 分成奇数和的分拆数， $p_n^d$ 是把 $n$ 分成不同部分的分拆个数。则 \[ p_n^o = p_n^d \]
- 利用 $Ferrers$ 图建立两种分拆的一一对应
计算分拆数的方法：
- 方法一：定理：$n$ 分拆数 $p_n^k$ 满足下列递推关系： \[ \sum_{j=1}^k p_n^i = p_{n+k}^k, p_n^1 = p_n^n = 1 \]
- 方法二：生成函数（见下）
定理8.3.4 数列 $p_0, p_1, …, p_n, …$ 的生成函数是 \[ g(x) = \sum_{n=0}^\infty p_n x^n = \prod_{k=1}^\infty (1-x^k)^{-1} \]
- 证明：由$(1-x^k)^{-1} = 1+x^k+x^{2k}+x^{3k}+\dots+x^{a_k k}+\dots$得 \[ \begin{align} \prod_{k=1}^\infty (1-x^k)^{-1} = &(1+x+x^2+\dots+x^{1a_1}+\dots) \times \\ &(1+x^2+x^4+\dots+x^{2a_2}+\dots) \times \\ &(1+x^k+x^{2k}+\dots+x^{ka_k}+\dots) \times \dots \\ \end{align} \] 每一个项 $x_n$ 由通过从第一个因子选择 $x^{1a_1}$，从第二个因子选择项 $x^{2a_2}$，从第三个因子选择项 $x^{3a_3}$ , $…$ 得到，其中，$1a_1+2a_2+3a_3+… ka_k+… = n (0≤a_i ≤n)$
  
  显然，方程 $(1)$ 的每个正整数解均对应 $n$ 的一个拆分，因此，$x_n$ 的系数，即方程 $(1)$ 的非负整数解的个数，就是 $n$ 的分拆数。
几个特殊的生成函数
- $n$ 分成 $k$ 个部分的分拆数 $p_n^k$ 的生成函数——转化为以 $k$ 为最大部分的拆分个数 \[ g(x)=x^k(1-x)^{-1}(1-x^2)^{-1}...(1-x^k)^{-1} \]
- $n$ 分成奇数和的分拆数 $p_n$ 的生成函数 \[ \begin{aligned} g(x)& =(1-x)^{-1}(1-x^3)^{-1}(1-x^5)^{-1}(1-x^7)^{-1}... \\ &=(1+x+x^2+...+x^{1a_1}+....)\times (1+x^3+x^6+...+x^{3a_2}+....)\times (1+x^5+x^{10}+...+x^{5a_k}+....) \end{aligned} \]
- $n$ 分成互不相等的部分的分拆数 $p_n$ 的生成函数 \[ g(x)=(1+x)(1+x^2)(1+x^3)...(1+x^n)... \]
- $n$ 分成互不相等的奇数部分的分拆数 $p_n$ 的生成函数 \[ g(x)=(1+x)(1+x^3)(1+x^5)...(1+x^{2k-1})... \]

第14章 $Pólya$ 计数

明确给出两种着色方案异同的数学定义

在规定每种颜色出现次数的情况下对着色方案数给出统一的表达式

14.1 置换群与对称群

群的定义：给定集合 $G$ 和 $G$ 上的二元运算 “$•$”，如果以下四个条件满足，则称代数结构 $(G, •)$ 为群:

封闭性、结合律、单位元、逆元
- 群的阶：有限群 $G$ 的元素个数，记为 $|G|$
- 循环群的生成元：$\exists a \in G$，$G$ 中任意元素 $b$ 均可以表示成 $a$ 的方幂，则称 $G$ 为循环群，$a$ 为该群生成元
置换
- 双射
- $S_n$ 为 $X = \{1,2, \dots, n\}$ 的所有 $n!$ 个置换构成的集合
- 是函数，可以合成
  - 先 $f$ 后 $g$ 记作 $g \circ f$，$f$ 的内容是 $i_k$，则 $g \circ f$ 记作 $j_{i_k}$
  - 满足分配律，通常不满足交换律
- 特殊置换
  - 自身合成置换
  - 恒等置换
  - 逆置换
    - 求法：交换上下两行，然后按自然顺序重新排列第一行的整数
置换群：$S_n$ 的非空子集 $G$ 满足如下四个性质，则称为置换的群，简称置换群
- 封闭性、结合律、单位元、逆元
- $S_n$ 称为 $n$ 阶对称群
- 仅含恒等置换的集合 $G = \{ \iota \}$ 是一个置换群
- 置换群满足左消去：$f \circ g = f \circ h$，则 $g = h$
几何图形 $\Omega$ 的对称
- 看作顶点、边以及三维情形下的面上的一个置换
- 对称构成置换群，称为 $\Omega$ 的对称群
  - 顶点对称群 $G_c$
    - $n$ 个旋转
    - $n$ 个反射
      - $n$ 为偶数：$\dfrac{n}{2}$ 个关于对角点的反射，$\dfrac{n}{2}$ 个关于对边中点连线的反射
      - $n$ 为奇数：$n$ 个关于角点与其对边中点的连线的反射
置换群与着色
- 一个着色可由一个对称（置换）得到与其等价的另一个着色
- 定义 $f * c$ 是使 $i_k$ 具有颜色 $c(k)$ 的着色，即 $(f*c)(i_k) = c(k)$
- $(g \circ f)*c = g*(f*c)$
着色等价关系
- $C$ 是 $X$ 的一个着色集合，对于 $G$ 中的任意置换 $f$ 和 $C$ 中任意着色 $c$，$X$ 的着色 $f*c$ 仍属于 $C$
- 定义 $C$ 中关系 $\sim$：设 $c_1, c_2$ 是 $C$ 中的任意两种着色，如果存在 $G$ 中的一个置换 $f$，使得 $f*c_1 = c_2$，则称 $c_1$ 等价于 $c_2$，记为 $c_1 \sim c_2$
  - 满足等价关系的自反性、对称性、传递性
计算非等价的着色数方法：
- $Burnside$ 定理、$Pólya$ 计算公式

14.2 $Burnside$ 定理

稳定核与不变着色集
- 使着色 $c$ 的 $G$ 中所有置换的集合 $G(c) = \{f | f \in G, f*c = c\}, c\in C$，称为 $c$ 的稳定核
  - 任何着色 $c$ 的稳定核也形成一个置换群
- 在置换 $f$ 作用下保持不变的 $C$ 中所有着色的集合 $C(f) = \{c | c \in C, f*c = c\}, f \in G$ 称为 $f$ 的不变着色集
定理14.2.3 ($Burnside$ 定理)：设 $G$ 是 $X$ 的置换群，$C$ 是 $X$ 中一个满足下面条件的着色集合：对于 $G$ 中所有 $f$ 与 $C$ 中所有 $c$，$f∗c$ 仍在 $C$ 中，则 $C$ 中非等价的着色数 $N(G, C)$ 为： \[ N(G,C) = \dfrac{1}{|G|} \sum_{f \in G} |C(f)| = \dfrac{1}{|G|} \sum_{c \in C} |G(c)| \] 即，$C$ 中非等价的着色数等于在 $G$ 中的置换作用下保持不变的着色的平均数。$C(f) = \{c|c \in C, f * c = c\}, f \in G$

具体地，设$G=\{f_1,f_2,\dots,f_n\}$，则$N(G,C) = \dfrac{1}{n} \sum_{i=1}^n |C(f_i)|$
计数非等价的着色数 $N(G,C)$ 的步骤：
- 确定置换群 $G$，确定着色集 $C$
- 计数 $G$ 中每个置换的不变着色集（或每个着色的稳定核）的大小
- 套用公式
例：用红、蓝两种颜色给一个正方形的 $4$ 个顶点着色，试问存在多少种不同的着色方法数
例(循环排列计数) ：把 $n$ 个不同的对象放在一个圆上，有多少种放法

14.3 $Pólya$ 计数

$Burnside$ 定理计数部分比较复杂，仅考虑置换的循环结构并引入有向圈概念

置换循环结构：$f$ 是置换，$D_f = (X, A_f)$ 是顶点集为 $X$ 且边集为 $A_f = \{(i, f(i)) | i \in X\}$ 的有向图
- $D_f$ 有 $n$ 个顶点和 $n$ 条边，且各顶点的入度和出度均为 $1$
- 弧集 $A_f$ 可以被划分为若干个有向圈，且每个顶点恰好属于一个有向圈
循环因子分解
- 循环因子分解是唯一的，但是循环出现的次序可以任意变化
- $1$ 循环也即恒等置换
- 在 $f$ 的循环因子分解中，$X$ 中的每个元素只出现一次
- 例：设 $X=\{1,2,3,4,5,6,7,8\}$ 的置换 $f$ 为：$f=\pmatrix{1&2&3&4&5&6&7&8\\ 6&8&5&4&1&3&2&7}$
  
  $|C(f)|=4^3=64$
定理14.3.1：设 $f$ 是集合 $X$ 的一个置换。假如用 $k$ 种颜色对 $X$ 的元素进行着色。令 $C$ 是 $X$ 的所有着色的集合，则 $f$ 保持 $C$ 中着色不变的着色数为：$|C(f )|=k^{\#(f)}$
- 和循环因子分解中循环个数有关，而与每个循环的阶数无关
置换的类型：$f$ 的循环因子分解中有 $e_1$ 个 $1$ - 循环，$e_2$ 个 $2$ - 循环，$\dots$ $n$ 个 $n$ - 循环，满足 $1e_1+2e_2+...+ne_n=n$，称 $n$ 元组 $(e_1,e_2,...,e_n)$ 是置换 $f$ 的类型，记作 $type(f) = (e_1,e_2,...,e_n)$
置换的单项式：引入 $n$ 个变量 $z_1,z_2,...,z_n$，$z_k$ 对应 $k$ 循环 $(k = 1,2, \dots, n)$，定义 $f$ 的单项式为 $mon(f) = z_1^{e_1}~z_2^{e_2}...z_n^{e_n}$
- 单项式的总次数 $e_1+e_2+...+e_n = \#(f)$
- 按照类型的生成函数是 $G$ 中所有置换的单项式的和 $\sum_{f\in G}mon(f)=\sum_{f\in G}{z_1}^{e_1}{z_2}^{e_2}...{z_n}^{e_n}$，系数对应类型为 $(e_1,e_2, \dots, e_n)$ 的置换的个数
置换的循环指数：$P_G(z_1,z_2,...,z_n)=\dfrac{1}{|G|}\sum_{f\in G}mon(f)=\dfrac{1}{|G|}\sum_{f\in G}{z_1}^{e_1}{z_2}^{e_2}...{z_n}^{e_n}$
- 例：求二面体群 $D_4$ 的循环指数
  
  $P_{D_4}(z_1,z_2,z_3,z_4)=\dfrac{1}{8}(z_1^4+2z_4+3z_2^2+2z_1^2z_2)$
- 用循环指数计算非等价着色数
  - 用 $z_i = k$ 代入 $P_G$ 中
  - $P_G(z_1,z_2,...,z_n)=\dfrac{1}{|G|}\sum_{f\in G}mon(f)=\dfrac{1}{|G|}\sum_{f\in G}{z_1}^{e_1}{z_2}^{e_2}...{z_n}^{e_n}$
  - $|C(f)| =k^{\#(f)} = k^{e_1+e_2+ \dots +e_n} = k^{e_1}k^{e_2} \dots k^{e_n}$
  - $N(G,C)=\dfrac{1}{|G|}\sum_{f\in G}|C(f)| =\dfrac{1}{|G|}\sum_{f\in G}k^{e_1}k^{e_2}\dots k^{e_n} =P_G(k,k,...,k)$w
定理14.3.2：$N(G,C)=P_G(k,k,...,k)$
- 例：求用 $k$ 种颜色对正方形的顶点进行着色的非等价着色数
  - 图略
  - $P_{D_4}(z_1,z_2,z_3,z_4)=\dfrac{1}{8}(z_1^4+2z_4+3z_2^2+2z_1^2z_2)$
  - $N(D_4,C)=P_{D_4}(k,k,k,k)=\dfrac{1}{8}(k^4+2k+3k^2+2k^2k)=\dfrac{1}{8}(k^4+2k^3+3k^2+2k)$
二元变量生成函数：非等价着色数等于 $P_G(r+b, r^2+b^2, \dots, r^n+b^n)$ 中 $r^pb^q$ 的系数
- 例：用 $2$ 种颜色对一个正方形的顶点着色，求它们的非等价着色数的生成函数
  
  $P_{D_4}(z_1,z_2,z_3,z_4)=\dfrac{1}{8}(z_1^4+2z_4+3z_2^2+2z_1^2z_2)$
  
  $\begin{aligned} &P_{D_4}(r+b,r^2+b^2,r^3+b^3,r^4+b^4) \\ &=\dfrac{1}{8}((r+b)^4+2(r^4+b^4)+3(r^2+b^2)^2+2(r+b)^2(r^2+b^2)) \\ &=r^4+r^3b+2r^2b^2+r b^3+b^4. \end{aligned}$
$Pólya$ 定理：$\{u_1,u_2,\ldots,u_k\}$ 是 $k$ 种颜色的一个集合，则针对各颜色数目的 $C$ 的非等价着色数的生成函数是由循环指数 $P_G(z_1,z_2,...,z_n)$ 通过做变量代换 $z_j=u_1^j+u_2^j+...+u_k^j(j=1,2,...,n)$ 得到的表达式 $P_G(u_1+u_2+\text{...}+u_k,u_1^2+u_2^2+\text{...}+u_k^2,\text{...},u_1^n+u_2^n+\text{...}+u_k^n)$
- $u_1^{p_1}u_2^{p_2}...u_k^{p_k}$ 的系数等于 $X$ 中的 $p_1$ 个元素着色成 $u_1$，$p_2$ 个元素着色成 $u_2$，$\dots$，$p_k$ 个元素着色成 $u_k$ 的非等价的着色数
- 例：用 $3$ 种颜色对一个正方形的顶点着色，求它们的非等价着色数的生成函数
  
  $P_{D_4}(z_1,z_2,z_3,z_4)=\dfrac{1}{8}(z_1^4+2z_4+3z_2^2+2z_1^2z_2)$
  
  $\begin{aligned} &P_{D_4}(r+b+g,r^2+b^2+b^2,r^3+b^3+g^3,r^4+b^4+g^4) \\ &=\dfrac{1}{8}((r+b+g)^4+2(r^4+b^4+g^4)+3(r^2+b^2+g^2)^2+2(r+b+g)^2(r^2+b^2+g^2)) \\ \end{aligned}$