高中数学奥赛辅导 第九讲 组合恒等式、组合不等式

数学奥赛辅导 第九讲 组合恒等式、组合不等式

知识、方法、技能

Ⅰ．组合恒等式

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

rn r

Cn Cn

②

r 1r 1rCn Cn 1 Cn

③ Cr nCr 1nn 1⑤

rrmmr m

④ CnCn Cn Cn m

012n

Cn Cn Cn Cn 2n

⑥ C0 C1 C2 C3 ( 1)nCn 0nnnnn组合恒等式的证明方法有： ①恒等变形，变换求和指标； ②建立递推关系； ③数学归纳法； ④考虑组合意义； ⑤母函数. Ⅱ．组合不等式

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

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

1

1; |AI|

Ci 1n

m

（2）

C

i 1

m

|AI|n

m2

|A|

其中|Ai|表示Ai所含元素的个数，CnI表示n个不同元素取|Ai|的组合数. 再如1998年第39届国际数学奥林匹克竞赛中第二大试题为：

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

对k个选手有完全相同的评分. 证明：

kb 1 . a2b

因此我们有必要研究组合不等式的证明方法.组合不等式的证明方法有： 1．在集合间建立单射，利用集合阶的不等关系

定理，设X和Y都是有限集，f为从X到Y的一个映射， （1）若f为单射，则|X|≤|Y|； （2）若f为满射，则|X|≥|Y|. 2．利用容斥原理

例如：设元素a属于集族{A1，A2， ，An}的k个不同集合Ai1,Ai2, ,Aik，则在

2

a被计算了k次，当k≥2时，集合Ai1,Ai2, ,Aik两两的交集共有Ck个.由于

|A|中

i

i 1

n

Ck2

k(k 1)

k 1,故a在 |Ai Aj|中至少少被计算了k－1次，这样我们得到下面的不21 i j n

等式：

| Ai| |Ai|

i 1

i 1

n

n

1 i j n

|A A

i

j

|

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

| Ai| |Ai|

i 1

i 1

n

n

1 i j n

|A A

i

j

| ( 1)

(n 1)

| Ai|删去右边第三个和式起的所有和式

i 1

n

得到.

采用这种办法，我们可以从容斥公式得到另外一些组合不等式，只是要注意这些不等式的方向的变化.

3．利用抽屉原则

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

4．利用组合分析

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

赛题精讲

例1 证明：

C2kn 22n 1

k 0n

k2n

2n

n

(2n)!

2 n!n!

k2n

k

C,而对于 C2n，变换求和指标.

k

2n

k n 1

k n 1

2n

2n

【分析】 把

C

k 0

k2n

变形为 C

k 0

2n

k2n

2n

【证明】

C

k 0

n

C

k 0

k n 1

C

n

k2n

2

2n

n

k n 1

C

2n

k2n

k

,对于和式 C2n,令j 2n k，则

k n 1

2n

k n 1n

C

2n

k

2n

C

j 0n

n 1

j2n

C C

j2nj 0

n2n

kn

C2n C2n. k 0

所以

C

k 0n

k

2n

2

2n

kn

C2 Cn2n. k 0

即 2

n

C

k 0

k

2nn

22n C2n，从而有

C2kn 22n 1

k 0

(2n)!

.

2 n!n!

m 2

m 3

11n

Cn ,其中n N. n

m n 1(m n 1)Cm n

例2 求证：1C0 1C1 1C2 ( 1)n

nnn

m 1

1111012nCn Cn Cn ( 1)nCn，则由基本恒等式m 1m 2m 3m n 1

rrrrr 1r 1

Cn Cn C及C Cn得 1n 1n

n

证明 设an

an

111( 1)n 1n 1( 1)n 1n 101021n 2

Cn (Cn C) (C C) (C C) Cn 1. 1n 1n 1n 1n 1n 2

m 1m 2m 3m nm n 1

m 1m 1

an,即an an an 1.nnnn(n 1)

所以an an 1 an 2

m n 1(m n 1)(m n)

n!

a1,

(m n 1)(m n) (m 3)111

而a1 ,

m 1m 2(m 2)(m 1)

n!1

从而有an .n

