离散数学III

排列与组合

基本计数原理

加法原理与乘法原理（略）

减法原理与除法原理

集合的排列

集合的线性排列：

定义：从n哥不同元素取出r个元素有序摆放，称n元素集合的r-排列
集合S的一个排列时某种顺序列出S的所有元素。（称为全排列）

定理：对于整数n和r， $r\leq n$ ，有 $P(n,r)=\frac{n!}{(n-r)!}$

$P(n,r)=n*P(n-1,r-1)$

$P(n,r)=P(n-1,r)+r*P(n-1,r-1)$

循环排列：

定理：n个元素集合的循环r排列个数为： $\frac{P(n,r)}{r}=\frac{n!}{r(n-r)!}$
特别地，n元素的循环排列个数为 $(n-1)!$

项链排列：

n个元素集合串起来循环r排列数为 $\frac{P(n,r)}{2r}=\frac{n!}{2r(n-r)!}$

集合的组合

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

$C(n,r)=C(n,n-r)$

$C(n,r)*C(n,k)=C(n,k)*C(n-k,r-k)$

$ \binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \dots + \binom{n}{n} = 2^n $

多重集的排列

多重集：允许元素重复。例如 $M=\{a,a,b,c,c,c\}=\{2a,1b,3c\}$

无限重复数

定理：令S是多重集，它有k种不同的元素，每个元素都有无限重复次数，那么，S的r-排列个数为 $k^r$

有限重复数

定理：令S是多重集，它有k种不同的元素，每种元素的重复数分别为 $n_1,n_2,...,n_k$ ，那么，S的排列数等于 $\frac{n!}{n_1!n_2!...n_k!}$ ，其中 $n=n_1+n_2+...+n_k$

定理：设 $n=n_1+n_2+...+n_k$ ，将n个元素集合划分为做了标签的k个盒子 $B_1,B_2,...,B_k$ ，其中 $B_i$ 盒子含有 $n_i$ 个元素，方法数为 $\frac{n!}{n_1!...n_k!}$

多重集的组合

多重集S的一个r-组合是S 的子多重集。

定理：令S是多重集，它有k个不同的元素，每个元素都有无线重复次数，那么，S的r-组合个数为 $\binom{r+k-1}{r}=\binom{r+k-1}{k-1}$

有元素约束问题？例：方程 $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.$

n个元素	r排列问题（choose a list）	r组合问题（choose a set）
无重复	$P(n,r)$	$C(n,r)$
允许重复（无限）	$n^r$	$C(n+r-1,r)$

$n_1+...n_k=r$ 的非负整数解个数为 $C(k+r-1,k-1)$
$n_1+...n_k=r$ 的正整数解个数为 $C(r-1,k-1)$

有限概率

相对于微积分为基础的连续概率。

鸽巢原理

鸽巢原理的简单形式

略。

鸽巢原理的加强形式

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

或者第1个盒子至少含有 $q_1$ 个物体，
或者第2个盒子至少含有 $q_2$ 个物体，…
或者第n个盒子至少含有 $q_n$ 个物体。

简单形式：当 $q_1=q_2=...q_n=2$ ，有 $q_1+q_2+...+q_n-n+1=n+1$

推论：设n和r都是正整数。如果 $n(r-1)+1$ 个物体放入n个盒子，则至少有一个盒子含有r个或更多的物体。

平均原理：如果n个非负整数 $m_1,m_2,...m_n$ 的平均数大于 $r-1$ ，即 $(m_1+m_2+...+m_n)/n>r-1$ ，则是稍有一个整数大于或等于 $r$ 。

Ramsey定理

如果 $m\geq 2,n\geq 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)$ 一定存在（ $m\geq 2,n\geq 2$ 是两个整数）
$r(m,n)=r(n,m)$

平凡的Ramsey数：

$r(2,n)=n$
$r(m,2)=m$

推论： $r(m,n)\leq r(m-1,n)+r(m,n-1)$

Ramsey定理推广

Ramsey定理可推广到任意多种颜色的情况

$l$ 种颜色：如果 $n_1,n_2,...,n_l$ 都是大于或等于2的整数，则一定存在正整数 $p$ ，使得 $K_p\rightarrow K_{n_1},K_{n_2},...K_{n_l}$ ，满足以上条件的最小整数 $p$ 成为Ramsey数 $r(n_1,n_2,...,n_l)$

例如： $K_{17}\rightarrow K_3,K_3,K_3$

Ramsey定理更一般形式

把点对（边）扩展至t个元素的子集（ $t\geq 2$ ）：
给定整数 $t\geq 2$ 及整数 $q_1,q_2,...,q_k\geq t$ ，则存在一个整数 $p$ 使得：如果将 $p$ 元素集合种每一个 $t$ 元素子集指定为 $k$ 种颜色 $c_1,c_2,...,c_k$ 中一种，那么：

或者存在 $q_1$ 个元素，它的所有 $t$ 自己被指定成颜色 $c_1$ ，
…
或者存在 $q_k$ 个元素，它的所有 $t$ 自己被指定成颜色 $c_k$ .

满足结论的最小整数 $p$ 为Ramsey数 $r_t(q_1,q_2,...,q_k)$

令 $K_n^t$ 表示n个元素集合中所有t个元素的子集的集合。
给定整数 $t\geq 2$ 及整数 $q_1,q_2,...,q_k\geq t$ ，存在一个整数 $p$ ，使得 $K_p^t\rightarrow K_{q_1}^t,K_{q_2}^t,...,K_{q_k}^t$

