鸽巢原理

鸽巢原理

1.简单形式

如果n+1个物体被放进n个盒子，那么至少有一个盒子包含两个或更多的物体。

例1：在13个人中存在两个人，他们的生日在同一月份里。

例2：设有n对已婚夫妇。为保证有一对夫妇被选出，至少要从这2n个人中选出多少人？（n+1）

2.加强形式

令q1,q2,...qn为正整数。如果将

q1+q2+...+qn-n+1个物体放入n个盒子内,那么或者第一个盒子至少含有q1个物体,或者第二个盒子

至少含有q2个物体,...,或者第n个盒子含有qn个物体.

例3:一篮子水果装有苹果、香蕉、和橘子。为了保证篮子内或者至少8个苹果或者至少6个香蕉或者至少9

个橘子，则放入篮子中的水果的最小件数是多少？（21件）

5.2   容斥原理及应用  

原理：集S的不具有性质P1,P2,...，Pm的物体的个数由下式给出：

|A1∩A2∩...∩Am|=|S|-∑|Ai|+∑|Ai∩Aj|-∑|Ai∩Aj∩Ak|+...+(-1)m|A1∩A2∩...∩Am|

如:m=3,时上式为：

|A1∩A2∩A3|=|S|-(|A1|+|A2|+|A3|)+(|A1∩A2|+|A1∩A3|+|A2∩A3|)－|A1∩A2∩A3|

推论:至少具有性质P1,P2,...Pm之一的集合S的物体的个数有：

| A1∪A2∪....∪Am|=|S|—|A1∩A2∩...∩Am|=

∑|Ai|-∑|Ai∩Aj|+∑|Ai∩Aj∩Ak|+...+(-1)m+1|A1∩A2∩...∩Am|

例4：求从1到1000不能被5，6，和8整除的整数的个数？

（1000-（200+166+125）+（33+25+41）-8=600）

5.３ 常见递推关系及应用

1.算术序列

每一项比前一项大一个常数d；

若初始项为h0：则递推关系为 hn=hn-1+d=h0+nd；

对应的各项为：h0，h0+d，h0+2d，....,h0+nd;

前n项的和为(n+1)h0+dn(n+1)/2

例5:1,2,3,...

例6:1,3,5,7...等都是算术序列。

2.几何序列

每一项是前面一项的常数q倍

若初始项为h0：则递推关系为 hn=h0qn-1q=h0qn；

对应的各项为: h0，h0q1，h0q2，....,h0qn
例7: 1,2,4,8,16,...

例8:5,15,45,135,...等都是几何序列;

前n项和为((qn+1-1)/(q-1) )h0

3.Fibonacci序列

除第一、第二项外每一项是它前两项的和；

若首项为f0为0,则序列为0，1，1，2，3，5，8...递推关系为(n>=2)fn=fn-1+fn-2   

前n项的和Sn=f0+f1+f2+...+fn=fn+2-1

例9:以下是Fibonacci的示例:

     1.楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法?

     2.有一对雌雄兔,每两个月就繁殖雌雄各一对兔子.问n个月后共有多少对兔子?

     3.有n*2的一个长方形方格,用一个1*2的骨牌铺满方格。求铺法总数？

4.错位排列

首先看例题：

例10：在书架上放有编号为1,2,....n的n本书。现将n本书全部取下然后再放回去,当放回去时要求每本书都不能

放在原来的位置上。

例如:n=3时:

原来位置为:123

放回去时只能为:312或231这两种

问题:求当n=5时满足以上条件的放法共有多少种?(不用列出每种放法) (44)

{1，2，3，....,n}错位排列是{1,2,3,..,n}的一个排列i1i2...in,使得i1<>1,i2<>2,i3<>3,...in<>n

错位排列数列为

0,1,2,9,44,265,....

错位排列的递推公式是:dn=(n-1)(dn-2+dn-1)(n>=3)

                    =ndn-1+(-1)n-2

5.分平面的最大区域数

   1.直线分平面的最大区域数的序列为:

      2，4，7，11，....,

     递推公式是: fn=fn-1+n=n(n+1)/2+1

   2.折线分平面的最大区域数的序列为:

     2, 7, 16,29, ...,

     递推公式是:fn=(n-1)(2n-1)+2n;

   3.封闭曲线(如一般位置上的圆)分平面的最大区域数的序列为:

     2, 4, 8, 14,...,

   递推公式是:fn=fn-1+2(n-1)=n2-n+2