3. 容斥原理与鸽巢原理
为了区分讨论的问题类型困难，区分同类型，避免重复和遗漏？？
所以引入了容斥原理和鸽巢原理
3.1 De Morgan定理
De Morgan定理的推广
是的子集
3.1 容斥原理
加法法则
事件有种产生方式，事件有种产生方式，则事件或事件之一有种产生方式。
若,则
容斥原理计数思想是
先不考虑重叠的情况，把包括于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去
例子
中2或3的倍数的个数
2的倍数是
3的倍数是
但答案不是16个，因为6,12,18在两类中重复计数，应减去16-3=13
容斥原理概念
容斥原理应用
求从1到500的整数中能被3或5除尽的数的个数
所以结果为
求六个字母的全排列中不允许出现和图像的排列数
解：6个字母全排列，,
设为作为一个元素出现的排列集：
为作为一个元素出现的排列集
为同时出现的排列数
求四个字母构成的位符号串中都至少出现一次的符号串数目
令分别为位符号串中不出现符号的集合
欧拉函数
欧拉函数是关求小于且与互素的数的个数
例子小于8且与8互素有1 3 5 7
若分解为不同素数的乘积
设到的个数中为倍数的集合为
对于即是的倍数也是的倍数
例子
定理
求不定方程,求非负整数解的数目
开始添加约束
求不定方程,求非负整数解的数目
若添加约束。
解：
设为的解，
设为的解，
设为的解，
放球问题
在放球问题中，我们引入了第二类Stirling数
的组合意义：将n个有标志的球放入m个无区别的盒子，而且无一空盒的方案数
先考虑n个有标志的球，放入m个有区别的盒子，无一空盒的方案数。
解表示第个盒子为空，
个有标志的球放入个有区别的盒子的事件全体为,
共有个
共有个
m个有区别盒子，无空盒的方案数：
错排问题
个元素依次给以标号个元素的全排列中，求每个元素都不在自己原来位置上的排列数
设为数在第位上的全体排列，，因数字不能动
因而
=
3.2 鸽巢原理(抽屉原理)
桌子有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放？，我们会发现至少会有一个抽屉里面放不少于两个苹果。这一现象就是我们所说的“抽屉原理”。抽屉原理的一般含义为：“如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有n+1个元素放到n个集合中去，其中必定有一个集合里至少有两个元素。”
例子
班级中30个人，有至少3位同学在同一月出生
例子
10双蓝袜子，12双白袜子，随机去几次就能凑成一对
什么是鸽子，什么是巢？？
证明
已知个正整数，他们全都小于或等于,证明当中一定有两个数是互质的
每个盒子里放2个相邻的球，相邻的球一定是互质的
取n+1个球，会发现一定会有一定有2个球是来自同一个盒子里
例子
从1到的正整数中任取个，则这个数中，至少有一对数，其中一个是另一个的倍数
证明
设个数是每个数去掉一切2的因子，直到剩下一个奇数为止，组成序列.
这个数仍在中，且都是奇数。而中只有个奇数
故必有
则
若,则是的倍数
设是由1和2组成的序列，已知从其任一数开始的顺序10个数的和不超过16，即
则至少存在和,使得
根据假定,有，相互不相同
做序列共200项。其中最大项
因为一共200项，最大值是199,。所以根据鸽巢原理，必有两项相等。而且必是前段中某个项与后段中某一项相等
一个抽屉里面有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件蓝色的，剩下的从红色和灰色中取,故需取能保证有5件同色的
今有无，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何？？答23
中国剩余定理
m和n是两个互质的正整数，对于任意非负整数a与b(a<m,b<n)，则必然存在正整数x使得联立的同余方程组有公解
p,q为非负整数
3.3 Ramsey 数
拉姆齐(Ramsey)定理是要解决以下的问题：要找这样一个最小的数n，使得n个人中必定有k个人相识或l个人互不相识。
6人行
6人行对应是Ramsey数就是
世界上任意挑选6个人，这6个人中，总有3个人相互认识或相互皆不认识
证明6人行如下
这个问题可以转化为完全图的着色形式即：完全图(即6个点及它们两两之间所有连边组成的图)的边红蓝二着色，证明存在同色三角形
设的顶点集合为
表示与顶点关联的红色边的条数
在中，有,有鸽巢原理可知，5个鸽子到2个笼子，至少有3条边同色
棋盘多项式
个元素的一个排列可以看作是个旗子在棋盘上的一种布局，当一个棋子置于棋盘的某一个格子时，则这个棋子所在的行和列都不允许放置任何棋子
https://blog.csdn.net/kele52he/article/details/77150025