组合恒等式与组合

①

⑤ ②

③

④

⑥ 数学奥赛辅导 第九讲

组合恒等式、组合不等式

知识、方法、技能

Ⅰ．组合恒等式

竞赛数学中的组合恒等式是以高中排列组合、二项式定理为基础，加以推广、补充而形成的一类组合问题.组合恒等式的证明要借助于高中常见的基础组合等式.例如

0)1(2321021011111nnnnnnnnnnnnnmrmnmnmnrnrnrnrnrnrnrnnrnCCCCCCCCCCCCCCrnCCCCCC

组合恒等式的证明方法有：

①恒等变形，变换求和指标；

②建立递推关系；

③数学归纳法；

④考虑组合意义；

⑤母函数.

Ⅱ．组合不等式

组事不等式以前我们见的不多，在其他一些书籍中组合不等式的著述也很少，但是近年来组合不等式的证明却出现在国内、国际大赛上.例如1993年中国高中数学联赛二试第二大题为：

设A是一个有n个元素的集合，A的m个子集A1，A2„，Am两两互不包含，试证：

（1）miAnIC1||;11 （2）miAnmCI12||

其中|Ai|表示Ai所含元素的个数，||IAnC表示n个不同元素取|Ai|的组合数.

再如1998年第39届国际数学奥林匹克竞赛中第二大试题为：

在某一次竞赛中，共有a个参赛选手与b个裁判，其中b≥3，且为奇数.每个裁判对每个选手的评分中只有“通过”或“不及格”两个等级，设k是满足条件的整数；任何两个裁判至多可对k个选手有完全相同的评分. 证明：

.21bbak

因此我们有必要研究组合不等式的证明方法.组合不等式的证明方法有：

1．在集合间建立单射，利用集合阶的不等关系

定理，设X和Y都是有限集，f为从X到Y的一个映射，

（1）若f为单射，则|X|≤|Y|；

（2）若f为满射，则|X|≥|Y|.

2．利用容斥原理

例如：设元素a属于集族{A1，A2，„，An}的k个不同集合kiiiAAA,,,21，则在niiA1||中a被计算了k次，当k≥2时，集合kiiiAAA,,,21两两的交集共有2kC个.由于

||,12)1(12jnjiikAAakkkC在故中至少少被计算了k－1次，这样我们得到下面的不等式：

||||||111jnjiiiniiniAAAA

组合不等式（*）可由容斥公式：

||)1(||||||1)1(111ininjnjiiiniiniAAAAA删去右边第三个和式起的所有和式得到. 采用这种办法，我们可以从容斥公式得到另外一些组合不等式，只是要注意这些不等式的方向的变化.

3．利用抽屉原则

由于抽世原则的结论本身就是组合不等式关系，所以我们利用抽屉原则，巧妙构造抽屉的方法证明组合不等式.

4．利用组合分析

在复杂的组合计数问题、离散极值问题等问题中，会出现一些组合不等式，这时可运用组合分析方法证明之.

赛题精讲

例1 证明：nknknnnnC0122!!2)!2(2

【分析】 把nnkknnnkknnkknnkknCCCC21221220202,而对于变形为，变换求和指标.

【证明】knjCCCCCnnkknnnkknnnnkknnkknnkkn2,,2212212221220202令对于和式，则.202022102212nnnkknnjnnjnnjjnnnkknCCCCCC

所以.2202202nnnkknnnkknCCC

即 nnnnkknCC220222，从而有

nknknnnnC0122!!2)!2(2.

例2 求证：.,)1(111)1(312111210NnCnmCnmCmCmCmnnmnnnnnn其中

证明 设nnnnnnnCnmCmCmCma11)1(312111210，则由基本恒等式rnrnrnrnrnCnrCCCC1111及得

.1)1()()1()(31)(211111122111112101110nnnnnnnnnnnnnnCnmCCnmCCmCCmCma

.)1(1)1)(2())(1(!,)1)(2(12111,)3())(1(!))(1()1(1.1,1112111nnmnnnnnnnnnnCnmmmnmnmnammmmaamnmnmnanmnmnnanmnaaanmaanmaa从而有而所以即故

【说明】注意到an中各项的系数均与n无关，且符号正负相同，由此想到an与an－1之间必定存在着某些联系，且是递推关系.

例3 求证：nkkknknknC01222.12)1(

【分析】考虑到恒等式12212kknkknkknCCC，仿例2解决.

【证明】令nkkknknknCa01222,2)1(

因为，12212kknkknkknCCC，

.2)1(2)1(2)1(,1.2)1(2)1()(2)1(22)1(211)1(2102)1(21)1(2102)1(21121221212202221212222112222nrrnnrrnrrrnnrrnrkknnkknkkknnkknknkkknknkkknnkkknknknnkkknknknnaCCCkrCCCCCa则令所以 5

令nknnnnkknknkaabbC01222,2)1(则 ①

.42)1(4)1()(2)1(2)1(2)1(21110)1(22)1(211121112222112222nnnjjjnjnjnnkknnkkknknknnknkknknknnbaCaCCCb又

于是由①式得1221112112,4,nnnnnnnnnnnaaaaaaaaaab即从而推知.

这说明{an}为等差数列，而a0=1,a1=2，故公差d=1，且an=n+1 .

【说明】此题运用变换求和指标的方法，找出了an，an－1，an－2之间的线性关系式，再由 初始条件求得an.这种利用递推关系求组合数的方法，在解决较复杂的计算或证明组事恒等式时经常用到.

例11：设},,,{},,,,{212211nnBBBDAAAD是集合M的两个划分，又对任何两个不变的子集),1(,njiBAji有,||nBAji求证：221||nM并说明等号能否成立？

【证明】令},1|,||,min{|njiBAkji，不妨设,||kAi因nBBB,,,21两两不交，故nBBB,,,21中至多有k个,jB使jBA1 .设

jBA1 .,,,2,1,knmj

由k的选取知),,2,1(||mjkBj从而.||1mkBmjj

又因 jBA1 .,,1,nmi

故 ,||||||11nBABAii

即 .||knBi

所以 ))((||||||||111knmnmkBBBMnmjjmjjnjj ).2()(knmknn

若,2nk因,km故

.2)2(2)2(2)2()()2()(||222nknnknkknnknmknnM

若,2nk则),,,2,1(2||ninAi 从而 .2||||||211nAAMniinii

下面说明2||2nM是可以取到的.显然这时n为偶数，取,4n则8||M，令

},8,7,6,5,4,3,2,1{M易验证M的两个划分.

D1={{1,2}{3,4}{5,6}{7,8}}, D2={{1,2}{3,5}{4,6}{7,8}},

满足题目条件.

例12：设n是正整数，我们说集合{1，2，„，2n}的一个排列（nxxx221,,）具有性质P，是指在{1，2，„，2n－1}当中至少有一个i，使得.||1nxxii求证，对于任何n，具有性质P的排列比不具有性质P的排列的个数多.

（1989，第30届IMO试题6）

【证明】设A为不具有性质P的排列的集合，B为具有性质P的排列的集合，显然)!.2(||||nBA为了证明||||BA，只要得到)!2(21||nB就够了.使作容斥原理.

设(nxxx221,,,)中,k与nk相邻的排列的集合为.,,2,1,nkAk则,)!12(2||nxAk,1,)!22(2||2njknxAAjk由容斥原理得

)!22(4)!12(2||||||211nCnnAAABnnjkjknkk

=)!22(2)!22()1(2)!2(nnnnnnn )!2(21)!22(2122nnnn

例13：平面上给定n个点，其中任何三点不共线，任意地用线段连接某些点（这些线段称为边），则确保图形中出现以给定点为顶点的)(nmm阶完全图的条件是图形中的边的条数

.1)1(222mnmmnCCCx 【证明】构造抽屉：每个抽屉里有m个相异点，共可得mnC个抽屉，又由于同一条边会在22mnC个抽屉里出现，根据抽屉原则知，当1)1(222mmnmnCCCx时，才能确保有一个抽屉里有2mC条边，而这2mC条边恰好与其中不共线的相异m点构成一个m阶完全图.

这就是说，确保图形中出现m阶完全图的条件是其中边的条数.1)1(222mnmmnCCCx

【评述】“完全图”，是图论中的基本概念.（此处从略）

例14：设nxxx,,,21为实数，满足,12232221nxxxx求证：对于每一整数2k，存在不全为零的整数,,,,21naaa使得),,,3,2,1(1||nikai并且

（1987年第28届IMO试题3）

.1)1(||2211nnnknkxaxaxa

【证】由柯西不等式得

).)(111(|)||||(|2232221222221nnxxxxxxx

即.||||||21nxxxn

所以，当10kai时，有

.)1(|)||||)(|1(||||||212211nkxxxkxaxaxannn

把区间[0，nk)1(]等分成1nk个小区间，每个小区间的长度1)1(2knk，由于每个ia能取k个整数，因此||||||2211nnxaxaxa