词条 | 拉蒙塞数 |
释义 | 拉蒙塞问题是组合数学中鸽巢原理的一个推广. 一个最典型的例子:6个人在一起,其中至少3个人互相认识或者不认识. 该问题等价于:对一个凸六边形的每条顶点连线着以蓝色或者红色,则必然至少构成一个红色或者蓝色三角形. 实际上,它可以构成2个同色三角形. 一般的拉蒙赛问题: 一对常数a和b,对应一个整数r,使得r个人中有a个互相认识,或者b个互不认识;或者a个互不认识,b个互相认识.r的最小值即为拉蒙塞数,记为R(a,b).例如R(3,3)=6,R(3,4)=9,R(4,4)=18. 关于拉蒙塞数有如下几个定理: 定理1: R(a,b)=R(b,a),R(a,2)=a. 定理2: 对任意整数a,b≥2,R(a,b)是存在的. 定理3:R(a,b)≤R(a,b-1)+R(a-1,b)-1. 定理4:R(a,b)≤C(a+b-2,a-1) (C(n,m)代表从n个数中取m个的组合数). |
随便看 |
|
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。