请输入您要查询的百科知识:

 

词条 拉蒙塞数
释义

拉蒙塞问题是组合数学中鸽巢原理的一个推广.

一个最典型的例子: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条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。

 

Copyright © 2004-2023 Cnenc.net All Rights Reserved
更新时间:2025/3/4 16:14:43