组合数学课件：基本计数原理

基本计数原理2.1和式与积式

2.2加法原理和乘法原理

2.3鸽巢原理

2.4Ramsey问题

2.5排列与组合

2.6排列与组合的进一步讨论

2.7二项式系数

2.8杨辉三角（或称贾宪三角）

2.9多项式定理

2.10集合的划分的计数2.1和式与积式2.1.1和式(Sumformula）

定义1

a0+a1+…+an称为a0,a1,…,an的和式，常简记为或(2.1.1)“∑”称为和号；“ai”称为和式的通项或累加项，“i”为通项的下标或足标，用来标识和式中不同的项。下标i的变化范围常以逻辑表达式的形式写在和号下面，简单时也以罗列的形式表示在和号“∑”的上、下方，下边指明初值，上边指明终值，其变化取由初值到终值的相继递增整数。若令Nn表示前n+1个自然数所成之集，即Nn={0,1,2,…,n}，则（2.1.1）式还可表示为

命题1

用和号∑表示的和式中，通项下标的改变不影响和式。例如都表示同一和式。当通项下标不取连续整数时，也希望能寻找一些规律，以便于用和式写出简单的表示式，下面给出一些特殊和式的例子。1.奇数做下标2.偶数做下标3.双下标4.给定数42的所有因子之和

1+2+3+6+7+14+21+42=5.求给定数42的真因子个数6.空和（由逻辑表达式不成立所致，约定空和的值为0）命题2（加法的交换律）

如果（i1,i2,…,ii）是(1,2,…,n)的一个置换，则命题3（加法的结合律）如果1≤m≤n，则命题4（乘法交换律）命题5（乘法对加法的分配律）推论·

对（2.1.1）式的求和算法

№1定义数组A(0∶N)；

№2对i=0,N

输入A(i)；

№3

S

0；（累加器S置0）

№4对i=0,N,做

S

S+A(i)；（S中存放（2.1.1）式的值）；

№5输出S；

№6结束。·

对（2.1.2）及（2.1.3）式的求和算法

№1定义数组A（0：N）；(N=2k+1)

№2对j=0,N,输入A(j)；

№3

S1

0;S2

0;

№4对j=1,N,步长取2，做

S1

S1+A(j);（S1中存放（2.1.2）式的值）

№5对j=0,N,步长取2，做

S2

S2+A(j)；（S2中存放（2.1.3）式的值）

№6输出S1,S2;

№7结束。·

对（2.1.4）式的求和算法

№1定义数组A(1：M,1：N)；

№2对i=1,M

对j=1,N

输入A(i,j)；

№3

S

0；

№4对i=1,M,做 对j=1,N,做

S

S+A(i,j)；（S中存放（2.1.4）式的值）

№5输出S;

№6结束。·

对（2.1.5）式及（2.1.6）式的求和算法№1

N

42;S

0；（累加器置0）T

0；（计数器置0）№2对k=2,N/2,做若N/k=［N/k］则

S

S+k；（S中存放42的真因子和）

T

T+1；（T中存放42的真因子数）№3打印S+1+N,T；№4结束。2.1.2积式（Productformula）与和式类似,还可以并行的讨论积式或更一般地写为注意到若附加条件xi＞0(1≤i≤n)，则即积式可转化为和式来处理。条件xi＞0并无实质性的限制，因若某个xi=0，则整个积式为0，又恰有k项取负时，可先对（2.1.8）式两边乘(-1)k，以确保xi＞0，最后再将其恢复过来。例如：（1）n的阶乘n!还可递归定义如下：0!∷=1（“∷=”取自BNF，读作定义为）n!∷=n·(n-1)!（2）矩阵An×n的迹=·

对（2.1.8）式的算法№1定义数组X(0∶N)；№2对i=0,N,输入X(i)；№3

M

1；（累乘器M置1）№4对i=0,N,做

M

M*

X(i)；№5打印M；№6结束。·

对（2.1.9）式的算法№1输入N

№2

M

1；（累乘器M置1）№3对k=2,N,做

M

M*k；№4打印M；№5结束。对（2.1.9）式亦可改用递归算法，其主体语句为ifN=0thenf（N）=1elsef（N）=N*f（N-1）;·

对（2.1.10）式的算法№1定义数组A(1∶N,1∶N)；№2对i=1,N,输入A(i,i)；№3

M

1；（累乘器M置1）№4对i=1,N,做

M

M*A(i,i);

№5打印″方阵An×n的迹是″M

№6结束。·

求 的算法№1输入N；№2

E

1；（累加器E置1）№3

T

1；（累乘器T置1）№4对k=1,N,做

T

T/k；E

E+T；№5打印E；№6结束。·

求和式 的算法№1输入N,A;

№2

S

0;B

1；№3对k=1,N,做

B

B*A;S

S+B；№4打印N,A,S；№5结束。2.2加法原理和乘法原理2.2.1加法原理（AdditionPrinciple）设A，B为两个不同类事件，若事件A有m种产生方式，事件B有n种产生方式，则“事件A或者事件B”有m+n种产生方式。用集合论的术语，加法原理也可描述如下：设S为m元集，T为n元集，如果S∩T=￠,则S∪T为m+n元集。

推广的加法原理是：如果Ti为ni元集（i=1,2,…,r），并且π={T1,T2,…,Tr}形成 的一个划分，则 为元集。加法原理的通俗说法是：部分之和等于全体。约束条件是：(1)讨论范围局限于有限集；(2)任意两个部分都不相交。若有相交的情形出现，则要用到后面讨论的包含排斥原理。

例1

小于100的正偶数有49个，小于100的正奇数有50个，则小于100的正整数有49+50=99个。2.2.2乘法原理(MultiplicationPrinciple)

设A，B为二不同类事件，若事件A有m种产生方式，事件B有n种产生方式，则“事件A与事件B”有mn种产生方式用集合论的术语，乘法原理也可描述如下：设S，T为二集，若S为m元集，T为n元集，则S与T的叉积之集合S×T为mn元集。推广的乘法原理是：如果Ti为ni元集(i=1,2,…,r)，则 元集。

推论设X为n元集，则是nr元集。这是乘法原理中取Ti=X(i=1,2,…,r)均为n元集的特殊情形。

例2

从u到v有3条不同的道路，从v到w有2条不同的道路，则从u经v到w有3×2=6条不同的道路。

例3

某高级语言的标识符规定长度最多为6位，其中第一位限取字母，其余各位可取字母，也可取数字。求所有可能出现的标识符总数。

解长为1的只有26个；长为2的由乘法原理有26(26+10)个；……长为6的由乘法原理有26(26+10)5个。最后由加法原理，所有可能出现的标识符总数为

例4

用四子于两路棋盘，能摆出34=81种两两不同的棋局；用九子于三路棋盘，能摆出39=19683种两两不同的棋局；用16子于四路棋盘，能摆出316=43046721种两两不同的棋局，用25子于五路棋盘，能摆出325=847288609443种两两不同的棋局；……用361子于十九路棋盘，能摆出3361种两两不同的棋局。

注:

本例指围棋，现代围棋采用十九路，即有19×19=361个交叉点可落黑子、白子或留空。

例5

求含有数字1的4位数的个数。

解先求不含有1的4位数的个数，即求由{0,2,3,4,5,6,7,8,9}9个数字组成的4位数的个数（第一位不得出现0）。由乘法原理，有8×9×9×9=5832个又4位数共有9999-999=9000个。因此,含有数字1的4位数的个数为9000-5832=3168。注：本例中用到了一种求补原理。提法是：由总数中去掉不满足某些性质的物件数，则剩余者即为满足该性质的物件总数。2.3鸽巢原理2.3.1鸽巢原理（Thepigeonholeprinciple）之一若在n个盒子中放有n+1个物件，则至少有一个盒子中放有两个或更多的物件。

证明若每个盒子中至多存放1个物件，则n个盒子中至多存放n个物件，但因最初已有n+1个物件，这是不可能的。请注意，鸽巢原理没有能力指出究竟哪个盒子中放有两个或更多的物件,若要做到这一点，除非逐个检查n个盒子。即应用鸽巢原理只能证明某种安排或某些现象的存在性，但却不能用来构造这种安排或找出某些现象中的具体例子。

例113个人中，至少有2个人的生日在同一个月。

例2

从1到2n的正整数中任取n+1个数，则这n+1个数中至少有一对数，其中一个数可整除另一个数。

证明设所取的n+1个数是a1,a2,…,an,an+1将序列中每个数都写成一个奇数乘以2的次幂的形式，得到相应序列

例3某次会议有n位代表参加，已知每一位代表至少认识其余n-1位中的一位，则n位代表中至少有两位认识的人数相等。

证明n位代表认识的人数有1,2,…,n-1，由鸽巢原理知至少两位代表认识的人数相等。

例4

给定m个整数a1,a2,…,am。则至少存在整数k和l(1≤k≤l≤m)，使得证明构造序列s1=a1,s2=a1+a2,…,sm=a1+a2+…+am (2.3.1)

则有s1＜s2

＜…＜sm

如下分两种情况讨论：

(a)若有一个sh,使m|sh,则命题已明（此时k=1,l=h）;

(b)设若单调增序列（2.3.1）式中任何一个元素都不能被m整除。令sh≡rh(modm)(h=1,2,…,m),则因0＜rh＜m，由鸽巢原理，序列r1,r2,…,rm相对于序列1,2,…,m-1必要选中i≠j（不妨设i＜j）使ri=rj,从而这时

例5设a1,a2,a3为任意三个整数，(b1,b2,b3)为(a1,a2,a3)的一个任意置换，则(ai-bi)(i=1,2,3)中至少有一个是偶数。

证明由鸽巢原理a1,a2,a3中至少有两个数同为奇数或同为偶数，不妨设a1,a2同为奇数，又b1,b2中至少有一个是奇数，从而a1-b1与a2-b2中至少有一个偶数,原因是二奇数之差必为偶数。当a1,a2同取偶数时，讨论过程类似（因二偶数之差必为偶数）。2.3.2鸽巢原理之二设有n个正整数q1,q2,…,qn,若将 个物件放进n个盒子，则或者第一个盒子中至少放进了q1个物件，或者第二个盒子中至少放进了q2个物件，……或者第n个盒子中至少放进了qn个物件。

证明若第i个盒子中至多放进qi-1个物件(i=1,2,…,n)，则放进n个盒子的物件总数是这与最初放进的物件总数是矛盾。

注：鸽巢原理之一是鸽巢原理之二当qi(i=1,2,…,n)都取2时的特殊形式。

推论1

m个物件放进n个盒子，则至少有一个盒子里放的物件数不少于［(m-1)/n］+1。

推论2

若n(r-1)+1个物件放进n个盒子中，则至少有一个盒子放进了r个或更多的物件。

推论3

若q1,q2,…,qn是n个正整数，而且，则qi(i=1,2,…,n)中至少有一个不小于r。

例1

把两个大小不等的同心圆盘都划分成20个相等的扇区。在大圆盘的20个扇区中分别填入10个0及10个1,对小圆盘只要求用0或1两种数字把扇区填满而不限制双方的个数。断言存在某种配合，可使小圆盘的20个扇区中至少有10个与大圆盘的对应扇区中数字相同。

证明固定小圆盘并让大圆盘依次转过20个扇面,这使小圆盘的每个扇面恰碰到10次与自己相同的数字。对整个小圆盘来说，相同的数字总数应是20×10=200。从而大圆盘平均转过一个扇面使大小圆盘对应扇面数字相同者应是200/20=10。根据鸽巢原理，至少有一次，其中对应扇面数字相同者不少于10。

例2

（P.ErdosandA.Szekeres,1935）试证任意n2+1个实数所成的序列a1,a2,…,an2+1中都含有一个长为n+1的递增子序列或递减子序列。

证明证明思路:假定没有长为n+1的递增子序列，必可推得存在长为n+1的递减子序列或反之。对每个k(k=1,2,…,n2+1)，令mk表以ak为首的最长递增子序列的长度。若有一个mk＞n,则命题已明。下设对每个k(k=1,2,…,n2+1),mk≤n，即假设不存在任何一条长度大于n的递增子序列。因对每个k(k=1,2,…,n2+1),mk≥1，这使n2+1个正整数m1,m2,…,mn2+1都落在1,2,…,n之间。由鸽巢原理之二的推论2（取r=n+1的特殊形式），上述n2+1个整数中必有n+1个完全相同。不失一般性，令其中，1≤k1＜k2＜…＜kn+1≤n2+1。下证ak1,ak2,…,akn+1构成一长为n+1的递增子序列。用反证法，设若不然，即存在某个i(i=1,2,…,n)使 ，则因ki＜ki+1，故可对以 为首的最长递增子序列前再置以而得到一条以为首的最长递增子序列，但这将导致 ，与 矛盾。结论是 ，而这对每个i(i=1,2,…,n)都是对的，从而有 。2.4Ramsey问题2.4.1

Ramsey问题

问题16人行，必有3人或互相认识，或互不认识。类似于问题1，还有问题2和问题3。问题29人行，或有3人互相认识，或有4人互不认识。

问题318人行，定有4人或互相认识，或互不认识。上述问题，可用图论的方法予以解决。即将n个人视为n个顶点（设n个顶点中任意3点不共线），并构造n点完全图Kn，对Kn中的边染以红、蓝两种颜色，2人相识染红色，不相识染蓝色，最后求证图中必存在同色三角形，或同色四边形。对于问题1，转化为图论问题即为如下定理：

定理1

K6中的边染以红、蓝两种颜色，则必存在同色三角形。证明令K6=(V,E),V={v0,v1,…,v5}，任选一点v0，由鸽巢原理，v0与其余5个顶点所成的5条边中必有3条属于同色，不妨设为(v0,v1),(v0,v2),(v0,v3)，且均系红色。此时，若v1,v2,v3两两连线中有一边为红色，设为(v1,v2)，则v0,v1,v2形成一同色红色三角形；又如果v1,v2,v3两两连线无一为红，则v1,v2,v3形成一同色蓝色三角形。如图2.4.1所示。注意:6是染两色时出现同色三角形的最小点数。若取5点，则可举出反例(如图2.4.2所示)，即可使K5不存在同色三角形。图2.4.1K4二染色(带有限制)图2.4.2K5二染色

定理2

K9中的边染以红、蓝2色，则或有一同色三角形，或有另一同色完全四边形。

证明第一步：若将K9染色，则其中必存在一点，从这点到其余8点的边中，同色者不等于3。设若不然，K9中每个点与其余8个顶点所成之边都是恰染3条红色（或蓝色），现从每个端点统计各点引出的这些红色（或蓝色）边的总数应是3×9=27，但这是不可能的，因每条边关联两个端点，对这种统计，所有点引出的红色（或蓝色）连边的总数应为偶数。结论是，必存在一点，从该点到其余各点的边染红色（或蓝色）者一定大于3或小于3。

第二步：（1）设从v0向其余8点引出的边中，染红色者多于3条，即至少有4条，不妨设为(v0,v1),(v0,v2),(v0,v3),(v0,v4)。再看v1,v2,v3,v4所成完全图K4，若有一红色边，则其两端点连同v0已构成红色三角形,否则全为蓝色，这时v1,v2,v3,v4就构成一蓝色完全四边形。

（2）设从v0向其余8点引出的边中，红色边少于3条，即至多有2条，这时从v0引出的蓝色边至少会有6条，不妨设为(v0,v1),(v0,v2),…,(v0,v6)。再看v1,v2,v3,v4,v5,v6所成完全图K6，由定理1，其中若有红色三角形，则结论已真；若K6中有蓝色三角形，则其3个顶点连同v0即构成一蓝色完全四边形，结论亦真。由（1）及（2），定理得证。注意：当n＞9时，定理2自然成立。但当n=8时，可举出反例(如图2.4.3所示)，即可使其既无同色三角形，又无同色完全四边形。图2.4.3K8二染色

定理3

若将K18染以红、蓝两色，则一定会出现同色完全四边形（或称单色四面体）。

证明设K18的点集为V={v0,v1,…,v17}，考察v0到其余各点引出的17条边，因只有红、蓝两色，由鸽巢原理，至少有9条边染以红色（或蓝色），进一步，考察这9条边与异于v0的9个端点所成的完全图。由定理2，若K9中有一同色蓝色完全四边形，则问题已明；若K9中只有同色红色三角形，该三角形的3个顶点连同v0即已构成一个红色完全四边形。

与前边问题类似，18是染两色且有同色完全四边形的最少点数。即可以构造17点染两色的K17，使其中不存在同色完全四边形。其方法如下：对K17的点集V={v0,v1,…,v16}各点的下标，构造集合X、Y，使得X={1,2,4,8,9,13,15,16}

Y={3,5,6,7,10,11,12,14}

对i,j∈{0，1，2,…，15，16}，按以下规则染色：当|i-j|∈X时，(vi,vj)染红色；当|i-j|∈Y时，(vvi,vj)染蓝色。这样构造的K17不存在同色完全四边形。作为练习，请读者画出该图。将前面的问题加以推广，对于K17可有如下定理：

定理4

若将K17的边染以红、蓝、黄三色，则一定会出现一个同色三角形。

证明设V={v0,v1,…,v16}为K17的点集，任取一点v0，在v0与其余16点相连的边中，因染有三色，由鸽巢原理知至少有［16/3］+1=6条边染以同色。不妨设(v0,v1),

(v0,v2),…,(v0,v6)这6条边染为红色。考察v1,v2,v3,v4v5,v6组成的完全图K6，分两种情况讨论：

（1）如果该K6中有一条边为红色，设为(v1,v2)，则v0,,

v1,v2所成三角形已是同色三角形，定理得证。（2）如果该K6中没有红色边，即只染有黄、蓝两色，则由定理1，这个K6中就有同色三角形，定理同样为真。特别地，定理4中的17点恰是染三色时的最少点数，亦即K16用三色涂染时，可以构造一种图形，使得其中不存在同色三角形。

考虑四位的二进制数所成的集合V={0000，0001，0010,…,1111},若对V中的每个元素，施行按位加运算“+”，即不考虑进位，则（V,+）构成一16阶交换群，其中，0000为幺元。将V\{0000}分成三个不封闭的子集v1,v2,v3,

：v1={1100，0011，1001，1110，1000}

v2={1010，0101，0110，1101，0100}

v3={0001，0010，0111，1011，1111}然后构造图Γ，使其顶点与群的元素对应，并按如下方法进行三种颜色染色：

当x+y∈Vi时，边（x,y）染以颜色i，当x∈Vi时，边（0000，x）亦染以颜色i。这样构造的图Γ不存在同色三角形。定理1和定理4分别是对完全图K16和K17用两种、三种颜色染色，证明存在同色三角形及最少点数的问题。若令r（3,3;2）(可简记为r（3，3）或r2)表示用两种颜色涂染完全图的边存在三角形的最少点数，即有r(3,3;2）=r(3，3）=r2=6这就是Ramsey问题中的Ramsey数。

若进一步将用两种、三种颜色扩展到用任意有限（不妨设成m）种颜色涂染完全图的边，则有r1=3，r2=6，r3=17，有人证明了r4=65。找出rm的准确值是件困难的事情，目前仅知道以上几种。

定理5

rm≤m·(rm-1-1)+2。

证明若令t=m·(rm-1-1)+2，从完全图Kt的任一顶点v0引出的m·(rm-1-1)+1条边中，由鸽巢原理必有rm-1条染为同一种颜色，不妨设(v0,v1),(v0,v2,…,(v0,vrm-1)均为红色。v1,v2,…,vrm-1构成一完全图Krm-1

，若当

（1）Krm-1

中有一条红色边，比如（v1,v2)，则v0,v1,v2就形成一红色三角形。定理亦真。（2）Krm-1

中没有红色边，则因其rm-1条边只染有m-1种颜色，根据rm-1的定义知，这个Krm-1中必有一同色三角形。定理亦真。推论1

证明用数学归纳法。

(1)基础步：当m=1时，r1=3≤1+1+1，不等式成立；

(2)归纳步：设小于等于m-1时命题成立。由定理5知rm≤m!(rm-1-1)+2

由归纳假设得即这就证明了对m结论亦成立。命题得证。推论2

rm≤［m!·e］+1。证明因为注意到

推论3

rm≤3m!。证明因rm≤［m!e］+1＜m!e+1＜3m!+1，故rm≤3m!。一般地，对p,q∈Z+，

r(p,q)∈Z+。对n∈Z+，n≥r(p,q)，若对完全图Kn的边任意染以红、蓝两色的一种，则染色后Kn中或存在一红色Kp，或存在一蓝色Kq。

Ramsey数r(p,q;2)简记为r(p,q)，对定理2（问题2）即为r(3,4;2)=r(3,4)=9

又已知r(3,5)=14，r(4,4)=18（定理3）。许多教科书中都有关于已知的、为数不多的一些r(p,q)的列表，其中有的仅给出了上下界。

定理6

设p,q∈Z+，则对Ramsey数r(p,q)有

(1)r(p,q)=r(q,p);

(2)r(p,1)=r(1,q)=1;

(3)r(p,2)=p,r(2,q)=q。

证明

(1)由Ramsey数的对称性可得。

(2)是显然的。

(3)的第一式指，若Kp中有一条边染以红、蓝二色之一，则显见该边已构成一红色（或蓝色）完全子图K2;若不存在红色（或蓝色）K2，则Kp全染以蓝色（或红色），那么，Kp便构成了一蓝色（或红色）完全子图。由Ramsey数的对称性有r(2,q)=q。

定理7

对p,q∈Z+，p≥2,q≥2有r(p,q)≤r(p,q-1)+r(p-1,q)(2.4.1)

证明令r(p,q)≤r(p,q-1)+r(p-1,q)=n，考虑这n个点构成的完全图Kn，将Kn着以红、蓝二色。需要证明的是必定或出现红色完全子图Kp，或出现蓝色完全子图Kq。为此，从这n个点中任选一点v，考虑v与其余n-1个点连线所成的n-1条边，设这n-1条边中有红色n1条，蓝色n2条，这时n1+n2+1=n=r(p,q-1)+r(p-1,q)

如下分情况讨论：

(1)若n1≥r(p-1,q)，可考察n1条边所有异于v的端点构成的完全子图Kn1。这时，Kn1中必或有红色完全子图Kp-1，或有蓝色完全子图Kq。若是后者，则结论已明，若是前者，则红色Kp连同v点一起便构成红色子图Kp。命题亦真。(2)若n1＜r(p-1,q)，则n2+1＞r(p,q-1)。于是，n2≥r(p,q-1)。剩下的讨论类似于(1)。无论是(1)还是(2)，都证明了Kn上必定或出现红色Kp，或出现蓝色Kq。本定理当r(p,q-1)和r(p-1,q)都为偶数时，(2.4.1)式的不等式严格成立。事实上，当r(p,q-1)和r(p-1,q)都为偶数时，有r(p,q)≤r(p,q-1)+r(p-1,q)-1

令 n=r(p,q-1)+r(p-1,q)-1

设v是完全图Kn上的任意一点，则v恰是n-1条边的公共端点。由于n-1是偶数，因此这些边中可能红、蓝边均为偶数,也可能红、蓝边均为奇数。如下证明Kn上至少有一点vi，它恰是偶数条红边的公共端点。采用反证法，用tj表示与vj关联的全部红边数，j=1,2,…,n。若tj无一为偶，则t=t1+t2+…+tn也是奇数，从而，Kn上的全部红边数 ，矛盾。因vi是恰与偶数条红边关联的公共顶点，所以，以vi为一端的r(p,q-1)+r(p-1,q)-2条边中，或有不少于r(p,q-1)条红边,或有不少于r(p-1,q)条蓝边（因红边不多于r(p,q-1)-2条）。若是前者，则vi连同与之关联为红边的其余r(p,q-1)个端点构成的完全图中，按r(p,q-1)的定义，一定或存在同色完全子图Kp

，或存在同色完全子图Kq

。若是后者，结论亦然。定理8(2.4.2)

证明对p+q施用归纳法。

(1)基础步：只要p、q中有一个为1，或有一个为2，(2.4.2)式中的等号成立。p+q≤5时，易证(2.4.2)式成立。(2)归纳步：设小于等于p+q-1时(2.4.2)式恒为真，对p+q，据定理7和归纳假设，有

定理9

对p∈Z∧p≥2,有

r(p,p)≥2p/2 (2.4.3)

证明当p=1时，r(1,1)=1,21/2= ，(2.4.3)式不成立；当p=2时，r(2,2)=2=22/2，(2.4.3)式成立。对p≥3,设V={v1,v2,…,vn}是完全图Kn的顶点集，若用红、蓝二色对Kn的边着色，由于每边有且仅有两种可能的染色选择，所以，共有种不同的着色方案。用Sn表示全部双色Kn所成之集,则令事实上，从n个顶点中确定p个顶点，共有种不同方案,而对于p个确定的顶点，Kp上条边全着红色只有一种可能，故包含某特定红色Kp的双色Kn恰有 个。当2p/2＞n时,有其中,基于以下事实:

当p=3时，该式成立，对于不小于3的一切整数p，有p!＞2p-1，对于不小于4的一切整数p，又有2p-1≥2p/2+1。由对称性，不难证得对蓝色类似有其中，={S|S∈Sn

且蓝色Kp

S},Sn为双色Kn所成之集。

综上所述，只要完全图顶点数n＜2p/2，则必存在这样的双色Kn，其上不含任何同色Kp。故知r(p,p)≥2p/2

2.4.2Ramsey定理

1.先将r(p,q;2)推广到r(p,q;k)，k为任一正整数

采用图论的术语：r(p,q;k)为满足如下条件的最小正整数n。用两种颜色对Kn染色时，可用同一种颜色涂染Kn的任意2点连线（一边）；任意3点（不共线）所成三角形的边；任意4点（不共面）所成四面体的棱；……任意k点所成的完全图Kk的边（有些教科书中称其为k级边，相应地，称n个点连同其所有k级边所成之完全图为k级完全图，记为

，常称其为超图）。则Kn中或者存在p点完全子图Kp，其上的所有k级边全染为同一颜色；或者存在q点完全子图Kq，其上的所有k级边全染为同一颜色。

采用集合论的术语：对n元集合V={v1,v2,…,vn}，当n充分大时，对V的2元子集族S={X|X

V,|X|=2}，及S的任一2-拆分{S1,S2}，使得或者存在V的p元子集V1，满足V1的2元子集族包含在S1中;或者存在V的q元子集V2，满足V2的2元子集族包含在S2中。

2.将r(p,q;k)推广到r(p1,p2,…,pm;k)

r(p1,p2,…,pm;k)表示用m种颜色对Kn的k级边染色，寻求使Kn存在pi点完全子图Kpi，其上的所有k级边全染为同一颜色的最小的正整数n，其中i∈{1,2,…,m}。或者表示某个最小的正整数n，对这种n元集V的k元子集族，及其上的任一m-拆分{S1,S2,…,Sm}，存在V的pi元子集Vi，满足Vi的k元子集族包含在m-拆分的某类中，其中i∈{1,2,…,m}。定义设V={v1,v2,…,vn},V的k元子集族记为{S1,S2,…，Sm}称为ρk(V)的一个m-拆分 ,i≠j,Si∩Sj=￠,这里不要求Si≠

￠定理10

Ramsey数证明设V={v1,v2,…,vn}，令,易见ρ1(V)={{v1},{v2},…,{vn}}设{S1,S2,…,Sm}是ρ1(V)的任一m-拆分，即S1∪S2∪…∪m=ρ1(V),Si∩Sj=￠,i≠j

这相当于有 只鸽子飞进了m个鸽巢。由鸽巢原理可知，一定有一个鸽巢Si飞进了不少于pi只鸽子，即存在包含pi个元素的子集Vi

V，且ρ1(Vi)

Si。以上只是证明了r(p1,p2,…,pm;1)≤n，进一步,为了证明r(p1,p2,…,pm;1)≥n，只需在n-1个元素所成子集V′={v1,v2,…,vn-1}上找到一种m-拆分，使得在该拆分下，不存在包含pi个元素的子集Vi

V′，满足ρ1(Vi)

Si(i=1,2,…,m)。事实上，由于因而，总存在V′上的m-拆分{S1,S2,…,Sm},使得|Si|=pi-1,i=1,2,…，m

综上所述，即得

定理11

对于不小于k的一切正整数p,q，有r(p,k;k)=p,r(k,q;k)=q

证明只证前者，后者可由对偶原理给出。设V={v1,v2,…,vp}，ρk(V)={X|X

V,|X|=k}，令{S1,S2}是ρk(V)的任一2-拆分，即S1∪S2=ρk(V),S1∩S2=￠若S2≠￠，即存在X∈S2，则X

V,|X|=k，即找到了一个包含k个元素的子集X,使得

若S2=￠,即ρk(V)=S1，这表明V正是要找的子集，它包含了p个元素，并有ρk(V)=S1

S1

故有 r(p,k;k)≤p

另一方面，对于任意一个至多只有p-1个元素的集合V′，在ρk(V′)上总存在这样的2-拆分{S1,S2}，其中令S2=￠。于是在V′上既不存在包含p个元素的子集V1，满足ρk(V1)

S1,也没有包含k个元素的子集V2，满足ρk(V2)

S2。因此有r(p,k;k)≥p。定理11得证。

定理12

设p,q是超过k(k≥1)的整数，则有递归关系式

r(p,q;k)≤r(r(p-1,q;k),r(p,q-1;k);k-1)+1

证明设V={v1,v2,…,vn}，n=r(r(p-1,q;k),r(p,q-1;k);k-1)+1ρk(V)={X|X

V,且|X|=k}令{S1,S2}是ρk(V)上的一个2-拆分，即有S1∪S2=ρk(V),S1∩S2=￠

又设V′=V-{vn}={v1,v2,…,vn-1}

对ρk-1(V′)总可构造2-拆分{A1,A2},使满足Ai={Y|Y

V′,|Y|=k-1且Y∪{Vn}∈Si},i=1,2

注意到n-1是Ramsey数r(r(p-1,q;k),r(p,q-1;k);k-1)。于是，根据Ramsey数的定义，在V′上或者存在包含r(p-1,q;k)(≥p-1)个元素的子集Y1，满足ρk-1(Y1)A1，从而存在包含p个元素的V1=(Y1∪{vn})V，满足ρk(V1)S1。在V′上，或者存在包含r(p,q-1;k)(≥q-1)个元素的子集Y2，满足ρk-1(Y2)A2，从而存在包含q个元素的子集V2=(Y2∪{Vn})

V，满足ρk(V2)

S2。这就证明了r(p,q;k)≤n。定理得证。

定理13（Ramsey定理）

Ramsey数r(p1,p2,…,pm;k)存在,其中，pi≥k≥1，i=1,2,…,m。

证明对m施行归纳法。

(1)基础步：先证当m=2时，r(p,q;k)的存在性。事实上，由定理10知r(p,q;1)=p+q-1存在。假设h≤k-1时，r(p,q;h)都存在,下证r(p,q;k)也存在。由定理11知，r(p,q;k)=p，r(k,q;k)=q，其中p,q≥k。进而利用定理12可得r(p,q;k)≤r(r(p-1,q;k),r(p,q-1;k);k-1)+1

r(p-1,q;k)≤r(r(p-2,q;k),r(p-1,q-1;k);k-1)+1

r(p,q-1;k)≤r(r(p-1,q-1;k),r(p,p-2;k);k-1)+1…经有限步迭代与归纳，最终r(p,q;k)的上界一定是一个关于r(r(p,k;k),r(k,q;k);k-1)=r(p,q;k-1)的多层嵌套表达式，根据假设，这个上界存在，从而r(p,q;k)存在。

（2）归纳步：假设定理对m-1成立，下证r(p1,p2,…,pm,k)存在。设V={v1,v2,…,vn},其中n=r(p1,p2,…,pm;k)令{S1,S2,…,Sm}是V的任一m-拆分，即有S1∪S2∪…∪Sm=ρk(V);Si∩Sj=￠,i≠j

则{S1,S2,…,Sm-2,Sm-1∪Sm}是ρk(V)的一个(m-1)-拆分。

由基础步可知r(pm-1,pm;k)存在，且不小于k,再由归纳假设知，r(p1,p2,…,pm-2,q;k)也存在,其中q=r(pm-1,pm;k)。若n≤r(p1,p2,…,pm-2,q;k)，则定理已明。现设n＞r(p1,p2,…,pm-2,q;k)。由Ramsey数的定义知，在V上，或者存在某个包含pi个元素的子集Vi，有ρk(Vi)Si,i∈{1,2,…,m-2};或者存在包含q个元素的子集Y

V，使得ρk(V)

(Sm-1∪Sm)

由于Sm-1∩Sm=￠，所以总存在ρk(Y)的一个2-拆分{Am-1,Am}，即有Am-1∪Am=ρk(Y),Am-1∩Am=￠使得

对于q=r(pm-1,pm;k)和2-拆分{Am-1,Am}，根据Ramsey数的定义知，或者存在包含pm-1个元素的子集Vm-1

Y

V，满足ρk(Vm-1)

Am-1

Sm-1，或者存在包含pm个元素的子集Vm

YV，满足ρk(Vm)

Am

Sm。

总之，至少存在一个包含pi个元素的子集Vi

V，使得ρk(Vi)

Si,i∈{1,2,…,m}Ramsey定理得证。推论1

Ramsey数r(p1,p2,…,pm;2)≤r(p1-1,p2,p3,…,pm;2)+r(p1,p2-1,p3,…,pm;2)+…+r(p1,p2

，…,pm-1;2)-m+2

其中，整数pi≥2,i=1,2,…,m。提示:可令rm(i)=r(p1,p2,…,pi-1,pi-1,…,pm;2),i=1,2,…,m，于是n=rm(1)+rm(2)+…+rm(m)-m+2

=(rm(1)-1)+(rm(2)-1)+…+(rm(m)-1)+2

然后，用m种颜色给完全图Kn的边集着色，每边着一色。换言之，可对Kn的边集E构造m-拆分{E1,E2,…,Em}，使得 ,i≠j;接着证明在边集E上，无论怎样进行m-拆分，Kn上总存在一个同色的Kpi,i∈{1,2,…,m}。推论2

Ramsey数

推论3

若用rm表示p1=p2=…=pm=3的Ramsey数r(p1,p2,…,pm;2)，则有递归关系rm≤m·(rm-1-1)+2

此即定理5。

证明由推论1，欲证这一递归关系，只需证：恰存在一个pi=2，其余都等于3的广义Ramsey数r(p1,p2,…,pi-1,2,pi+1,…,

pm;2)不超过rm-1，其中i=1,2,…,m。只证r(2,3,3,…,3;2)≤rm-1，余类同。

令n=rm-1,并用m种颜色c1,c2,…,cm给完全图Kn的边集着色，每边着一色。若Kn上有颜色为c1的边，证明Kn上存在着颜色c1的同色K2；若Kn上颜色c1未出现，即至多用了m-1种颜色于Kn的边集,结合Ramsey数的定义，在Kn上总存在某种同色K3，其颜色为c2,c3,…,cm中的一种。最后，由推论1和可证的m个不等式，有rm≤m·rm-1-m+2=m·(rm-1-1)+2

例1

r(3,3,3;2)=17。利用推论3给出的递归关系，有r(3,3,3;2)≤3(r2-1)+2

注意到r2=r(3,3)=6，故r(3,3,3;2)≤17。另一方面，由定理4的反例知，可构造出边集有三色的K16，其上不存在同色K3,从而，r(3,3,3;2)=17。

例2

设整数集H={1,2,…,rm}，其中，Ramsey数rm=(3,3,…,3;2)中的3有m项。那么可以证明，对于H上的任一m-拆分{H1,H2,…,Hm}，总存在某个Hi,i∈{1,2,…,m}，在Hi上有x,y和z(不必相异),满足方程x+y=z。

证明以H为顶点集构造完全图Kn,其中,n=rm。用m种颜色给Kn的边着色，每边一色，其中，给边(i,j)着第k种颜色(当且仅当|i-j|∈Hk,k=1,2,…,m)。据Ramsey数的定义知，Kn上至少存在一同色K3。不妨设该K3的顶点为a,b,c，且有a＜b＜c，它的边都着第i种颜色。令x=c-b,y=b-a,z=c-a，则x,y,z∈Hi，且满足方程x+y=z。

例3

在通信中，由于信道噪声等意外因素的种种干扰，某些字母被认为是“极易混同”的。为了避免这种弊病，可以考虑能否从现有字母表中抽出一尽可能大的子集，使得该子集中任意二字母在任何通信环境下不会混同，或者让可能混同的概率几乎为零。

解设字母表为A={a,b,c,…,x,y,z}以A为顶点集构造完全图K26，两顶点Vi,Vj∈A,(i≠j)，连一条红边的充要条件是二者极易混同,连一条蓝边的充要条件是Vi和Vj间不易混同。问题转化为在K26上寻找最大的蓝色完全子图。该子图的顶点集即为不易混同的字母子集。

实际上，从26个字母中剔除容易混同的字母后，往往所剩无几。进一步的考虑就是对长度大于1的符号串寻找最大的非混符号串子集。如对串长等于2的串集，令A×A={(x,y)|x∈A∧y∈A}构造以A×A为顶点集的完全图K26×26，点(x1,x2)与(y1,y2)连一红边当且仅当如下三条件中任一成立：(1)(x1,y1)，(x2,y2)在K26×26中都是红边，即x1与易混，且x2与y2易混。

(2)x1=y1,(x2,y2)在K26×26

中是红边，即x1与y1相同，且x2与y2易混。

(3)x2=y2,(x1,y1)在K26×26

中是红色，即x1与y1易混，且x2与y2相同。

在K26×26上凡不是红边的均染蓝边。图论中，把图K26×26称为K26和K26的正规积，记为K26

·

K26

。这里关心的是K26

·

K26上最大蓝色完全子图的顶点集Vw。若用α(K26,K26)表示Vw中顶点数，则Z.Hedrlin于1966年证明的结果可述为定理14。

定理14

α(Km·Kn)≤r(p,q;2)-1,其中，Ramsey数r(p,q;2)中p=α(Km)+1,q=α(Kn)+1。2.5排列与组合

定义1(排列（Permutation）)设m元集A={a1,a2,…,am}，从A中取出n个不同元素按次序排列，称为A的一个n排列，其个数称为n排列数，记作P(m,n)或。当n=m时，A的n排列又称A的全排列，其个数P(m,m)又称全排列数。命题1

证明

A的一个n排列由n个不同的元素组成，其中第一位有m种可能。第二位有m-1种可能；……第n位有m-(n-1)种可能。由乘法原理，m元集A的不同排列数为

推论

P(m,m)=m!。

例1

从A={a,b,c}中任取两个不同的字母构成的字共有3×2=6个。罗列如下：ab,ac,ba,bc,ca,cb

例23个物件分放4个不同的盒子中，要求每个盒子至多放一个物件的放法共有4×3×2=24种。

定义2(组合（Combination）)

设m元集A={a1,a2,…,am}，从A中取出n个不同元素构成一组，称为A的一个n组合，其个数称为n组合数，记作C(m,n)，

命题2

由m个不同的元素共可构成P(m,n)/n!种组合。即C(m,n)=P(m,n)/n!。

证明由定义n组合与n排列的区别在于前者不计较元素的先后顺序，因此由每个n组合可以作出n！个不同的n排列。于是若有C(m,n)种n组合，则有C(m,n)*n!种排列,因此C(m,n)=P(m,n)/n!。

推论1

任意n个相继的正整数之积可被n！整除，即有

推论2

推论3

C(m,n)=C(m,m-n)。

推论4

m元集A的n元子集的个数等于C(m,n)。

推论5

设m元集A={a1,a2,…,am},其字典序如下标所示，则从A中每次取出满足条件 的n个元的方式数等于C(m,n)。

证明A的任一组合都可调整为 并使其满足 ；另一方面，任一满足条件 的n个元都是A的一个n组合。

例3

平面上任三点都不共线的25个点，可形成多少条直线？可形成多少个三角形？

解

25点中任取2点即可惟一确定一条直线，故可形成C(25,2)=25!/(2!23!)=300条直线；同理，任取3点即可惟一确定一个三角形，故三角形的数目等于C(25,3)=25!/(3!22!)

=2300。

例4

用26个英文字母能构成多少个含有3个、4个或5个元音的长为8位的单词？其中，一个字母出现在单词中的次数不限。）

解对于含有3个元音（Vowel）的长为8位的单词,8位中任三位都可是元音，故共有C(8,3)种不同的方式,每种方式有53种可能，其余5位都是辅音(Consonant)有215种可能，从而具有3个元音的单词数为C(8,3)53215=(8!/3!5!)53215

同理，含有4个元音的单词数为C(8,4)54214=(8!/4!4!)54214

含有5个元音的单词数为C(8，5)55213=(8!/5!3!)55213

从而，满足题设的单词共有8!(53215/3!5!+54214/4!4!+55213/5!3!)·求的算法№1输入M，N；

№2

P1;M1

M+1

№3对K=1,2,…,N,做

M1

M1-1;P

P*M1

№4打印M,N,P

№5结束。

·

求 的算法

№1输入M,N;

№2

C

1;M1

M+1;

№3对K=1,2,…,N,做

M1

M1-1;C

C*M1/K;

№4打印M,N,C;

№5结束。

·

生成n!个全排列的错位置数算法当n=1，排列方式只有一种，就是1。当n=2时，先将惟一的1排列1写出两次，并错位置以2，即得两个2排列如下：1221

当n=3时，先将两个2排列分别写出3次，并错位置以3，即得3!=6个3排列如下：123

132

312

321

231

213

当n=4时，先将6个3排列分别写出4次，并错位置以4，即得4!=24个4排列。（请仿上法自