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