3. 容斥原理与鸽巢原理

为了区分讨论的问题类型困难，区分同类型，避免重复和遗漏？？

所以引入了容斥原理和鸽巢原理

3.1 De Morgan定理

$\overline{A\cup B}=\overline{A}\cap \overline{B}$

$\overline{A\cap B}=\overline{A}\cup \overline{B}$

De Morgan定理的推广

$A_1,A_2,\cdots,A_n$是$U$的子集

$\overline{A_1\cup A_2\cup \cdots \cup A_n}=\overline{A_1}\cap \overline{A_2}\cap \cdots \cap \overline{A_n}$

3.1 容斥原理

加法法则

事件$A$有$m$种产生方式，事件$B$有$n$种产生方式，则事件$A$或事件$B$之一有$m+n$种产生方式。

若$|A|=m,|B|=n,A\cap B= \varnothing$,则$|A\cup B|=m+n$

容斥原理计数思想是

先不考虑重叠的情况，把包括于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去

例子

$[1,20]$中2或3的倍数的个数

2的倍数是$2,3,6,8,10,12,14,16,18,20$

3的倍数是$3,6,9,12,15,18$

但答案不是16个，因为6,12,18在两类中重复计数，应减去16-3=13

容斥原理概念

$|A\cup B|=|A|+|B|-|A\cap B|$

$|A\cup B\cup C|=|A|+|B|+|C|+|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$

容斥原理应用

求从1到500的整数中能被3或5除尽的数的个数

$|A|=\lfloor \frac{500}{3}\rfloor,|B|=\lfloor \frac{500}{5}\rfloor=100,|A\cap B|=\lfloor \frac{500}{15}\rfloor=33$

所以结果为$|A\cup B|=|A|+|B|-|A\cap B|=166+100-33=233$

---

求$a,b,c,d,e,f$六个字母的全排列中不允许出现$ace$和$df$图像的排列数

解：6个字母全排列，$|S|=6!$,

设$A$为$ace$作为一个元素出现的排列集：$|A|=4!$

$B$为$df$作为一个元素出现的排列集$|B|=5!$

$A\cap B$为同时出现$ace,df$的排列数$|A\cap B|=3!$

$|\overline{A}\cap \overline{B}|=|\overline{A \cup B}|=6!-4!-5!+3!=582$

---

求$a,b,c,d$四个字母构成的$n$位符号串中$a,b,c$都至少出现一次的符号串数目

令$A,B,C$分别为$n$位符号串中不出现$a,b,c$符号的集合

$|\overline{A}\cap \overline{B}\cap \overline{C}|=4^n-(|A|+|B|+|C|)+(|A\cap B|+|A\cap C|+|C\cap B|)-|A\cap B\cap C|$

$=4^n-3\cdot 3^n+3\cdot 2^n-1$

欧拉函数

欧拉函数$\phi(n)$是关求小于$n$且与$n$互素的数的个数

例子$\phi(8)=4,$小于8且与8互素有1 3 5 7

若$n$分解为不同素数的乘积

$n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$

设$1$到$n$的$n$个数中为$p_i$倍数的集合为$A_i$

$|A_i|=\frac{n}{p_i},i=1,2,\cdots,k$

对于$p_i\ne p_j,A_i\cap A_j$即是$p_i$的倍数也是$p_j$的倍数

$|A_i\cap A_j|=\frac{n}{p_ip_j},i,j=1,2,\cdots,k,i\ne j$

$$\phi(n)=|\overline{A_1}\cap \overline{A_2}\cap \cdots \cap \overline{A_k}| \\ =n-(\frac{n}{p_1}+\frac{n}{p_2}+\cdots+\frac{n}{p_k})+(\frac{n}{p_1p_2}+\frac{n}{p_2p_3}+\cdots+\frac{n}{p_1p_k})+\cdots (\frac{n}{p_1 p_2\cdots p_k}) \\ \phi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_k})$$

例子

$n=60=2^2\times 3\times 5$

