1.3.2 Ramsey数
对于任意给定的两个正整数a和b,如果存在最小的正整数r(a,b)，使得当N?r(a,b) 时，对KN任意进行红、蓝两边着色，KN中均有红色Ka，或蓝色Kb，则r(a,b)称为Ramsey数。
由命题1.3.1知：r(3,3)?6；由命题1.3.4知r(4,3)?9。从下面两图的着色方式可知：r(3,3)=6，r(4,3)=9。
目前所已知的一些Ramsey数：
b/a 2 3 4 5 6 7 8 9 2 2 3 4 5 6 7 8 9 3 3 6 9 14 18 23 28 36 4 4 9 18 25 5 5 14 25 6 6 18 7 7 23 8 8 28
9 9 36
定理1.3.1 对任意的正整数a?3,b?3，有
r(a,b)?r(a?1,b)?r(a,b?1)。
定理1.3.2 对任意的正整数a?2,b?2，有
?a?b?2?r(a,b)???。
?a?1?
本章小结：
鸽巢原理也叫做狄利克雷（P.G.Drichlet）原理。如此简单明了的事实，竟冠以著名德国数学家的名字，似乎有点“过分”，但正如我们上面所看到的，这样一个貌不惊人的几乎是不证自明的原理，却有着这么多的出乎意料的应用。而这些应用的关键就在于“鸽巢”的构筑，这也是鸽巢原理运用的难点所在。因此，要想熟练地掌握这一原理，还需同学们多加练习。
第2章 基本计数问题
第一节 加法原理与乘法原理
2.1.1 加法原则
设事件A有m种选取方式，事件B有n种选取方式，则事件A或B有m+n种选取方式。
定理2.1.1 设A，B为有限集，A1,A2,?,An满足Ai?Aj??(1?i?j?n) 则?Ai??Ai
i?1i?1nn
例1 在所有六位二进制数中，至少有连续4位是1的有多少个？
2.1.2 乘法原则
设事件A有m种选取方式，事件B有n种选取方式，则事件A以后再选取事件B有mn种选取方式。
定理2.1.1 设A，B为有限集，A?m,B?n，则A?B?A?B?m?n。
推论2.1.1 设A1,A2,?,An为n个有限集合，则
A1?A2???An?A1?A2??An。
例2 从5位先生、6位女士、2位男孩和4位女孩中选取1位先生、1位女士、1位男孩和1位女孩，共有5×6×2×4=240种方式（由乘法原理）。而从中选取一个人的方式共有5+6+2+4=17种方式（由加法原理）。
例3 在1000到9999之间有多少个各位数字不同的奇数？
第二节 排列与组合
2.2.1 集合的排列
n元集合S的一个r排列是指先从S中选出r个元素，然后将其按次序排列。一般用P(n,r)表示n元集合的r排列数。
定理2.2.1 设对于满足r?n的正整数n和r，有
n!。 P(n,r)?n(n?1)?(n?r?1)?(n?r)!
例1 从将a，b，c，d，e，f进行排列。问： （1）使得字母b正好在字母e的左邻的排列有多少种？ （2）使得字母b在字母e的左边的排列有多少种？
例2 从{1，2，?，9}中选出不同的7个数字组成7位数，要求5和6不相邻，问有多少种方法？
1n!定理2.2.2 n元集合的r圆排列数为P(n,r)?。
rr(n?r)!
例3 10个男生和5个女生聚餐，围坐在圆桌旁，任意两个女生不相邻的坐法有多少种？
2.2.2 集合的组合
n元集合S的一个r组合是指先从S中选出r个元素的一种无序选择，其组合数记为r。 Cn?n?P(n,r)n!r定理2.2.3 若0?r?n，则Cn。 ?????r!r!(n?r)!?r?
例4 从1，2，?，100中选出两个不同的数，使其和为偶数，问有多少种取法？
例5 在一个凸n(n?4)边形C的内部，如果没有3条对角线共点，求其全部对角线在C的内部的交点的个数。
解：从右图可看出，对角线在C的内部的交点与凸n边形的四个顶点
?n?1成一一对应关系，故交点的个数为???n(n?1)(n?2)(n?3)。
?4?24
?n??n?推论2.2.1 若0?r?n，则?????。
?r??n?r?
?n??n??n??n?n定理2.2.4 若对任意正整数n，有??????????????2。
?0??1??2??n?
例6 从求至少出现一个6且能被3整除的五位数的个数。
例7 从某车站有6个入口，每个入口每次只能进一个人，问9人小组共有多少种进站方案？
解： 第1个可以有6种进站方式，即可从6个入口中的任一个进站；第2个人也可以选择6个入口中的任一个进站，但当他选择与第1人相同的入口进站时，有在第1人前面还是后面两种方式，所以第2个人有7种进站方案；同理，第3个人有8种进站方案，?，第9人有14种进站方案。由乘法原理，总的进站方案数为6?7???14?726485760。
第三节 多重集合的排列与组合
2.3.1 多重集合的排列
我们通常所讨论的集合要求集合的各个元素互不相同，如果我们允许集合的元素可以相同，则这样的集合我们称为多重集合。
一般地，多重集合可表示为
M?{k1?a1,k2?a2,?,kn?an}
其中，a1,a2,?,an为M中所有的互不相同的元素，M中有ki个ai(1?i?n)，称 ki为ai的重数。ki是正整数，也可以是?，表示M中有无限个ai。
定理2.3.1 多重集合
M?{k1?a1,k2?a2,?,kn?an} 的r排列数为kr。