(m n 1)(m n) (m 2)(m 1)(m n 1)Cm n故an an 1

【说明】注意到an中各项的系数均与n无关，且符号正负相同，由此想到an与an－1之间

必定存在着某些联系，且是递推关系.

例3 求证：

( 1)

k 0

n

k

k

22n 2kC2n k 1 n 1.

kkk 1

【分析】考虑到恒等式C2n k 1 C2n k C2n k，仿例2解决.

n

【证明】令an

( 1)

k 0

k

k

22n 2k C2n k 1,

kkk 1

因为，C2n k 1 C2n k C2n k，

n

所以an 2

2

2n

k

( 1)k 22n 2kC2n k 1k 1n

2n

kk 1 ( 1)k 22n 2k(C2n k C2n k)k 1k

2n 2k

k

2n k

k 1

( 1)k 22n 2kC2n k.k 1n

( 1) 2

k 0

n

C

令r k 1,则

( 1)

k 1

n

k

2

2n 2k

C

k 1

2n k

r

( 1)r 1 22(n 1) 2rC2(n 1) r 1r 0

r ( 1)r22(n 1) 2rC2(n 1) r 1 an 1.

r 0n 1

n 1

令

( 1)

k 0

n

k

k

22n 2kC2n k bn,则bn an an 1 ①

又bn 2

2

2n

kn ( 1)k 22n 2kC2 ( 1)n kk 1

kk 1n ( 1)k 22n 2k(C2 C) ( 1)n k 12n k 1k 1n 1n 1

n 1

2n

4an 1 ( 1)j 22(n 1) 2jC2j(n 1) j

j 0

4an 1 bn 1.

于是由①式得bn 1 an 1 an 2,从而推知an an 1 4an 1 an 1 an 2,即an an 2 2an 1. 这说明{an}为等差数列，而a0=1,a1=2，故公差d=1，且an=n+1 .

【说明】此题运用变换求和指标的方法，找出了an，an－1，an－2之间的线性关系式，再由 初始条

件求得an.这种利用递推关系求组合数的方法，在解决较复杂的计算或证明组事恒等式时经常用到.

例11：设D1 {A1,A2, ,An},D2 {B1,B2, ,Bn}是集合M的两个划分，又对任何两个不变的子集Ai,Bj(1 i,j n)有|Ai Bj| n,求证：|M|

12

n并说明等号能否成立？ 2

【证明】令k min{|Ai|,|Bj|,1 i,j n}，不妨设|Ai| k,因B1,B2, ,Bn两两不交，故B1,B2, ,Bn中至多有k个Bj,使A1 Bj .设

A1 Bj ,j 1,2, ,m,n k.

由k的选取知|Bj| k(j 1,2, m),从而|又因 A1 Bj ,i m 1, ,n.

故 |A1| |Bi| |A1 Bi| n, 即 |Bi| n k. 所以 |M| |B| |B| |

j j

j 1

j 1

n

m

B

j 1

m

j

| mk.

j m 1

B

n

j

| mk (n m)(n k)

n(n k) m(n 2k).

若k

n

,因m k,故 2

n2nn22

|M| n(n k) m(n 2k) n(n k) k(n 2k) 2() 2( k) .

222

nnnnn2

若k ,则|Ai| (i 1,2, ,n), 从而 |M| | Ai| |Ai| .

222i 1i 1

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

2

2

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

D1={{1,2}{3,4}{5,6}{7,8}}, D2={{1,2}{3,5}{4,6}{7,8}}, 满足题目条件.

例12：设n是正整数，我们说集合{1，2， ，2n}的一个排列（x1,x2, x2n）具有性

质P，是指在{1，2， ，2n－1}当中至少有一个i，使得|xi xi 1| n.求证，对于任何n，具有性质P的排列比不具有性质P的排列的个数多.

（1989，第30届IMO试题6）

【证明】设A为不具有性质P的排列的集合，B为具有性质P的排列的集合，显然

|A| |B| (2n)!.为了证明|A| |B|，只要得到|B|

1

(2n)!就够了.使作容斥原理. 2

设(x1,x2, ,x2n)中,k与k n相邻的排列的集合为Ak,k 1,2, ,n.则