组合数学笔记(二)

组合数学

第4章 生成排列和组合

4.1 生成排列

递归生成算法

邻位对换算法

定义

如果整数 k 的箭头指向与其相邻但比它小的整数, 则称 k 是可移动（活动）的

算法

生成{1, 2, …, n}的排列算法:

1. 初始：% “ … (；
2. while 存在活动整数时，do
   (1) 求出最大的活动整数 m
   (2) 交换 m 和其箭头指向的相邻整数的位置
   (3) 改变所有满足p>m的整数 p 的箭头方向。
3. 不存在活动整数时，算法结束。

结论：两种算法生成的排列顺序一致

4.2 排序中的逆序

定义

1. 逆序：令 $i_1,i_2 ,…, i_n$ 是集合 ${1, 2, …, n}$ 的一个排列，如果 $0 \leq k < l \leq n$ , 且 $i_k > i_l$ , 称数对 $（i_k , i_l）$ 是排列的一个逆序。

2. 逆序数：对于 { ${1, 2, …, n}$ } 上的一个排列，令 $a_j$ 表示第二元是 $j$ 的逆序的数量，即 $a_j$ 是排列中先于整数 $j$ 并大于 $j$ 的整数的个数，用于度量 $j$ 的反序程度。

3. 逆序列：令 $a_j$ 表示排列 $i_1,i_2 ,…, i_n$ 中数 $j$ 的逆序数，称 $a_1,a_2 ,…, a_n$ 为排列 $i_1,i_2 ,…, i_n$ 的逆序列。

4. 奇排列、偶排列：逆序个数为奇数的排列称为奇排列；逆序个数为偶数的排列称为偶排列

性质

性质1：排列 $i1,i_2,…,i_n$ 的逆序列 $a_1,a_2,…,a_n$ 满足： $0\leq a_1\leq n-1,0\leq a_2\leq n-2,…,0 \leq a{n-1}\leq1,a_n=0（1）$
性质2：满足条件（1）的序列 $a_1,a_2,…,a_n$ 有 $n!$ 个。

定理

1. 令 $b_1, b_2,…, b_n$ 为满足 $0\leq b_1\leq n-1,0\leq b_2\leq n-2,...,0\leq b_{n-1}\leq1,b_n=0$ 的整数序列，那么存在集合{ $1, 2, …, n$ }的唯一一个排列，满足它的逆序列为 $b_1, b_2,…, b_n$

2. n阶矩阵 $A=[a_{ij}] (i, j =1, 2, .., n)$ , 其行列式为 $det(A)= \Sigma \varepsilon (i_1i_2…i_n)a_{i_1}a_{i_2}…a_{i_n}$ ,其中， $ε(i_1i_2…i_n)$ 是 $i_1i_2…i_n$ 的符号(偶排列为+1，奇排列为-1)

3. 已知排列 $i_1, i_2 ,…, i_n$ 的逆序列为 $b_1b_2 … b_n$ ，且 $k = b_1+ b_2+… + b_n$ 为逆序数。则可以通过 $k$ 次交换相邻两个数，转化为 $1 2 … n$ 。

4.3 生成组合

算法1：字典序的组合生成

通过特征函数，将n元集合 $S=$ { ${x_{n-1}, x_{n-2}, …, x_0}$ }的组合与长度 为 $n$ 的二进制数一一对应

算法按自然二进制数顺序生成， 称为n元
组字典序。

子集的压缩序：当 j<n-1时，{ $x_j, …, x_1, x_0$ }的所有组合都在至少含有{ $x_{n-1},…, x_{j+1}$ }中一个元素的组合的前面

算法2：发射Gray码序生成算法

特点

相邻的组合仅相差一个元素（增加一个或者删除一个元素）

定义

n阶Gray码

1. n 元组看作是 n 维空间的点的坐标。
2. 每两个点的坐标仅有一个位置不同时，有一条连线。
3. 算法生成所有的 n 元组：遍历 n 维空间的每个点，使得每个点与其后继只在一个位置不同。
4. 产生的路径称为n阶Gray码

循环Gray码

遍历可以再经过一条边从终点返回到起点

n阶Gray反射码

1. 1阶反射Gray码是 0 或 1

2. 设 n>1 且 n-1 阶反射 Gray 码已经构造，如下构建 n 阶反射 Gray 码：
   (1) 以 n-1 阶反射 Gray 码所给出的顺序列出 0 和 1 的 n-1 元组，把 0 添到每个 n-1 元组的开头，
   (2) 再反序列出 n-1 阶反射 Gray 码的全部 n-1 元组, 并把1加到全部 n-1 元组的开头。

• n 阶反射 Gray 码以 00…0 开始，并以 10…0 结束。
• n 因为 00…0 与 10…0 只相差一位，因此该码是循环码。

递归方法构造反射 Gray 码，生成组合。

算法

逐次法

• 以反射 Gray 码的顺序直接生成 0，1 的n元组

1. 初始： $a_{n-1}…a_1a_0＝0…00$

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

定理

1. 对于每一个正整数 n ， 逐次法生成 n 阶反射Gray码

总结

字典序

• 与二进制数顺序一致

反射 Gray 码

• 相邻两个子集相差一个元素

• 递归法、逐次法

确定 n 元组在 Gray 码序表的准确位置

给定 Gray 码 $a_{n-1}…a_1a_0$ . 对于 $i = 0, 1, …, n-1$ ， 设

$$b_i = 0,若a_{n-1}+...+a_i是偶数\\ b_i = 1,若a_{n-1}+...+a_i是奇数$$

此时， $a_{n-1}…a_1a_0$ 在 Gray码序表的位置和 $b_{n-1}…b_1b_0$ 在字典序表上的位置相同。即 $a_{n-1}… a_1a_0$ 在Gray码序表的位置是 $b_{n-1}×2^{n-1}+…+b_1×2 + b_0×2^0$ 。

4.4 生成 r 子集

定义

r 子集的字典序

令 $S=$ { $1, 2, …, n$ } 由前 $n$ 个正整数组成。

• 给出 S 的元素的一个自然顺序:

$$1 < 2 < … < n$$

设 $A，B$ 是 $S$ 的两个 $r$ 组合，若 $A\cup B$ \ $A\cap B$ 中的最小整数属于A，则称 A先于B

组合表示为子序列

约定 $S=$ { $1, 2, …, n$ } 的 $r$ 子集为如下形式：

$$a_1 a_2 … a_r $$ , 其中 $$ 1 ≤ a_1< a_2 < … < a_r ≤ n$$

性质

设 $S=$ { $1, 2,…, n$ }, $a_1…a_r$ 是 $S$ 的一个 $r$ 子集。

• (1) 对任意的 $1≤ i < j ≤ r-1$ ，

  $a_1…a_r$ 的以 $a_1…a_j$ 开头的第一个后继一定先于以 $a_1…a_i$ 开头的第一个后继（如果存在）。

• (2) 如果 $a_r< n$ , 则 $a_1…a_r$ 的直接后继为

  $a_1…a_{r-1}\textcolor {red}{a_r+1}$ 。

定理

4.4.1

(1)

设 $a_1a_2…a_r$ 是 { $1, 2, …, n$ } 的 $r$ 子集。在字典序中, 第一个 $r$ 子集是 $12…r$ , 最后一个 $r$ 子集是 $(n-r+1)(n-r+2) … n$ 。 $a_1…a_{r-1}$ 不是最后一个 $r$ 子集。

(2)

设 $a_1a_2…a_r \neq (n-r+1)(n-r+2)…n$ 。令 $k$ 是满足 $a_k < n$ 且使得 $a_k+1$ 不同于 $a_1a_2…a_r$ 中任一数的最大整数。那么, 在字典序中, $a_1a_2…a_r$ 的直接后继是：

$$\textcolor{blue}{a_1a_2…a_{k-1}} \textcolor{red}{(a_k+1)(a_k+2)…(a_k+r-k+1)}$$

直接后继求解算法

1. 当 $a_i<n$ 时 $(1≤ i ≤ r)$ ， 求 $a_i+1$ , 判断 $a_i+1$ 是否属于{ $a_1, …, a_r$ }；

2. 找出满足 $a_i < n$ , 且 $a_i+1$ 不在 { $a_1,…, a_r$ }中的最大的 $i$ , 记为 $k$ ，那么， 在字典序中， $a_1a_2…a_r$ 的直接后继是 ：

   $$\textcolor{blue}{a_1a_2…a_{k-1}} \textcolor{red}{(a_k+1)(a_k+2)…(a_k+r-k+1)}$$

字典序 r 子集的生成算法

{ $1, 2,…, n$ }的字典序 $r$ 子集的生成算法：

从 $12…r$ 开始，逐个列出直接后继，直至得到 $(n-r+1)(n-r+2)…n$

1. 初始： $a_1a_2…a_r＝12…r$ ；
2. 当 $a_1a_2…a_r \neq(n-r+1)(n-r+2)…n$ 时，进行以下操作：
   (1) 确定最大整数k, 使得 $a_k+1\leq n，且 a_k+1\neq a_i (i=1,2,…,r)$ ；
   (2) 用 $a_1a_2…a_{k-1} (a_k+1)…(a_k+r-k+1)$ 替换 $a_1a_2…a_r$ .

定理

4.2.2

{ $1, 2,…, n$ }的 $r$ 子集 $a_1a_2…a_r$ 出现在 { $1, 2, …, n$ }的 $r$ 子集中的字典序中的位置号为：

$${{n}\choose{r}}- {{n-a_1}\choose{r}}- {{n-a_2}\choose{r-1}}...- {{n-a_{r-1}}\choose{2}}- {{n-a_r}\choose{1}}$$

第5章 二项式系数

组合证明

是一种依靠计数原理构建代数事实的证明方法

基本框架：

1. 定义一个集合 $S$ ；
2. 通过一种计数方式得出 $|S|= n$ ；
3. 通过另一种计数方式得出 $|S|= m$ ；
4. 得出结论 $n = m$ 。

二项式定理

令 $n$ 是一个正整数, 那么对于所有的 $x, y$ 有：

$$(x+y)^{n}= \sum_{k=0}^{n} {n\choose k}x^{n-k}y^{k}$$

其中：

$${n\choose k}= \frac {n!}{k!(n-k)!}=\frac {n(n-1)...(n-k+1)}{k(k-1)...1}$$

5.1 帕斯卡三角形

定理

5.1.1

( Pascal 公式) 对于满足 $1\leq k \leq n$ 的所有整数 $k$ 和 $n$ , 有：

$${n\choose k}={n-1\choose k}+{n-1\choose k-1}$$

5.2 二项式定理

定理

5.2.1

令 $n$ 是一个正整数, 那么对于所有的 $x, y$ 有：

$$(x+y)^{n}= \sum_{k=0}^{n} {n\choose k}x^{n-k}y^{k}$$

二项式系数的其他等式

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

方法

证明等式的方法

• 利用已有等式：帕斯卡公式
• 求导法、积分法
• 组合推理法

性质

组合推理路径数

从 $(0,0)$ 点到 $(m,n)$ 点，共有 ${m+n \choose m} = {m+n \choose n}$ 种路径

组合定义扩展

$${n\choose k}= \frac {n!}{k!(n-k)!}= \frac {n(n-1)...(n-k+1)}{k(k-1)...1}$$

扩展：

• $$\textcolor{red}{n}扩展为\textcolor{red}{任意实数}$$
• $$\textcolor{blue}{k}扩展为\textcolor{blue}{任意整数}$$

令 $\textcolor{red}{r}$ 可取 $\textcolor{red}{任意实数}$ , $\textcolor{blue}k$ 可取 $\textcolor{blue}{任意整数（正的、负的或零）}$ ,
定义二项式系数 $r\choose k$ 为：

$${r\choose k}=\left\{ \begin{array}{rcl} x & = & \frac{r(r-1)...{r-k+1}}{k!} &, 若k \geq 1\\ y & = & 1 &, 若k = 0\\ z & = & 0 &, 若k \leq -1 \end{array} \right.$$

• 扩展定义 $n\choose k$ 仍使Pascal公式成立

• 令 $\textcolor{red}{r}$ 可取 $\textcolor{red}{任意实数}$ , $\textcolor{blue}k$ 可取 $\textcolor{blue}{任意整数}$ ，仍有：

  $${r\choose k}={r-1\choose k}+{r-1\choose k-1}\\ k{r \choose k}=r{r-1 \choose k-1}$$

5.3 二项式系数的单峰性

定义

单峰性

设序列 $s_0,s_1,s_2,…,s_n$ , 若存在一个整数 $t$ , $0 \leq t \leq n$ , 使得:

$$s_0 \leq s_1 \leq s_2 \leq ... \leq s_t， s_t \geq s_{t+1} \geq s_{t+2} \geq ... \geq s_n$$

那么, 称序列是 $\textcolor{red}{单峰}$ 的。

注意

1. $s_t$ 一定是序列中的最大数
2. $t$ 不一定是唯一的

取整

设 $x$ 为任意实数, 令 $\lceil x \rceil$ 表示大于或等于 $x$ 的最小整数,称强取整(上取整); $\lfloor x \rfloor$ 表示小于或等于 $x$ 的最大整数,称弱取整(下取整).

定理

5.3.1

令 $n$ 为正整数, 二项式系数序列是 $\textcolor{red}{单峰序列}$ ,其中：

• 若 $n$ 是偶数：

$${n\choose0}<{n\choose1}<...<{n\choose n/2}， {n\choose n/2}>...>{n\choose n-1}>{n\choose n}$$

• 若 $n$ 是奇数：

$${n\choose0}<{n\choose1}<...<{n\choose (n-1)/2}， {n\choose (n+1)/2}>...>{n\choose n-1}>{n\choose n}$$

5.3.2

二项式系数 ${n\choose 0},{n\choose 1},...,{n\choose n}$ 的最大者是：

• ${n\choose \lfloor n/2 \rfloor} = {n\choose \lceil n/2 \rceil} = {n\choose n/2 }$ ( $n$ 为偶数时)
• ${n\choose \lfloor n/2 \rfloor} = {n\choose \lceil n/2 \rceil} = {n\choose (n-1)/2 } == {n\choose (n+1)/2 }$ ( $n$ 为奇数时)

扩展 1

• 由集合的子集的包含关系定义的链与反链
• 由包含关系推广到一般偏序

定义

反链

令 $S$ 是 $n$ 个元素的集合， $S$ 上的一条反链是 $S$ 的子集的一个集合 $A$ ，其中 $A$ 中的子集不相互包含。

链

令 $S$ 是 $n$ 个元素的集合, $S$ 上的一条链是 $S$ 的子集的集合 $C$ ，其中对于 $C$ 中的每一对子集，总有一个包含在另一个之中：
对任意 $S_1,S_2\in C$ ，且 $S1 \neq S2$ ，则 $S1 \subset S2$ 或者 $S2 \subset S1$

最大链

令 $S$ 是 $n$ 个元素的集合, $S$ 上的最大链 $C$ 定义为： $C = {A_0, A_1, …, A_n}$ ，
满足:
(1) $A_0= Φ \subset A_1 \subset A2…\subset An$ , 且
(2) $| A_i | = i (i =1, …, n)$

方法

构造反链

令 $S$ 为 $n$ 个元素的集合，一个构造反链的方法：

选择一个整数 $k \leq n$ ，取 $A_k$ 为 $S$ 所有的 $k$ 子集的集合。该方法构成的反链最多含有 $n \choose \lfloor n/2 \rfloor$ 个子集。

构造最大链

1. $$A_0= Φ$$

2. 从 $S$ 中选择一个元素 $i_1$ , 形成 $A_1=$ { $i_1$ }.

3. 选择一个元素 $i_2 \neq i_1$ , 形成 $A_2=$ { $i_1, i_2$ }.

4. 选择一个元素 $i_3 \neq i_1, i_2$ 形成 $A_3=$ { $i_1, i_2, i_3$ }.

   …

   k. 选择一个元素 $i_k \neq i_1, i_2,…, i_{k-1}$ 形成 $A_k=$ { $i_1, i_2, …, i_k$ }.
   …
   n. 选择一个元素 $i_n \neq i+1,…, i+{n-1}$ 形成 $An=$ { $i_1, i_2, …, i_n$ }.

• S上的最大链与 S 的排列一一对应
• 最大链的数目为 $n!$

链与反链的关系

• $S$ 上的一条链最多只能包含 $S$ 的任意一条反链中的一个子集
• $S$ 上的一条反链最多只能包含 $S$ 的任意一条链中的一个子集

定理

5.3.3

设 $S$ 为 $n$ 个元素的集合，则 $S$ 上的一条反链最多包含 $n\choose \lfloor n/2 \rfloor$ 个子集

更强的结果

设 $S$ 是为 $n$ 个元素的集合，

• 如果n是偶数，则大小为 $n\choose \lfloor n/2 \rfloor$ 的唯一的反链是所有 $n/2$ 子集的反链
• 如果n是奇数，则大小为 $n\choose \lfloor n/2 \rfloor$ 的反链有两个：
  • 所有 $(n-1)/2$ 子集构成的反链；
  • 所有 $(n+1)/2$ 子集构成的反链。

扩展 2

• 集合的包含关系是偏序关系
• 把链、反链的概念推广到偏序集

令 $( X,\leq )$ 是一个有限偏序集,

• 链是 $X$ 的一个子集, 其中任意两个元素都是可比的,

• 反链是 $X$ 的一个子集, 其中任意两个元素都不可比.

• 极小元： $a$ 是偏序集的极小元当且仅当 $X$ 中不存在
  满足 $x < a$ 的元素 $x$

  • $X$ 的所有极小元构成的子集是反链
• 极大元： $av 是偏序集的极大元当且仅当 `$ X$ 中不存在
  满足 $x > a$ 的元素 $x$
  • $X$ 的所有极大元构成的子集也是反链

定理

5.6.1

令 $( X, \leq )$ 是一个有限偏序集, 并令 $r$ 是最大链的大小, 则 $X$ 可以被划分成 $r$ 个反链，但不能划分为少于 $r$ 个的反链。

5.6.2

令 $(X, \leq)$ 是一个有限偏序集, 并令 $m$ 是最大反链的大小, 则 $X$ 可以被划分成 $m$ 个链，但不能划分成少于 $m$ 个链

定义

对称链划分

设 $S=$ { $1, 2,…, n$ }， 如果 $S$ 的幂集 $P(S)$ 的一个链划分满足以下两个条件，则称其是一个对称链划分：
(1) 链中每一个子集比它前面的子集的元素个数多 $1$ ；
(2) 链中第一个子集与最后一个子集的大小和等于 $n$ 。
如果这个链只含一个子集，那么这个子集既是第一个子集也是最后一个子集，所以其大小为 $n/2$ (此时， $n$ 为偶数)

方法

对称链划分的构造方法

基本思路：将 $S$ 的所有子集划分为 ${n\choose \lfloor n/2 \rfloor}$ 个对称链。令 $S=$ { $1, 2, …, n$ } ，对 $n$ 进行归纳构造：

对于 $n=k$ 时的每一个含多个子集的链 $E$ ，可构造 $n=k+1$ 时的两个链：

1. 对 $E$ 增加如下子集：在 $E$ 的最后一个子集中增加 $k+1$ ，构成一个新子集
2. 把 $k+1$ 加到 $E$ 中除最后一个子集之外的所有子集，并删除最后一个子集

注意：

• 对称链划分中的每一个链必须正好含有一个 $\lfloor n/2 \rfloor$ 子集（也正好含有一个 $\lceil n/2 \rceil$ 子集）
• 对称链划分中的链的个数等于： ${n\choose \lfloor n/2 \rfloor }= {n \choose \lceil \lceil n/2 \rceil \rceil}$

5.4 多项式定理

定义

• 把二项式定理 $(x+y)^n$ 扩展到 $(x_1+x_2+…+x_t)^n$
• 多项式系数： ${n\choose n_1n_2...n_t}={\frac{n!}{n_1!n_2!...n_t!}}$ , 其中 $n_1, n_2, … n_t$ 是非负整数，且 $n_1+n_2+…+n_t=n$
• • 表示重数分别为 $n_1, n_2, … n_t$ 的 $t$ 种不同类型物品的多重集的排列数
  • 二项式系数： ${n\choose r}={\frac {n!}{r!(n-r)!}}$ , 可记为 $n\choose r\quad n-r$

定理

帕斯卡公式

• 二项式系数的帕斯卡公式

$${n\choose k\quad n-k}= {n-1\choose k\quad n-k-1}+ {n-1\choose k-1\quad n-k}$$

• 多项式系数的帕斯卡公式

$${n\choose n_1\quad n_2\quad ... n_t}= {n-1\choose n_1-1\quad n_2\quad ... n_t}+ {n-1\choose n_1\quad n_2-1\quad ... n_t}+ ...+ {n-1\choose n_1\quad n_2\quad ... n_t-1}$$

5.4.1

设 n是正整数。对于所有的 $x_1, x_2,…, x_t$ , 有

$$(x_1+x_2+...+x_t)^n=\Sigma{n\choose n_1\quad n_2\quad ... n_t} x_1^{n_1}x_2^{n_2}...x_t^{n_t}$$

其中求和是对 $n_1+n_2+…+n_t=n$ 的所有非负整数解 $ n_1, n_2, …, n_t $ 进行的。

牛顿二项式定理

定理

5.5.1

令 $a$ 是一个实数, 对于所有满足 $0 \leq |x|< |y|$ 的变量 $x , y$ 有

$$(x+y)^{\alpha}=\Sigma^{\infty}_{k=0}{\alpha \choose k}x^ky^{\alpha -k}$$

其中， ${\alpha\choose k} = \frac{\alpha(\alpha -1)...(\alpha - k +1)}{k!}$

如果 $\alpha$ 为整数，则就是二项式定理

等价形式

对满足 $|z|<1$ 的任意 $z$ ，有 $(1+z)^{-n}=\Sigma^{\infty}_{k=0}(-1)^k{n+k-1 \choose k}z^k$

应用

求解任意精度平方根

令 $\alpha =1/2$ ，有 ${\alpha \choose 0}=1$ ，对于 $k>0$ 有：

$${\alpha \choose k}={1/2 \choose k}=\frac{(-1)^{k-1}}{k\times 2^{2k-1}}{2k-2 \choose k-1}$$

因此，对 $|z|<1$ ，有：

$$\sqrt{1+z} = (1+z)^{1/2} = 1+\sum^{\infty}_{k=1}\frac{(-1)^{k-1}}{k \times 2^{2k-1}}{2k-2 \choose k-1}z^k\\ =1+\frac{1}{2}z- \frac{1}{2\times2^3}{2\choose1}z^2+ \frac{1}{3\times2^5}{4\choose2}z^3- ...$$

(详细证明见ppt)