Skip to content

3. 容斥原理与鸽巢原理

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

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

3.1 De Morgan定理

De Morgan定理的推广

的子集

3.1 容斥原理

加法法则

事件种产生方式,事件种产生方式,则事件或事件之一有种产生方式。

,则

image-20211227162124381

容斥原理计数思想是

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

例子

中2或3的倍数的个数

2的倍数是

3的倍数是

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

容斥原理概念

image-20211227164127723

容斥原理应用

求从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个相邻的球,相邻的球一定是互质的

image-20220105112710648

取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条边同色

棋盘多项式

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

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