组合数学(3)容斥鸽巢

《组合数学(3)容斥鸽巢》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ACM暑期集训组合数学（3）容斥原理鸽巢原理1容斥原理2错位排列3有限制的排列部分错位排列：n排列恰有k个位置正确的个数为C(n,k)*Dn-k4鸽巢原理例：有一样大小的红色珠子5个，蓝色珠子3个，黄色珠子4个混放在箱子里，取出多少个珠子能保证至少有3个颜色相同的？2*3+1=7取出多少个珠子能保证至少每种颜色都有1个？5+4+1=105鸽巢原理的推广6Ramsey数(瑞姆赛数)推广为一般问题：给定任意正整数a和b，存在一个最小整数R(a,b)，使得R(a,b)个人中，或者有a个人互相认识，或者有b个人

2、互不认识。称R(a,b)为Ramsey数。上界估计程序Programramseyusescrt;Constmaxn=50;Typertype=array[1..maxn,1..maxn]ofinteger;Varr:rtype;{ramsey数组}a,b:integer;{ramsey数的两个参数}Procedureinit;{输入ramsey数的两个参数}Beginclrscr;repeatwrite(‘a=’);readln(a);until(a>1)and(a<=maxn);repeatwrite

3、(‘b=’);readln(b);until(b>1)and(b<=maxn);end;ProceduremainvarI,j:integer;Beginfori:=2toador[I,2]:=I;{建立递归边界}fori:=2tobdor[2,i]:=I;fori:=3toadoforj:=3tobdoif(odd(r[i-1,j])or(odd(r[I,j-1]))thenr[I,j]:=r[i-1,j]+r[I,j-1]elser[I,j]:=r[i-1,j]+r[I,j-1]-1;writeln

4、(‘R(’,a,’,’,b,’)=‘,r[a,b]);end;Begininit;{输入参数a和b}main;{计算和输出ramsey数r（a，b）}End；程序只能估计上界，一些运行结果与精确值有一定误差。要准确计算Ramsey数，只要将程序返回的整数值逐一递减。直至递减后的n值所对应的kn图中出现了不含红色完全子图kp或蓝色完全子图kg的情形，则n+1就是精确的RAMSEY数了。