组合数学笔记(一)

组合数学

6.7 之后出现了大量渲染错误，懒得改了 (～￣▽￣)～

第 2 章组合与排列

2.2 集合的排列

插空法捆绑法隔板法

循环排列

全排列种类数 $= \frac{P (n, n)}{n} = (n - 1)!$

循环 r 排列个数 $= \frac{P (n, r)}{r} = \frac{n!}{r (n - r)!}$

项链排列

r 排列个数 $= \frac{P (n, r)}{2 r} = \frac{n!}{2 r! (n - r)!}$

2.3 集合的组合

排列:

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

性质 1:

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

性质 2:

k (\binom{n}{k}) = n (\binom{n - 1}{k - 1})

帕斯卡公式

C (n, k) = C (n - 1, k) + C (n - 1, k - 1)

C (n, 0) + . . . + C (n, n) = 2^{n}

2.4 多重集合的排列

概念

多重集：允许元素重复（多重集不是集合）

无限重复排列有限重复排列

定理

无限重复 r 排列

令 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}, \dots, n_{k}$ 是正整数，且 $n = n_{1} + n_{2} + \dots + n_{k}$ 。将 n 个元素集合划分成 k 个标有标签的盒子 $B_{1}, B_{2}, \dots, B_{k}$ , 其中 $B_{i}$ 含有 $n_{i}$ 个元素 (i=1, 2,…,k), 则划分方法数为

\frac{n!}{n_{1}! n_{2}! . . . n_{k}!}

若盒子无标号，划分数为

\frac{n!}{k! n_{1}! n_{2}! . . . n_{k}!}

非攻击性车

懒得写力～自己想罢

2.5 多重集合的组合

2.5 多重集合的组合
 去瞅瞅更完整的 6.2

定义

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

方法

有重组合转无重组合

{1, 2, …,k} 的 r 组合数 ={1, 2, …,k+r-1} 的无重 r 组合数 = $(\binom{r + k - 1}{r})$

隔板法

(\binom{r + k - 1}{k - 1}) = (\binom{r + k - 1}{r})

相当于 r 个盒子，插 k-1 个板，两个板之间放球，但某种球可以不放，因此再加 k 个盒子，使每种球至少放一个盒子

定理

令 S 是多重集，它有 k 个不同的元素，每个元素都有无限重复次数，那么，S 的 r 组合个数为

(\binom{r + k - 1}{k - 1}) = (\binom{r + k - 1}{r})

多重集组合 -> 方程的非负整数集

2.6 有限概率

定义

有限概率：相对于微积分为基础的连续概率

方法

不相邻问题

转换为整数解问题使用隔板法

方程的解问题

非负整数解

x_{1} + x_{2} + . . . + x_{k} = n $ $ 的 非 负 整 数 解 个 数 为 $ $ (\binom{n + k - 1}{n}) = (\binom{n + k - 1}{k - 1})

正整数解 (万物之源)

(\binom{x_{1} + x_{2} + . . . + x_{k} = n $ $ 的 正 整 数 解 个 数 为 $ $ n - 1}{k - 1})

不相邻问题

链不相邻问题

转换为方程的解问题

设为 $n$ 个球中取 $k$ 个不相邻数，可理解为插入 $k$ 个挡板，每个挡板的左边球为所取的球

转换为方程为 $x_{1} + x_{2} + . . . + x_{k} + x_{k + 1} = n$ ，其中

x_{1} \geq 1, x_{2} \geq 2, x_{3} \geq 2, . . ., x_{k} \geq 2, x_{k + 1} \geq 0

代入正整数解问题，求解得不相邻问题的数量为：

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

环不相邻问题

用链不相邻问题推导

\begin{aligned} a (n, k) & = 2 \times (\binom{2 n - 3 - (k - 1) + 1}{k - 1}) + (\binom{2 n - 2 - k + 1}{k}) \\ = 2 \times (\binom{2 n - k - 1}{k - 1}) + (\binom{2 n - k - 1}{k}) \\ = 2 \times \frac{(2 n - k - 1)!}{(k - 1)! (2 n - 2 k)!} + \frac{(2 n - k - 1)!}{k! (2 n - 2 k - 1)!} \\ = 2 \times \frac{k}{2 n - k} \times (\binom{2 n - k}{k}) + \frac{2 n - 2 k}{2 n - k} \times (\binom{2 n - k}{k}) \\ = \frac{2 n}{2 n - k} (\binom{2 n - k}{k}) \end{aligned}

第 3 章鸽巢原理

鸽巢原理研究的是存在性问题

核心在于构建出盒子和物体

简单形式: n 个盒子，n+1 个物体

加强形式: m 个盒子，n 个物体

知识点:

数论问题
几何图形类问题
连续时间问题
棋盘着色
中国剩余定理
满足条件的最小物体数