$\phi(60)=60(1-\frac{1}{2})(1-\frac{1}{3})(1-\frac{1}{5})=16$

---

定理

求不定方程$x_1+x_2+\cdots +x_n=b$,求非负整数解的数目

$C(n+b-1,b)$

开始添加约束

求不定方程$x_1+x_2+x_3=15$,求非负整数解的数目

$C(n+b-1,b)=C(3+15-1,15)$

若添加约束$0\le x_1\le 5,0\le x_2\le 6,0\le x_3\le 7$。

解：

设$A_1$为$x_1\ge 6$的解，$y_1+6+x_2+x_3=15$

$|A_1|=C(9+3-1,9)=C(11,2)$

设$A_2$为$x_2\ge 7$的解，$x_1+y_2+7+x_3=15$

$|A_2|=C(8+3-1,8)=C(10,2)$

设$A_3$为$x_3\ge 8$的解，$x_1+_2+y_3+8=15$

$|A_3|=C(7+3-1,7)=C(9,2)$

$A_1\cap A_2:y_1+6+y_2+7+x_3=15,|A_1\cap A_2|=C(4,2)$

$A_1\cap A_3:y_1+6+x_2+y_3+8=15,|A_1\cap A_3|=C(3,1)$

$A_2\cap A_3:x_1+y_2+7+y_3+8=15,|A_2\cap A_3|=1$

---

放球问题

在放球问题中，我们引入了第二类Stirling数

$S(n,m)=\frac{1}{m!}\sum_{k=1}^m C(m,k)(-1)^k(m-k)^n$

$S(n,m)$的组合意义：将n个有标志的球放入m个无区别的盒子，而且无一空盒的方案数

先考虑n个有标志的球，放入m个有区别的盒子，无一空盒的方案数。

解$A_i$表示第$i$个盒子为空，$i=1,2,\cdots,m$

$n$个有标志的球放入$m$个有区别的盒子的事件全体为$S$,$|S|=m^n$

$|A_i|=(m-1)^n$共有$C(m,1)$个

$|A_i\cap A_j|=(m-2)^n$共有$C(m,2)$个

m个有区别盒子，无空盒的方案数：

$N=|\overline{A_1}\cap \overline{A_2}\cdots \cap \overline{A_n}$

$=m^n-C(m,1)(m-1)^n+C(m,2)(m-2)^n+\cdots+(-1)^nC(m,m)(m-m)^n$

$=\sum_{k=0}^m(-1)^kC(m,k)(m-k)^n$

---

错排问题

$n$个元素依次给以标号$1,2,\cdots,n$个元素的全排列中，求每个元素都不在自己原来位置上的排列数

设$A_i$为数$i$在第$i$位上的全体排列，$i=1,2,\cdots,n$，因数字$i$不能动

因而$|A_i|=(n-1)!$

$|A_i\cap A_j|=(n-2)!$

$|\overline{A_1}\cap \overline{A_2}\cap \cdots\cap \overline{A_n}=n!-C(n,1)(n-1)!+C(n,2)(n-2)!-\cdots \pm C(n,n)0!$

=$n!(1-\frac{1}{1!}+\frac{1}{2!}-\cdots\pm \frac{1}{n!})$

3.2 鸽巢原理(抽屉原理)

桌子有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放？，我们会发现至少会有一个抽屉里面放不少于两个苹果。这一现象就是我们所说的“抽屉原理”。抽屉原理的一般含义为：“如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有n+1个元素放到n个集合中去，其中必定有一个集合里至少有两个元素。”

例子

班级中30个人，有至少3位同学在同一月出生

例子

10双蓝袜子，12双白袜子，随机去几次就能凑成一对

什么是鸽子，什么是巢？？

证明

已知$n+1$个正整数，他们全都小于或等于$2n$,证明当中一定有两个数是互质的

每个盒子里放2个相邻的球，相邻的球一定是互质的

