6 容斥和鸽巢
我想容斥就是把不好算的补集的并集转化为求交集。交集是很好球的了。
鸽巢比较难的一个地方就是，如何构造鸽巢。
6-1 且容且斥
容斥原理的形式
6-2 容斥的精妙
求从1到500的整数中能被3或5除尽的数的个数。
求不超过120的素数个数
欧拉函数
在数论，对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。它又称为Euler's totient、function、φ函数、欧拉商数等。
例如φ(8)=4，因为1,3,5,7均和8互质。 从欧拉函数引伸出来在环论方面的事实和拉格朗日定理构成了欧拉定理的证明。
φ函数的值
通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn)，其中p1, p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1（唯一和1互质的数就是1本身）。 (注意：每种质因数只一个。比如12=223，那么φ（12）=12（1-1/2）(1-1/3)=4)
若n是质数p的k次幂，φ(n)=pk-p(k-1)=(p-1)p^(k-1)，因为除了p的倍数外，其他数都跟n互质。
设n为正整数，以 φ(n)表示不超过n且与n互素的正整数的个数，称为n的欧拉函数值，这里函数φ：N→N，n→φ(n)称为欧拉函数。
欧拉函数是积性函数——若m,n互质，φ(mn)=φ(m)φ(n)。
特殊性质：当n为奇数时，φ(2n)=φ(n), 证明与上述类似。
6-3 回忆过去，容斥新解
- 求不定方程x1+x2+x3=15,求非负整数解的数目
C(n+b-1,b) = C(3+15-1,15)
若附加约束为0 ≤ x1 ≤ 5, 0 ≤ x2 ≤ 6, 0 ≤ x3 ≤ 7, - 例 第二类Stirling数的展开式
- 例 错排问题
6-4 鸽子抢巢
“若有n-1个鸽子巢，n个鸽子，则至少有一个巢内有至少有2个鸽子。”
例 已知n + 1个正整数，它们全都小于或等于2n，证明当中一定有两个数是互质的。
例 从1到2n的正整数中任取n+1个，则这n+1个数中，至少有一对数，其中一个是另一个的倍数。
例 设a1, a2, ··· , a100是由 1和２组成的序列 , 已知从其任一数开始的顺序10个数的和不超过16．即ai + ai+1 +… + ai+9 ≤16，1≤ i ≤91则至少存在 h 和 k ，k > h，使得ah + ah+1 +… + ak = 39
6-5 看得见摸得着的鸽巢
一个抽屉里面有20件衬衣，其中4件蓝色的，7件灰色的，9件红色的，问从中任意取至少多少件保证有4件同色的？
鸽巢原理：n个鸽巢，kn+1只鸽子，至少有一个鸽巢里面有k+1个鸽子。
解：有三种颜色，三个鸽巢，要求k+1=4，K=3, kn+1=10,从中任意取至少10件才能保证有4件同色的。
一个抽屉里面有20件衬衣，其中4件蓝色的，7件灰色的，9件红色的，问从中任意取至少多少件能保证有5，6，7，8，9件同色的？
解：（5件）：第一次取正好4件蓝色的，剩下的从红色和灰色中取，n=2,k+1=5
故需取4+4×2+1=13件能保证有5件同色的
6-6 6人行，Ramsey
例 6 个人中至少存在３人相互认识或者相互不认识．
这个问题可转化为完全图的着色形式即:完全图K6(即6个点及它们两两之间所有连边组成的图)的边红蓝二着色,证明存在同色三角形．
Ramsey
- 出现ak + ak+1 + ··· + al累加,多半要构造部分和
- 出现奇偶性,整除,多半要取mod
- 反证法
- 多次利用鸽巢
网友评论