组合数学笔记(一)

组合数学

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)}{2r}=\frac{n!}{2r!(n-r)!}$

2.3 集合的组合

排列:

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

性质1:

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

性质2:

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

帕斯卡公式

$$C(n,k)=C(n-1,k)+C(n-1,k-1)$$ $$C(n,0)+...+C(n,n)=2^n$$

2.4 多重集合的排列

概念

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

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

定理

1. 无限重复 r排列

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

1. 有限重复 全排列

令S是多重集，它有k种不同的元素，
每种元素的重复数分别为 $n_1$ , $n_2$ , …, $n_k$ ,则S的排列数等于

$$\frac{n!}{n_1!n_2!...n_k!}$$

其中n= $n_1$ + $n_2$ + …+ $n_k$

1. 集合划分

设 $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$ 个元素(i=1, 2,…,k), 则划分方法数为

$$\frac{n!}{n_1!n_2!...n_k!}$$

若盒子无标号，划分数为

$$\frac{n!}{k!n_1!n_2!...n_k!}$$

1. 非攻击性车

懒得写力~自己想罢

2.5 多重集合的组合

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

定义

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

方法

1. 有重组合转无重组合

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

1. 隔板法

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

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

定理

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

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

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

2.6 有限概率

定义

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

方法

不相邻问题

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

方程的解问题

非负整数解

$$x_1+x_2+...+x_k=n $$ 的非负整数解个数为 $$ {n+k-1\choose n}={n+k-1\choose k-1}$$

正整数解(万物之源)

$$x_1+x_2+...+x_k=n $$ 的正整数解个数为 $$ n-1\choose k-1$$

不相邻问题

链不相邻问题

转换为方程的解问题

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

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

$$x_1 \geq 1,x_2\geq2,x_3\geq2,...,x_k\geq2,x_{k+1}\geq0$$

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

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

环不相邻问题

用链不相邻问题推导

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

第3章 鸽巢原理

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

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

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

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

知识点:

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

3.1 鸽巢原理的简单形式

定理

1. 鸽巢原理的简单形式

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

1. 中国剩余定理

设 $m_1, m_2,…,m_k$ 是k个两两互素的正整数， $0\leq a_i<m_i(i=1,...,k)$ ,则存在x，使得 x 除以 $m_i$ 的余数为 $a_i$ ，即 $x \equiv ai (\bmod m_i) (i=1,…，k)$

$$\begin{cases} \ x \equiv a_1 (\bmod m_1)\\ \ x \equiv a_2 (\bmod m_2)\\ \ \ldots\\ \ x \equiv a_n (\bmod m_n)\\ \end{cases}$$

3.2 鸽巢原理的加强形式

定理

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

$$q_1+q_2+…+q_n – n+1= n(r-1)+1$$

1. 平均原理：

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

理解

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

则不会出现:

第一个盒子少于1个

第二个盒子少于2个

第三个盒子少于3个

第四个盒子少于4个

第五个盒子少于5个

这五个不会同时出现

方法

1. 最小物品数

2. 圆盘问题，二进制问题

3.3 Ramsey原理

简单形式

通俗实例： 在6个人中，

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

完全形式

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

1. $$K_6 \rightarrow K_3,K_3$$

Ramsey定理

如果m ≥ 2及n ≥ 2是两个整数，则一定存在正整数 p，使得 $K_p \rightarrow K_m,K_n$

定义

Ramsey数 $r(m, n)$ 是使 $K_p \rightarrow K_m,K_n$ 成立的最小整数 p

1. $$r(2,n)=n$$
2. $$r(m,2)=m$$
3. $$r(m, n) ≤ r(m-1, n) + r(m, n-1)，m, n≥ 3$$

推广

如果 $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)$$

更一般的形式

给定整数 $t ≥2$ 及整数 $q_1, q_2, …, q_k ≥ 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 ≥2$ 及整数 $q_1, q_2, …, q_k ≥ t$ ，存在一个整数 p, 使..得 $K_p^t \rightarrow K_{q_1}^t,K_{q_2}^t,...,K_{q_k}^t$