取n+1个球，会发现一定会有一定有2个球是来自同一个盒子里

例子

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

证明

设$n+1$个数是$a_1,a_2,\cdots,a_{n+1}$每个数去掉一切2的因子，直到剩下一个奇数为止，组成序列$r_1,r_2,\cdots,r_{n+1}$.

这$n+1$个数仍在$[1,2n]$中，且都是奇数。而$[1.2n]$中只有$n$个奇数

故必有$r_i=r_j=r$

则$a_i=2^{ki}r,a_j=2^{kj}r$

若$a_i>a_j$,则$a_i$是$s_j$的倍数

---

设$a_1,a_2,\cdots,a_{100}$是由1和2组成的序列，已知从其任一数开始的顺序10个数的和不超过16，即

$a_i+a_{i+1}+\cdots+a_{i+9}\le 16$

则至少存在$h$和$k,k>h$,使得$a_{h+1}+\cdots a_k=39$

• 根据假定$a_i+a_{i+1}+\cdots+a_{i+9}\le 16,1\le i\le 91$,有$S_{100}\le 10\times 16=160$，$S_1,S_2,\cdots,S_{100}$相互不相同

• 做序列$S_1,S_2,\cdots,S_{100},S_1+39,\cdots,S_{100}+39$共200项。其中最大项

  $S_{100}+39\le 160+39=199$

  因为一共200项，最大值是199,。所以根据鸽巢原理，必有两项相等。而且必是前段中某个项与后段中某一项相等

  $S_k=S_h+39,k>h,S_k-S_h=39$

---

一个抽屉里面有20件衬衣，其中4件蓝色，7件灰色，9件红色的。问从中任意取至少多少件保证有4件同色的？？

鸽巢原理：n个鸽巢，(kn+1)个鸽子，至少有一个鸽巢里面有k+1个鸽子

解：有三种颜色，3个鸽巢，要求k+1=4.

K=3,kn+1=10,冲中取出至少10件衣服才能保证有4件同色的？

加问

一个抽屉里面有20件衬衣，其中4件蓝色，7件灰色，9件红色的。问从中任意取至少多少件保证有5件同色的？？

第一次取正好4件蓝色的，剩下的从红色和灰色中取$n=2,k+1=5$,故需取$4+4\times 2+1=13$能保证有5件同色的

---

今有无，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何？？答23

$$\begin{cases} x=3a+2 \\ x=5b+3 \\ x=7c+2 \end{cases}$$

中国剩余定理

m和n是两个互质的正整数，对于任意非负整数a与b(a<m,b<n)，则必然存在正整数x使得联立的同余方程组有公解

$$\begin{cases} x=pm+a \\ x=qn+b \end{cases}$$

p,q为非负整数

3.3 Ramsey 数

拉姆齐(Ramsey)定理是要解决以下的问题：要找这样一个最小的数n，使得n个人中必定有k个人相识或l个人互不相识。

$R(k,l)=n$

$R(3,3)=6,R(3,4)=9$

$R(4,4)=18$

$R(5,5)$

6人行

6人行对应是Ramsey数就是$R(3,3)=6$

世界上任意挑选6个人，这6个人中，总有3个人相互认识或相互皆不认识

证明6人行如下

这个问题可以转化为完全图的着色形式即：完全图$K6$(即6个点及它们两两之间所有连边组成的图)的边红蓝二着色，证明存在同色三角形

设$K6$的顶点集合为$\{V_1,V_2,\cdots,V_6\}$

$d_r(V)$表示与顶点$V$关联的红色边的条数

在$K_6$中，有$dr(V)+db(V)=5$,有鸽巢原理可知，5个鸽子到2个笼子，至少有3条边同色

棋盘多项式

$n$个元素的一个排列可以看作是$n$个旗子在$n\times n$棋盘上的一种布局，当一个棋子置于棋盘的某一个格子时，则这个棋子所在的行和列都不允许放置任何棋子

https://blog.csdn.net/kele52he/article/details/77150025