组合数学

根据课本做的笔记，供自己后期查阅。

一、排列与组合

三、容斥原理与鸽巢原理

12、鸽巢原理

13、鸽巢原理举例

1. 从 $1 \sim 2n$ 的 $2n$ 个正整数中任取 $ n+1$ 个，则这 $n+1$ 个数中至少有一对数，其中一个数是另一个数的倍数。

​ 证明

设所取的 $n+1$ 个数是

$$a_1,a_2,a_n,\cdots,a_{n+1}$$

​ 对$ a_1,a_2,a_n,\cdots,a_{n+1} $ 序列中的每一个数去掉所有 2 的因子，直至剩下一个奇数未知，例如，$ 68 = 2 \times 34 = 2^2 \times 17 $ ，去掉 2 的因子 $ 2^2$ ，留下奇数 17 ，结果得到由奇数组成的序列

$$r_1,r_2,\cdots,r_{n+1}$$

$ 1\sim 2n$ 中只有 $n$ 个奇数，故上式中至少有两个是相同的。设为 $ r_i = r_j = r $ ，对应的有

$$a_i = 2^{a_i}r, \ \ \ \ a_j= 2^{a_j}r$$

若 $a_i \gt a_j$ ，则 $a_i$ 是 $a_j$ 的倍数。

1. 设 $ a_1,a_2,a_n,\cdots,a_{m} $ 是正整数的序列，则至少存在整数 $k$ 和 $l$ ， $1 \leq k \lt l \leq m $，使得和 $ a_k + a_{k+1} + \cdots +a_l$ 是 $m$ 的倍数

   证明

​