生成排列和组合

生成排列

递归生成算法
邻位对换算法
多重集排列生成算法

递归生成算法

{1}的所有排列->{1,2}的所有排列->…{1,2,…,n}的所有排列

邻位对换算法

初始 $123...n$
while存在活动整数时，do
- 求出最大的活动整数m
- 交换m和其箭头指向的相邻整数的位置
- 改变所有满足p>m的整数p的箭头方向
不存在活动整数时，算法结束

多重集排列生成算法

字典序算法：next_permutation

适用于多重集。

从右向左找第一队“升序”相邻元素：找到最大的 $i$ 满足 $A[i]<A[i+1]$ 。如果没有，说明已经是最大字典序，结束
在 $i$ 的右侧找最后一个比 $A[i]$ 大的数：找到最大的 $j$ ，满足 $A[j]>A[i]$ 。
交换 $A[i]$ 与 $A[j]$ 。
反转：将 $A[i+1]...A[n]$ 反转为 $A[n]...A[i+1]$ ，使其变为升序。

排列中的逆序

逆序：（前>后）
例：31524中几组逆序？有(3,1),(3,2),(5,2),(5,4)

一个排列和一个逆序列一一对应。

已知 ${1,2,...,8}$ 的一个排列的逆序列位53402110，确定此排列：

0 -> 8:8
1 -> 7:87
1 -> 6:867
2 -> 5:8657
0 -> 4:48657
4 -> 3:486537
3 -> 2:4862537
5 -> 1:48625137

生成组合

压缩序
反射Gray码

压缩序

二进制加法。

n元集合 $S=\{x_{n-1},x_{n-2},...,x_0\}$ 的组合与长度为n的二进制数一一对应

初始： $a_{n-1}...a_1a_0=0...00$
当 $a_{n-1}...a_1a_0\neq 1...11$ 时，执行以下操作：
- 求出使得 $a_j=0的最小整数$ j$$
- 用1替换 $a_j$ 并用0替换每个 $a_{j-1},...,a_0$
当 $a_{n-1}...a_1a_0=1...11$ 时算法结束

反射Gray码

相邻的组合仅相差一个元素。

初始： $a_{n-1}...a_1a_0=0...00$
当 $a_{n-1}...a_1a_0\neq 1...00$ 时，进行以下操作：
- 计算 $\sigma(a_{n-1}...a_1a_0)=a_{n-1}+...+a_1+a_0$
- 如果 $\sigma(a_{n-1}...a_1a_0)$ 是偶数，则改变 $a_0$ （01互换）
- 否则，确定 $j$ ，使得 $a_j=1$ 且对于所有 $i<j$ ， $a_i=0$ ，然后改变 $a_{j+1}$

称为逐次法。

生成r组合

基于字典序的r子集生成算法。

// 初始化下标数组 a[1..r]，存储当前子集元素下标
for i ← 1 to r do
    a[i] ← i
end for

输出 a[1..r]

while true do
    // 从后往前找第一个可增大的位置 i
    i ← r
    while i ≥ 1 and a[i] = n - r + i do
        i ← i - 1
    end while

    // 无下一个子集，退出
    if i = 0 then
        break
    end if

    // 增大当前位
    a[i] ← a[i] + 1

    // 后续位依次递增
    for j ← i + 1 to r do
        a[j] ← a[j-1] + 1
    end for

    输出 a[1..r]
end while

二项式系数

帕斯卡三角形

对于满足 $1\leq k\leq n$ 的所有整数 $k$ 和 $n$ ，有 $\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$

(n元素集合的k子集的数目=n-1元素集合的k子集的数目+n-1元素集合的k-1子集的数目)

Pascal三角形

每一行相加（第n行）： $\binom{n}{0}+\binom{n}{1}+...\binom{n}{n}=2^n$

第k=1列：n

第k=2列：三角形数，即三角形阵列中的点数 $\binom{n}{2},n\geq 2$

第k=3列：四面体数，即四面体阵列中的点数 $\binom{n}{3}$

二项式系数的另一种组合解释

$p(n,k)$ ：从 $\binom{0}{0}$ 到 $\binom{n}{k}$ 项的路径数目

二项式定理

令 $n$ 是一个正整数，那么对于所有的 $x,y$ 有： $(x+y)^n=\sum^{n}_{k=0}\binom{n}{k}x^{n-k}y^k$

$k\binom{n}{k}=n\binom{n-1}{k-1}$

例：n个人中选k人组成队伍，其中一人为队长，有多少种选法？先选队员，其中选队长 $k\binom{n}{k}$ ，先选队长再选队员 $n\binom{n-1}{k-1}$

证明等式方法：帕斯卡公式，求导法，积分法，组合推理法

等式举例

对于 $0\leq k\leq n$ ，有 $\sum^{n}_{m=k}\binom{m}{k}=\binom{k}{k}+\binom{k+1}{k}+...+\binom{n}{k}=\binom{n+1}{k+1}$

对于 $0\leq k\leq n/2$ ，有 $\sum^{n-k}_{m=k}\binom{m}{k}\binom{n-m}{k}=\binom{n+1}{2k+1}$