3.1 鸽巢原理的简单形式

定理

鸽巢原理的简单形式

如果把 n＋1 个物体放进 n 个盒子，那么至少有一个盒子包含两个或更多的物体

中国剩余定理

设 $m_{1}, m_{2}, \dots, m_{k}$ 是 k 个两两互素的正整数， $0 \leq a_{i} < m_{i} (i = 1, . . ., k)$ , 则存在 x，使得 x 除以 $m_{i}$ 的余数为 $a_{i}$ ，即 $x \equiv a i (mod m_{i}) (i = 1, \dots ， k)$

{\begin{cases} x \equiv a_{1} (mod m_{1}) \\ x \equiv a_{2} (mod m_{2}) \\ \dots \\ x \equiv a_{n} (mod m_{n}) \end{cases}

3.2 鸽巢原理的加强形式

定理

鸽巢原理的加强形式

令 $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} = r$ 时，

q_{1} + q_{2} + \dots + q_{n} - n + 1 = n (r - 1) + 1

平均原理：

如果 $n$ 个非负整数 $m_{1}, m_{2}, \dots, m_{n}$ 的平均数大于 $r - 1$ ，即 $\frac{(m_{1} + m_{2} + \dots + m_{n})}{n} > r - 1$ ，则至少有一个整数大于或等于 $r$ 。
设 $m$ 和 $n$ 都是正整数。如果 $m$ 个物体放入 $n$ 个盒子，则至少有一个盒子含有 $⌈ \frac{m}{n} ⌉$ 个或更多的物体。

理解

例：5 个盒子 1+2+3+4+5-5+1=10

则不会出现:

第一个盒子少于1个

第二个盒子少于2个

第三个盒子少于3个

第四个盒子少于4个

第五个盒子少于5个

这五个不会同时出现

方法

最小物品数
圆盘问题，二进制问题

3.3 Ramsey 原理

简单形式

通俗实例：在 6 个人中，

或者有 3 个人，他们中每两个人都互相认识；
n 或者有 3 个人，他们中的每两个人都彼此不认识。

完全形式

用 $K_{n}$ 表示平面上没有 3 点共线的 n 个顶点构成
的一个完全图 (n 阶完全图)

$K_{6} \to K_{3}, K_{3}$

Ramsey 定理

如果 m ≥ 2 及 n ≥ 2 是两个整数，则一定存在正整数 p，使得 $K_{p} \to K_{m}, K_{n}$

定义

Ramsey 数 $r (m, n)$ 是使 $K_{p} \to K_{m}, K_{n}$ 成立的最小整数 p

$r (2, n) = n$
$r (m, 2) = m$
$r (m, n) \leq r (m - 1, n) + r (m, n - 1) ， m, n \geq 3$

推广

如果 $n_{1}, n_{2}, \dots, n_{l}$ 都是大于或等于 2 的整数则一定存在正整数 p，使得

K_{p} \to K_{n_{1}}, K_{n_{2}}, . . ., K_{n_{l}}

满足以上条件的最小整数 p 称为 Ramsey 数

r (n_{1}, n_{2}, . . ., n_{l})

更一般的形式

给定整数 $t \geq 2$ 及整数 $q_{1}, q_{2}, \dots, q_{k} \geq t$ ，则存在一个整数 p，
使得：如果将 p 元素集合中每一个 t 元素子集指定为 k 种
颜色 $c_{1}, c_{2}, \dots, c_{k}$ 中一种，那么

或者存在 $q_{1}$ 个元素，其所有 t 子集被指定成颜色 $c_{1}$ ,
… …,
或者存在 $q_{k}$ 个元素，其所有 t 子集被指定成颜色 $c_{k}$ ,

满足结论的最小整数 p 为 Ramsey 数 $r_{t} (q_{1}, q_{2}, \dots, q_{k})$

令 $K_{N}^{t}$ 表示 n 个元素集合中所有 t 个元素的子集的集合

给定整数 $t \geq 2$ 及整数 $q_{1}, q_{2}, \dots, q_{k} \geq t$ ，存在一个整数 p, 使.. 得 $K_{p}^{t} \to K_{q_{1}}^{t}, K_{q_{2}}^{t}, . . ., K_{q_{k}}^{t}$

组合数学

第 2 章 组合与排列

2.2 集合的排列

2.3 集合的组合

2.4 多重集合的排列

2.5 多重集合的组合

2.6 有限概率

方法

方程的解问题

非负整数解

正整数解 (万物之源)

不相邻问题

链不相邻问题

环不相邻问题

第 3 章 鸽巢原理

3.1 鸽巢原理的简单形式

3.2 鸽巢原理的加强形式

3.3 Ramsey 原理

微信扫一扫：分享

第 2 章组合与排列

第 3 章鸽巢原理