组合数学
34．用腰的长度分别为1与2的直角等腰三角形的砖及边长为1的正方形的砖给宽度为1长度为n的路铺面，有多少方案？在所有的方案中，小三角形的砖、大三角形的砖及正方形的砖各一共用了多少块？ [解1]
设所求的铺路的方案数为an，路的右端右上角缺一块小三角形砖的铺路方案数为
bn（注意：由方案的对称性可知，路的右下角为小三角形砖的方案数也是bn）
a1=3，a2=3·3+2=11；b1=1，b2=4
(1)
// 按照路的右端所用砖的情况进行分类。右端是方形砖的方案数是an-1；右端右上角是小三角形砖的方案数是bn，右下角是小三角形砖的方案数也是bn // an=an-1+2bn an-1: bn: bn:
n
n (2)
// 右端是小三角形砖的方案数是an-1；右端是大三角形砖的方案数是bn-1 // 由（1）可推得a0=a1-2b1=1。 // 注意：a0的值不直观，只能由递推式推得 // bn=an-1+bn-1 n n-1 由（1），bn=(an-an-1)/2，将此代入（2），得 (an-an-1)/2= an-1 +(an-1-an-2)/2，即 an-4 an-1+ an-2=0 (3)的特征方程是
x-4x+1=0
2
(3) (4)
3，?=2?
(4)的两个特征根是?= 2?
n
n3。
设an=A? +B?。由a0，a1可建立方程组
?A?B?1 ???A??B?3
6
组合数学
??11?131?1??23，
?A??13?2?3?3??1?3，
?B???3?2?3?1?3，
???A??3?633，B??B?3?3?63
an?3?6?n?3?6n?
设小三角形的砖在所有的方案中一共用了cn块，小三角形的砖在右端右上角缺一块小
三角形砖的方案中一共用了dn块。 c1=4，c2=28，c0=0 d1=1，d2=8，d3=47，
cn=cn-1+2dn+2bn
(1)
dn=cn-1+an-1+dn-1 (2) 由（1），dn=（cn-cn-1-2bn）/2，将此代入（2），得 cn-4cn-1+cn-2=4an-1 因序列{an}的特征方程为 x2-4x+1=0， 可设序列{cn}的特征方程为 (x2-4x+1)2=0。
特征根为?（2重根），?（2重根）。可设
cn=(En+F)?n +(Gn+H)?
n(3)
(4)
将（4）代入（3），得
?En?F??n??Gn?H??n?4??E(n?1)?F??n?1??G(n?1)?H??n?1?n?2n?2??4an?1//an的表达式已求出???E(n?2)?F????G(n?2)?H??通过比较?4E?n?1//
n?2前的系数：
n?2?2E??4?16(3?3)?n?1
求得 E?3?13，
同理求得
G?1?33。
7
组合数学
将E，G的值代入（4），求得 F?133， H??133n，因而求得
?1?33?cn??()n???39???1?33?n??()n???
39?? (5)
c3=4c2-c1+4a2=152，
?1??33?3??3)????[152.01779]?152 9?3由（5）直接计算 c3??(// 这里的[x]表示对x就近取整 //
设在所有的方案中正方形的砖共用了cn块，正方形的砖在路的右端右上角缺一块小三
角形砖的方案中一共用了ln块。
c1=1，c2=6，c3=31，c0=0； d1=0，d2=1，d3=7。
(1) (2)
cn=cn-1+an-1+2dn dn=cn-1+dn-1 由（1）得
dn=(cn-cn-1+-an-1)/2， 将此代入（2），得
cn?4cn?1?cn?2?an?1?an?2?3?63(?n?1??n?2)?3?63(?n?1??n?2) (3)
设cn=(En+F)?n +(Gn+H)?n，将此代入（3），得
?En?F??n??Gn?H??n?4??E(n?1)?F??n?1??G(n?1)?n?2n?2????E(n?2)?F????G(n?2)?H???3?63(?n?1H??n?1?
??n?2)?3?6316(?n?1??n?2)比较系数，求得E?1631616，G?， 再回（3），得
F?，H??16316 因而有 ，
cn?(n?318)?n?(n?318)?
n用同样的方法可求得在所有的方案中，大三角形的砖总块数为
设在所有的方案中大三角形的砖共用了cn块，大三角形的砖在路的右端右上角缺一块小三角形砖的方案中一共用了dn块。 c1=0，c2=4，c3=10，c0=0； d1=0，d2=1，d3=3。
8
组合数学
cn=cn-1+2dn (1)
(2)
dn=cn-1+b n-1+dn-1 求出： Cn=(n?6139)?n?(16n?39)?
n
(2?可求得在所有方案中所用砖的总块数为
3n?318)??(n2?333n?318)?
n
通过递推关系及直接计算可验证答案正确。 解毕。
★★★第三章：容斥与鸽巢★★★
例４ 从1到2n的正整数中任取n+1个，则这n+1个数中，至少有一对数， 其中一个是另一个的倍数。
证 设n+1个数是 a1 , a2 , ··· , an+1。每个数去掉一切2的因子， 直至剩下一个奇数为止。组成序列 r1 , r2, ··· , rn+1。这n+1个数仍在 ［1 , 2n］中，且都是奇数。而[1 , 2n]中只有n个奇数 . 故必有 ri = rj = r , 则
例5 设 a1 , a2 , ··· , am是正整数序列，则至少存在k和 l , 1≤k≤ l ≤m， 使得和 ak + ak+1 + ··· + al 是m的倍数。
,若αi＞αj ，则 ai 是 aj 的倍数。
证 设
,Sh≡ rh mod m , 0≤rh≤m-1，h = 1 , 2 , ··· , m . 若存在l , Sl≡0 mod m 则
命题成立．否则，1≤rh≤m-1．但h = 1 , 2 , ··· , m．由鸽巢原理，故存在 rk = rh , 即 Sk≡ Sh，不妨设 h ＞k．则
Sh－Sk = ak+1 + ak+2 +… + ah ≡0 mod m
例６ 设 a1 , a2 , a3为任意３个整数，b1b2b3为a1 , a2 , a3的任一排列， 则 a1－b1 , a2－b2 , a3－b3中至少有一个是偶数．
证 由鸽巢原理， a1 , a2 , a3必有两个同奇偶．设这３个数被２除的余数为 xxy， 于是b1 , b2 , b3中被２除的余数有２个x，一个y．这样a1－b1 , a2－b2 , a3－b3 被２除的余数必有一个为０．
例７ 设a1 , a2 , ··· , a100是由 1和２组成的序列 , 已知从其任一数开始的顺序10个数的 和不超过16．即
ai + ai+1 +… + ai+9 ≤16，1≤ i ≤91 则至少存在 h 和 k ，k > h，使得 ah + ah+1 +… + ak = 39
证 令
，j =1 , 2 , … ,100 显然S1＜S2＜…＜S100，且 S100=(a1 + … +a10)+(a11
+ … +a20)+…+(a91 + … +a100) 根据假定有 S100≤10×16=160，
9
组合数学
作序列S1, S2 , … , S100 , S1 +39, … , S100+39 .共200项．其中最大项 S100+39≤160+39由鸽巢原理，必有两项相等． 而且必是前段中某项与后段中某项相等．设 Sk=Sh + 39，k＞h, Sk－Sh =39 即 ah + ah+1 +… + ak = 39
5.设有三个7位的二进制数：a1a2a3a4a5a6a7，b1b2b3b4b5b6b7， c1c2c3c4c5c6c7．试证存在 整数i和j，1≤i≤j≤7，使得下列之一必定成立：ai=aj=bi=bj， ai=aj=ci=cj，ai=aj=ci=cj．
证： 显然，每列中必有两数字相同，共有种模式， 有０或１两种选择．故共有·2
种选择．·2=6．现有7列， ．即必有２列在相同的两行选择相同的数字，即
有一矩形，四角的数字相等．
6. 在边长为1的正方形内任取5个点试证其中至少有两点，其间距离小于证 把１×１正方形分成四个(1/2)×(1/2)的正方形．
如上图.则这５点中必有两点落在同一个小正方形内．而小正方 形内的任两点的距离都小于
．
7．在边长为1的等边三角形内任取5个点试证其中至少有两点，期间距离小于1/2．
证：
把边长为１的三角形分成四个边长为1/2的三角形，如上图：则这５点中必有两点落在 同一个小三角形中．小三角形中任意两点间的距离都小于1/2．
10. A、B、C三种材料用作产品I、II、III的原料，但要求I禁止用B、C作原料，II不能用B作原料， III不允许用A作原料，问有多少种安排方案？（假定每种材料只做一种产品的原料）
解 按题意可得如下的带禁区的棋盘,其中有阴影的表示禁区．
10