$\binom{m+n}{r}=\binom{m}{0\binom{n}{r}+\binom{m}{1}\binom{n}{r-1}+...+\binom{m}{r}\binom{n}{0}$

组合定义扩展

$\binom{n}{k}=\frac{n!}{k!(n-k)}$ ，n为任意实数，k为任意整数（若k=0，原式=1，若k≤-1，原式=0）

二项式系数的单峰性

多项式定理

牛顿二项式定理

容斥原理

定理：集合S不具有性质 $P_1,P_2,...,P_m$ 的物体的个数：

|\overline{A_1} \cap \cdots \cap \overline{A_m}| = |S| - \sum|A_i| + \sum|A_i \cap A_j| - \sum|A_i \cap A_j \cap A_k| + \dots + (-1)^m|A_1 \cap A_2 \cap \dots \cap A_m|

其中，第一个和对 $\{1,2,\dots,m\}$ 的所有的1子集 $\{i\}$ 进行，第二个和对 $\{1,2,\dots,m\}$ 的所有的2子集 $\{i,j\}$ 进行，依此类推。

推论：集合S中至少具有性质 $P_1,P_2,...,P_m$ 之一的物体的个数：

|A_1 \cup A_2 \cup \dots \cup A_m| = \sum|A_i| - \sum|A_i \cap A_j| + \sum|A_i \cap A_j \cap A_k| + \dots + (-1)^{m+1}|A_1 \cap A_2 \cap \dots \cap A_m|

特殊情况：任意k各级和的交包含相等个数的元素，k=1,2,…,n

\left| \overline{A}_1 \cap \overline{A}_2 \cap \dots \cap \overline{A}_m \right| = \alpha_0 - \binom{m}{1}\alpha_1 + \binom{m}{2}\alpha_2 - \binom{m}{3}\alpha_3 + \dots + (-1)^k \binom{m}{k}\alpha_k + \dots + (-1)^m \binom{m}{m}\alpha_m

带重复的组合

例：确定多重集 $T=\{3a,4b,5c\}$ 的10子集的个数。
设：令多重集 $T^\star = \{\infin a, \infin b, \infin c\}$ 的所有10子集的集合为 $S$ . $A_1$ 是 $S$ 中包含多于3个 $a$ 的10子集的集合； $A_2$ 是 $S$ 中包含多于4个 $b$ 的10子集的集合； $A_3$ 是 $S$ 中包含多于5个 $c$ 的10子集的集合；
则 $T$ 的10-组合数等于 $\left| \overline{A}_1 \cap \overline{A}_2 \cap \overline{A}_3 \right| = 66 - 28 - 21 - 15 + 3 + 1 + 0 - 0 = 6$

令 $S=\{\infty \cdot a_1, \infty \cdot a_2, \dots, \infty \cdot a_k\}$ ，则 $S$ 的一个 $r$ 组合具有形式
$\{x_1 \cdot a_1, x_2 \cdot a_2, \dots, x_k \cdot a_k\}$ ，满足

x_1 + x_2 + \dots + x_k = r \quad (1),

其中， $x_i$ 是非负整数，即 $x_i \ge 0, i=1, 2, \dots, k$ 。

以上方程的任何一个解确定 $S$ 的一个 $r$ 组合，反之亦然.
因此， $S$ 的 $r$ 组合个数等于方程(1)的非负整数解的个数.

多重集 $T=\{n_1 \cdot a_1, n_2 \cdot a_2, \dots, n_k \cdot a_k\}$ 的 $r$ 组合数等于方程

x_1 + x_2 + \dots + x_k = r, \quad 0 \le x_1 \le n_1, 0 \le x_2 \le n_2, \dots, 0 \le x_k \le n_k

的整数解的个数。

例2: 求满足 $1 \le x_1 \le 5$ , $-2 \le x_2 \le 4$ , $0 \le x_3 \le 5$ , $3 \le x_4 \le 9$ 的方程

x_1 + x_2 + x_3 + x_4 = 18

的整数解个数。

解: 作变量替换 $y_1 = x_1 - 1$ , $y_2 = x_2 + 2$ , $y_3 = x_3$ , $y_4 = x_4 - 3$ 得到方程：

y_1 + y_2 + y_3 + y_4 = 16 \quad (*)

且关于 $x_i$ 的不等式成立，当且仅当

0 \le y_1 \le 4, \ 0 \le y_2 \le 6, \ 0 \le y_3 \le 5, \ 0 \le y_4 \le 6。 \quad (**)

因此满足题意的整数解个数等于当条件（**）满足时，
方程（*）的整数解的个数。

令 $A_1, A_2, A_3, A_4$ 分别表示方程（）在 $y_1 \ge 5, \ y_2 \ge 7,$
$y_3 \ge 6, \ y_4 \ge 7$ 时的整数解的个数，则条件（**）满足时，
方程（）的整数解的个数为 $|\overline{A}_1 \cap \overline{A}_2 \cap \overline{A}_3 \cap \overline{A}_4|$ 。

设 $S$ 是方程(*)的非负整数解的集合，则 $|S|$ 等
于方程 $y_1 + y_2 + y_3 + y_4 = 16$ 的非负整数解的个数，得

|S| = \binom{16 + 4 - 1}{16} = \binom{19}{16} = 969

错位排列

定义: 设 $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$ 表示错位排列个数。

定理：对 $n \ge 1$ ，

D_n = n! \left( 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots + (-1)^n \frac{1}{n!} \right)

例2:在一次聚会上，7位绅士存放他们的帽子。有多少种方法使得他们的帽子返还时满足
(1) 没有绅士收到他自己的帽子？
(2) 至少一位绅士收到他自己的帽子？
(3) 至少两位绅士收到他们自己的帽子？

解:
(1) $D_7$
(2) $7! - D_7$
(3) $7! - D_7 - 7D_6$

错位排列的递推关系:

$D_n = (n-1)( D_{n-2} + D_{n-1} ), \quad (n=3, 4, \dots)$ ，初始值 $D_2=1; \ D_1=0$

$D_n = nD_{n-1} + (-1)^n$

带有禁止位置的排列

令 $X_1, X_2, \dots, X_n$ 是 $\{1, 2, \dots, n\}$ 的子集 (可以为空集)，
用 $P(X_1, X_2, \dots, X_n)$ 表示 $\{1, 2, \dots, n\}$ 的排列 $i_1 i_2 \dots i_n$ 的
集合，使得： $i_1 \notin X_1, \ i_2 \notin X_2, \ \dots,$ 且 $i_n \notin X_n$

记 $p(X_1,X_2,...,X_n) = | P(X_1,X_2,...,X_n) |$ ，表示 $P(X_1,X_2,...,X_n)$ 中排列的个数

例: $X_1 = \{1, 2\}, X_2 = \{2, 3\}, X_3 = \{3, 4\}, X_4 = \{4, 1\}$ 是 $\{1, 2, 3, 4\}$ 的子集，求 $p(X_1, X_2, X_3, X_4)$ 。
解: 设集合 $\{1, 2, 3, 4\}$ 的一个排列为 $i_1 i_2 i_3 i_4$ ， $A_j$ 表示 $i_j \in X_j$ 的排列的集合， $j=1, 2, 3, 4$ ，则

p(X_1, X_2, X_3, X_4) = |\overline{A_1} \cap \overline{A_2} \cap \overline{A_3} \cap \overline{A_4}|。

令 $S$ 表示 $\{1, 2, 3, 4\}$ 的所有排列的集合，则 $|S|=4!$ 。

|A_1| = \binom{2}{1} 3! = |A_2| = |A_3| = |A_4|,

|A_1 \cap A_2| = (2+1) 2! = |A_1 \cap A_4| = |A_2 \cap A_3| = |A_3 \cap A_4|

|A_1 \cap A_3| = \binom{2}{1} \binom{2}{1} 2! = |A_2 \cap A_4|。

$|A_i \cap A_j \cap A_k| = \dots$ （略）。

定理：将 $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

另一个禁止位置问题

令 $S$ 为 $\{1, 2, \dots, n\}$ 的全部排列，
$Q_n$ 是 $S$ 中没有 $12, 23, \dots, (n-1)n$ 这些模式的排列的个数。
令 $A_i$ 是 $i(i+1)$ 出现的排列的集合， $i=1, 2, \dots, n-1$ ，则有

Q_n = |\overline{A_1} \cap \overline{A_2} \cap \dots \cap \overline{A_{n-1}}|

定理：对于 $n \ge 1$ ,

\begin{aligned} \mathbf{Q_n} &= n! + \sum_{k=1}^{n-1} (-1)^k \binom{n-1}{k} (n-k)! \\ &= n! - \binom{n-1}{1} (n-1)! + \binom{n-1}{2} (n-2)! + \dots \\ &\quad + (-1)^{n-1} \binom{n-1}{n-1} 1! \end{aligned}

递推关系和生成函数

若干函数

斐波那契序列

f_n = \frac{1}{\sqrt{5}} \left( \frac{1+\sqrt{5}}{2} \right)^n - \frac{1}{\sqrt{5}} \left( \frac{1-\sqrt{5}}{2} \right)^n, n \ge 0

性质：
(1) 斐波那契数列的部分和为

s_n = f_0 + f_1 + \dots + f_n = f_{n+2} - 1

(2) 斐波那契数是偶数当且仅当n被3整除。

(3) 斐波那契数能被3整除当且仅当n可被4整除。

(4) 斐波那契数能被4整除当且仅当n可被6整除。

生成函数

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

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

数列与生成函数的关系：多重集组合

设 $k$ 是正整数， $g(x)$ 是数列 $h_0,h_1,...,h_n,...$ 的生成函数，其中 $h_n$ 等于方程 $e_1+e_2+...+e_k = n$ 的非负整数解个数。

g(x) = \sum^{\infin}_{n=0} \binom{n+k-1}{n} x^n = \frac{1}{(1-x)^k} \\ =(\sum^{\infin}_{e_1=0}x^{e_1})(\sum^{\infin}_{e_2=0}x^{e_2})...(\sum^{\infin}_{e_k=0}x^{e_k}) \\ =\sum^{\infin}_{e_1+...+e_k=n=0}x^{e_1}x^{e_2}...x^{e_k}

合并同次项后， $x^n$ 前的系数即为 $h_n$

例：设 $S$ 是多重集合 $\{\infin a_1,\infin a_2,\infin a_3,\infin a_4\}$ 。
当 $h_n$ 是满足以下约束的 $S$ 的 $n$ 组合数是，求解数列 $h_0,h_1,...,h_n,...$ 的一般项 $h_n$ .
元素 $a_1$ 不会出现, $a_2$ 至多出现1次

解:生成函数为 $g(x)=x^0(1+x)(1+x+x^2+...+x^n+...)^2 \\ = (1+x)(\frac{1}{1-x})^2 \\ = \frac{-1}{1-x} + \frac{2}{(1-x)^2} \\ = -\sum^{\infin}_{k=0}x^k + \sum^{\infin}_{k=0}2\binom{2+k-1}{k}x^k \\ =\sum^{\infin}_{k=0}(2k+1)x^k$

得一般项 $h_n = 2n+1, n\geq 0$

例子：什么样得数列的生成函数是如下式子：
$(1+x+x^2+x^3+x^4+x^5)(1+x+x^2)(1+x+x^2+x^3+x^4) \\ = (\sum^{5}_{e_1=0}x^{e_1})(\sum^{2}_{e_2=0}x^{e_2})(\sum^{4}_{e_3=0}x^{e_3})$

解：设 $e_1+e_2+e_3=n$ ,则有 $x^{e_1}x^{e_2}x^{e_3}=x^n$
因此乘积中 $x_n$ 的系数 $h_n$ 是 $e_1+e_2+e_3=n$ 的非负整数解的个数，其中 $0\leq e_1\leq 5,0\leq e_2\leq 2,0\leq e_3\leq 4$
注意：若 $n>5+2+4=11$ ,则 $h_n=0$

例：设 $h_n$ 是方程 $3e_1+4e_2+2e_3+5e_4=n$ 的非负整数解的个数，求序列 $h_0, h_1, \dots, h_n, \dots$ 的生成函数。

作变量替换 $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{aligned} g(x) &= (1+x^3+x^6+\dots)(1+x^4+x^8+\dots)(1+x^2+x^4+\dots)(1+x^5+x^{10}+\dots) \\ &= \frac{1}{1-x^3} \cdot \frac{1}{1-x^4} \cdot \frac{1}{1-x^2} \cdot \frac{1}{1-x^5} \end{aligned}

排列逆序：

设 $h(n,t)$ 表示 $\{1,2,...,n\}$ 的排列中有 $t$ 个你学的排列数目，则

对于 $0\leq t\leq n(n-1)/2$ ，有 $h(n,t)\geq 1$
对 $t>n(n-1)/2$ ，有 $h(n,t)=0$

定理：设 $n$ 是正整数，则数列 $h(n,0),h(n,1),...,h(n,n(n-1)/2)$ 的生成函数为

g_n(x) = 1(1+x)(1+x+x^2)\dots(1+x+\dots+x^{n-1}) = \frac{\prod_{j=1}^n(1-x^j)}{(1-x)^n} \quad

指数生成函数

数列 $h_0,h_1,h_2,...,h_n...$ 的指数生成函数定义为

g^{(e)}(x)=h_0+h_1x+h_2\frac{x^2}{2!}+...+h_n\frac{x^n}{n!}+... \\= \sum^{\infin}_{n=0}h_n\frac{x^n}{n!}

例：数列 $1,1,1,...,1,...$ 的指数生成函数 $g^{(e)}(x)=\sum^{\infin}_{n=0}\frac{x^n}{n!}=e^x$

例：求多重集合 $S=\{\infin a_1,\infin a_2,...,\infin a_k\}$ 的 $n$ 排列数 $h_n$ 的数列 $h_1,h_2,...$ 的指数生成函数。

$h_n = k^n$

$g^{(e)}(x)=\sum^{\infin}_{n=0}\frac{(kx)^n}{n!}=e^{kx}$

数列与指数生成函数的关系：多重集排列

例：有多重集合$S={3 a_1,2 a_2,3 a_3} $，从中取$ r $组合，其组合数为$ h_r $，则其对应的生成函数为$ g(x) = (1+x+x^2+x3)(1+x+x^2)(1+x+x2+x^3) = 1+3x+6x^2+9x3+10x^4+9x5+6x^6+3x7+x^8$

$r$ 组合的数目： $x^r$ 的系数

问题：如何取组合？

定理：设 $S$ 是多重集 $\{n_1 \cdot a_1, n_2 \cdot a_2, \dots, n_k \cdot a_k\}$ ，其中 $n_1, n_2, \dots, n_k$ 是非负整数。设 $h_n$ 是 $S$ 的 $n$ 排列数，则数列 $h_0, h_1, h_2, \dots, h_n, \dots$ 的指数生成函数 $g^{(e)}$ 为：

g^{(e)} = f_{n_1}(x) f_{n_2}(x) \dots f_{n_k}(x) \quad (1)

其中，对于 $i=1, 2, \dots, k$ ，有

f_{n_i}(x) = 1 + x + \frac{x^2}{2!} + \dots + \frac{x^{n_i}}{n_i!} \quad (2)

推广到无穷重数的情况：对 $\{\infin \cdot a_1, \infin \cdot a_2, \dots, \infin \cdot a_k\}$

$g^{e}(x)=h_0+h_1x+h_2\frac{x^2}{2!}+ \dots + h_n\frac{x^n}{n!}+ \dots \\= f_{\infin}(x) \dots f_{\infin}(x)$ ,其中 $f_{\infin}(x)=1+x+\frac{x^2}{2!}+ \dots + \frac{x^n}{n!} + \dots = e^x$

当 $n$ 排列中 $a_i$ 的出现有约束时，将反映到第 $i$ 个因子中

组合问题使用普通生成函数，排列问题是用指数生成函数。

几个常用的展开式

e^x = \sum_{n=0}^{\infty} \frac{x^n}{n!} = 1 + x + \frac{x^2}{2!} + \dots + \frac{x^n}{n!} + \dots

e^{-x} = \sum_{n=0}^{\infty} (-1)^n \frac{x^n}{n!} = 1 - x + \frac{x^2}{2!} + \dots + (-1)^n \frac{x^n}{n!} + \dots

\frac{1}{2} (e^x + e^{-x}) = 1 + \frac{x^2}{2!} + \frac{x^4}{4!} + \dots + \frac{x^{2n}}{(2n)!} + \dots

\frac{1}{2} (e^x - e^{-x}) = x + \frac{x^3}{3!} + \frac{x^5}{5!} + \dots + \frac{x^{2n+1}}{(2n+1)!} + \dots

例：用红、蓝、黄三种颜色给 $1 \times n$ 的棋盘着色，如果被着成红色的方格数是偶数，确定给这个棋盘着色的方法数 $h_n$ 。

解：设 $h_n$ 表示着色的方法数，定义 $h_0=1$ 。
显然， $h_n$ 等于包含 3 种颜色的多重集合的 $n$ 排列数，其中每种颜色的重数是无穷的，且红色出现的次数是偶数。

因此，数列 $h_0, \dots, h_n, \dots$ 的指数生成函数为

\begin{aligned} g^{(e)} &= \left(1 + \frac{x^2}{2!} + \frac{x^4}{4!} + \dots\right) \left(1 + \frac{x}{1!} + \frac{x^2}{2!} + \dots\right) \left(1 + \frac{x}{1!} + \frac{x^2}{2!} + \dots\right) \\ &= \frac{1}{2}(e^x + e^{-x}) e^x e^x = \frac{1}{2}(e^{3x} + e^x) = \frac{1}{2}\left(\sum_{n=0}^{\infty} 3^n \frac{x^n}{n!} + \sum_{n=0}^{\infty} \frac{x^n}{n!}\right) \\ &= \sum_{n=0}^{\infty} \frac{1}{2}(3^n + 1) \frac{x^n}{n!} \text{。} \quad \text{得 } h_n = \frac{3^n+1}{2}, n \ge 0 \text{。} \end{aligned}

例：确定满足下面条件的 $n$ 位数的个数 $h_n$ ：每个数字都是奇数且数字 1 和 3 出现偶数次。

解：设 $h_0=1$ ， $h_n$ 等于多重集合 $\{\infty \cdot 1, \infty \cdot 3, \infty \cdot 5, \infty \cdot 7, \infty \cdot 9\}$ 的 1和3出现偶数次的 $n$ 排列个数。
则 $h_0, h_1, h_2, \dots, h_n, \dots$ 的指数生成函数为

\begin{aligned} g^{(e)} &= \left(1 + \frac{x^2}{2!} + \frac{x^4}{4!} + \dots\right)^2 \left(1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \dots\right)^3 \\ &= \left(\frac{e^x + e^{-x}}{2}\right)^2 e^{3x} = \frac{1}{4}(e^{5x} + 2e^{3x} + e^x) \\ &= \frac{1}{4} \left( \sum_{n=0}^{\infty} 5^n \frac{x^n}{n!} + 2\sum_{n=0}^{\infty} 3^n \frac{x^n}{n!} + \sum_{n=0}^{\infty} \frac{x^n}{n!} \right) \\ &= \sum_{n=0}^{\infty} \left( \frac{5^n + 2 \times 3^n + 1}{4} \right) \frac{x^n}{n!} \qquad \text{得，} h_n = \frac{5^n + 2 \times 3^n + 1}{4}, n \ge 0 \end{aligned}

求解线性齐次递推关系

特征方程法
生成函数法

特征方程法

定理：令 $q$ 为一个非零数，则 $h_n = q^n$ 是常系数线性齐次递推关系

h_n = a_1 h_{n-1} + a_2 h_{n-2} + \dots + a_k h_{n-k} \quad (a_k \neq 0, n \ge k) \quad (1)

的解当且仅当 $q$ 是多项式方程（即 特征方程）

x^k - a_1 x^{k-1} - a_2 x^{k-2} - \dots - a_{k-1} x - a_k = 0 \quad (2)

的一个根。（即 特征根）

若多项式方程 (2) 有 $k$ 个不同的根 $q_1, q_2, \dots, q_k$ ，则

h_n = c_1 q_1^n + c_2 q_2^n + \dots + c_k q_k^n \quad (3)

是下述意义下(1)的通解：任意给定初始值 $h_0, h_1, \dots, h_{k-1}$ ，都存在 $c_1, c_2, \dots, c_k$ 使得(3)式是满足(1)式和初始条件的唯一的数列。

例：求满足初始值 $h_0=1, h_1=2$ 和 $h_2=0$ 的递推关系 $h_n=2h_{n-1}+h_{n-2}-2h_{n-3} \ (n \ge 3)$

解：递推关系的特征方程为 $x^3-2x^2-x+2=0 \quad \mathbf{(1)}$

3个根分别是 1, -1, 2.

因此，通解为 $h_n=c_1 1^n+c_2(-1)^n+c_3 2^n$

代入初始值解得 $c_1=2, c_2=\frac{2}{3}, c_3=-\frac{1}{3}$ ,

因此， $h_n = 2 - \frac{2}{3}(-1)^n - \frac{1}{3} \cdot 2^n \quad (n \ge 0)$

生成函数法

1.利用递推关系求出序列的生成函数： $\frac{p(x)}{q(x)}$

其中， $p(x)$ 是次数小于 $k$ 的多项式
$q(x)$ 是常数项等于 $1$ 的 $k$ 阶多项式

2.用部分分式法，把 $\frac{p(x)}{q(x)}$ 表示为如下代数分式的和： $\frac{c}{(1-rx)^t}$

3.利用牛顿二项式展开 $\frac{c}{(1-rx)^t}$ ，并把所有项求和，得到生成函数的幂级数

例：利用生成函数求解 $h_n=h_{n-1}+9h_{n-2}-9h_{n-3} \ (n \ge 3), \ h_0=0, h_1=1, h_2=2$

解：令生成函数为 $g(x) = h_0 + h_1x + h_2x^2 + h_3x^3 + \dots + h_nx^n + \dots \quad (1)$

将 (1) 式两边分别同乘 $-x, -9x^2, 9x^3$ ，得：

\begin{aligned} -x \cdot g(x) &= -h_0x - h_1x^2 - h_2x^3 - \dots - h_n x^{n+1} + \dots \quad (2) \\ -9x^2 \cdot g(x) &= \quad \quad \ -9h_0x^2 - 9h_1x^3 - 9h_2x^4 - \dots - 9h_n x^{n+2} + \dots \quad (3) \\ 9x^3 \cdot g(x) &= \quad \quad \quad \quad \quad 9h_0x^3 + 9h_1x^4 + 9h_2x^5 + \dots + 9h_n x^{n+3} + \dots \quad (4) \end{aligned}

将 (1), (2), (3) 与 (4) 四式左右两边分别相加得：

\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^3 + \dots \\ &= h_0 + (h_1 - h_0)x + (h_2 - h_1 - 9h_0)x^2 = x + x^2 \text{。} \end{aligned}

得 $g(x) = \frac{x + x^2}{1 - x - 9x^2 + 9x^3} = \frac{x + x^2}{(1-x)(1-3x)(1+3x)}$ （略）

特征方程有重根的情形

定理：令 $q_1, q_2, \dots, q_t$ 为常系数线性齐次递推关系：

h_n = a_1 h_{n-1} + a_2 h_{n-2} + \dots + a_k h_{n-k} \quad (n \ge k) \quad (1)

的特征方程的互异的根。

如果 $q_i$ 是 (1) 的特征方程的 $s_i$ 重根，那么该递推关系的通解中对应于 $q_i$ 的部分为：

H_n^{(i)} = c_1 q_i^n + c_2 n q_i^n + \dots + c_{s_i} n^{s_i-1} q_i^n

（即 $s_i$ 项的和），且该递推关系的通解为：

h_n = H_n^{(1)} + H_n^{(2)} + \dots + H_n^{(t)}

一般的：数列与生成函数关系

定理：令 $h_0, h_1, h_2, \dots, h_n, \dots$ 为满足 $k$ 阶常系数线性齐次递推关系：

h_n + c_1 h_{n-1} + \dots + c_k h_{n-k} = 0 \quad (c_k \neq 0, n \ge k) \quad (1)

的数列，则它的生成函数 $g(x)$ 形如：

g(x) = p(x) / q(x) \quad (2)

其中，
$q(x)$ 是具有非零常数项的 $k$ 次多项式，
$p(x)$ 是小于 $k$ 次的多项式。

反之，给定这样的多项式 $p(x)$ 和 $q(x)$ ，则存在序列 $h_0, h_1, \dots, h_n, \dots$ 满足 (1) 式的 $k$ 阶常系数线性齐次递推关系，其生成函数由 (2) 式给出。

小结

令 $h_0, h_1, h_2, \dots, h_n, \dots$ 是一个数列，若存在常数量 $a_1, a_2, \dots, a_k \ (a_k \neq 0)$ 使得
$h_n = a_1 h_{n-1} + a_2 h_{n-2} + \dots + a_k h_{n-k} \quad (n \ge k)$
则称该数列是 $k$ 阶常系数线性齐次递推关系。

利用特征方程求解常系数线性齐次递推关系：
1. 写出相应的特征方程；
2. 求解特征方程：
(a) 如果没有重根，则直接给出通解
(b) 如果有重根，根据重根求出通解
3. 将初始条件代入通解，得到满足初始条件的解。
利用生成函数求解： 使得 $x^j \ (j \ge k)$ 前的系数为 0。

非齐次递推关系

形如

h_n = a_1 h_{n-1} + a_2 h_{n-2} + \dots + a_k h_{n-k} \quad (n \ge k) + b_n (a_k\neq 0, n\geq k)

若 $b_n\neq 0$ ，则称该递推关系为常系数线性非齐次递推关系。

例如，汉诺塔地推关系 $h_n = 2h_{n-1} + 1 (n\geq 1)$

迭代求解 + 数学归纳法
生成函数法
特征方程法：
- 求对应的齐次递推关系的通解；
- 求原非齐次递推关系的一个特解；
- 将一般解和特解结合，得到该非齐次递推关系的通解；
- 通过初始条件确定通解中出现的常系数值。

尝试特解的方法

根据非齐次项 bn来尝试某些类型的特解:
(1) 如果bn是n的k次多项式，尝试hn也是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_n2+d_n+c$ (a,d,c是常数), 尝试 $h_n= r_n2+s_n+t$ (r, s, t是常数)
(2) 若 $b_n=d_n$ (d是常数)是指数形式，尝试 $h_n= pd^n$ (p是常数)也是指数形式。

一个几何例子

详见PPT.

定理：设 $h_n$ 表示用下面方法把凸多边形区域分成三角形区域的方法数：

在有 $n+1$ 条边的凸多边形区域内通过插入不相交的对角线，而把它分成三角形区域。

定义 $h_1 = 1$ 。

则 $h_n$ 满足如下递推关系：

h_n = h_1h_{n-1} + h_2h_{n-2} + \dots + h_{n-1}h_1 = \sum_{k=1}^{n-1} h_k h_{n-k} \quad (n \ge 2)

该递推关系解为：

h_n = \frac{1}{n} \binom{2n-2}{n-1} \quad (n = 1, 2, 3, \dots)

注：此数列即为 Catalan数 $C_{n-1}$

特殊计数序列

Catalan数

Catalan数列是序列 $C_0,C_1,..,C_n,...,$ ，其中

C_n = \frac{1}{n+1}\binom{2n}{n},n=0,1,2,...

是第 $n$ 个Catalan数

凸 $n+1$ 边形被在其内部不相交的对角线划分成三角形区域的方法数

h_n = C_{n-1} = \frac{1}{n}\binom{2n-2}{n-1}

递推数：

C_n = C_0C_{n-1}+C_1C_{n-2}+...+C_{n-1}C_0; C_0 = 1, C_1 = 1, C_2 = 2, C_3 = 5, ...

典型应用：二叉树问题，出栈次序问题，括号化问题

定理：考虑由 $n$ 个 $+1$ 和 $n$ 个 $-1$ 构成的 $2n$ 项序列 $a_1,a_2,...,a_{2n}$ ，其部分和总满足 $a_1+a_2+...+a_k\geq 0 (k = 1,2,...,2n)$ 的序列的个数等于第 $n$ 个Catalan数 $C_n = \frac{1}{n+1}\binom{2n}{n}$

典型应用：买票找零问题，走方格问题

另一个递推关系： $C_n = \frac{4n-2}{n+1}C_{n-1} (n\geq 1), C_0 = 1$

拟Catalan数

一般表达式：

定义一个新的数列 $C_1^{*},C_2^{*},...,C_n^{*},...$
其中 $C_n^{*} = n!C_{n-1}^{*}$
则 $C_n^{*} = (n-1)!\binom{2n-2}{n-1}$

递推关系：

C_n^{*} = (4n-6)C_{n-1}^{*}, C_1^{*} = 1

差分序列和Stirling数

设 $h_0,h_1,...,h_n,...$ 是一个序列。定义新序列 $\Delta h_0,\Delta h_1,...,\Delta h_n,...$ 称为（一阶）差分序列，其中 $\Delta h_n = h_{n+1}-h_n (n\geq 0)$ ，是序列的相邻项的差。

二阶差分序列 $\Delta^2 h_n = \Delta h_{n+1} - \Delta h_n = h_{n+2} - 2h_{n+1} + h_n$

差分表（略）从某一阶开始全为0

定理：设序列的通项 $h_n$ 是 $n$ 的 $p$ 次多项式：$$h_n = a_pn^p+a_{p-1}n{p-1}+a_{p-2}n^{p-2}+…+a_1n+a_0, a_p \neq 0$$，则对于所有的 $n\geq 0$ ，必有 $\Delta^{p+1}h_n = 0$

差分表的性质：

差分表由第0行上元素的值就能决定
差分表也可由第0条对角线决定

定理：差分表的第0条对角线等于

c_0,c_1,c_2,...,c_p,0,0,0,... $$，其中 $ c_p \neq 0 $ 的序列的通项满足：

h_n = c_0\binom{n}{0} + c_1\binom{n}{1} + c_2\binom{n}{2} + … + c_p\binom{n}{p}

> 例：考虑通项$h_n = n^3 + 3n^2 - 2n + 1 (n\geq 0)$的序列 解：代入定理得到第0条对角线$1,2,12,6,0,0,...$

\begin{aligned}
\sum_{k=0}^n h_k &= h_0 + h_1 + \dots + h_n \
&= \sum_{k=0}^n \left(1 \binom{k}{0} + 2 \binom{k}{1} + 12 \binom{k}{2} + 6 \binom{k}{3}\right) \
&= 1\sum_{k=0}^n \binom{k}{0} + 2\sum_{k=0}^n \binom{k}{1} + 12\sum_{k=0}^n \binom{k}{2} + 6\sum_{k=0}^n \binom{k}{3} \
&= 1\binom{n+1}{1} + 2\binom{n+1}{2} + 12\binom{n+1}{3} + 6\binom{n+1}{4}。
\end{aligned}

定理：假设序列$h_0,h_1,...,h_n,...$的差分表的第0条对角线等于

c_0,c_1,…,c_p,0,0,…

则有

\sum_{k=0}^n h_k = c_0 \binom{n+1}{1} + c_1 \binom{n+1}{2} + \dots + c_p \binom{n+1}{p+1}

第二类Stirling数：$S(p,k) = \frac{c(p,k)}{k!}$ 则$h_n = n^p = \sum^{p}_{k=0}S(p,k)[n]_k$ 其中，$[n]_k = n$个不同元素中取$k$个元素的排列数$P(n,k)$ 定理：如果$1\leq k\leq p-1$则

S(p,k) = kS(p-1,k) + S(p-1,k-1)

类比二项式公式中：

\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}

定理：第二类Stirling数$S(p,k)$计数的是：把$p$元素集合划分到$k$个不可区分的盒子且没有空盒的划分的个数。 定理：如果$1\leq k \leq p-1$则