算两次在证明组合恒等式中的应用

“算两次”思想在证明组合恒等式中的应用

mnm1.Cn，取走和剩下的一一对应； Cn

n

2.C

k0kn2n

122nn我们可令等式(1x)n1CnxCnxCnx中的x等于1，得到该式。

另外，我们可考察集合{b1,,bn}的子集的个数：

一方面，采取加法原理，根据子集中元素个数分类：C

k0nkn；

另一方面，采取乘法原理，设其子集为S，我们逐一考察bi,i1,2,,n是否在S内，每个元素都有两种可能，考察完毕，子集S确定，或者我没把子集看成一个排列，如

n；b11,0,0,,0。共2。 0,0,,0

nn1

所以得证。

mmm1mm13.Cn，从{a,b1,,bn}取m个有Cn，一类不含a：1CnCn1种：一类含a：Cnm。 Cn

mmm1推广①： An 1AnmAn

mm1m从{a,b1,,bn}取m个排成一排An，一类不含a：An。 1：一类含a：mAn

n1nnnnn推广②：CnCCC

CCm1mnmn1mn2n1n

解释：有m+n+1不同小球，其中黑球m+1个，白球n个。从中选取n+1个小球，

n1选法共：Cnm1种，

n考虑另外一种算法：若有黑1则在剩余小球中选n个，即Cnm，若无黑1，则考虑是否有

n黑2，若有则从剩余n+m-1个小球中取n个，即Cnm1，依次考虑下去，到考虑是否有黑

nm，若有，则在剩余n个小球取n个，即Cn1，若无黑m。则必有黑m+1，最后剩下的m

个白球全取。总共CmnCmn1Cmn2Cn1Cn。所以得证。 nnnnn

rr1

本公式另一种表现形式：CrrCrr1Crr2Cn本公式也可从杨辉三角1Cn。

观察可得。还可考察等式(1x)(1x)

rr1

(1r)

n1

(1x)n(1x)x

两端

x

xr的系数相同。

推广③： C

rnm

krk

CmCnk0r

r

从{a1,am,b1,,bn}取r(rm)个元素Cn：从这n+m个元素中取k个a系，r-k个bm

r

系的方法CC

k

mrkn

种，k0,1,2,,r，所以C

rnm

krk

。（Vandermonde恒等式） CmCnk0

rrr1

特例，当m1时，即CnCC1nn。

n

当nmr时，

CnkC2nn

k0

2n!。

（人教B选修2-3教材P35T17，此题

n!n!

n

还可以通过考察等式(1x)n(1x)n(1x)2n左右两边含x项的系数相等得到；同样考察(1x)n(1x)m(1x)nm左右两边含x项的系数相等得到Vandermonde恒等式）

1222n2n1推广④：(Cn)2(Cn)n(Cn)nC2n1。

r

r

证明：由C

r

nm

krkkk1

，令rmn1结合kCnCmCnnCn1可得。 k0

nC

n1

2n1

knk1

nCn1Cn

k0

n1

knk1

nCn1Cnk0n1

k1nk1(k1)CnCnk0n1

n1

(k1)C

k0n

k1

n



kC

k0

kn



得证。

解释：a系{a1,a2,,an}选一个作为主元素，从剩余的2n-1中再选n-1个；再有对于k=1，

2,3„„，n从n个a系中选k个，再从中选一主元素，再从n个b系{b1,b2,,bn}中选n-k

knk

个（不做主元素），即kCn。 Cn

另一种证明方法：

00nn因为：(1x)nCnCnxCnx，(1

1n001n1)CnCnCn两展开式右

xxxn

1222n2

(Cn)2(Cn)n(Cn)，而

边乘积中的常数项恰好等于

(1x)n(1

1n1n

)n(1x)2n，(1x)2n中含xn的系数是C2

n。

xx

krk

，当nm时，即是上式。 kCmCn

k1m

推广：mC

r1

nm1

rr1

4.rCn（可直接用组合数公式证明） nCn1，

r

解释：从n个元素中选出r个元素并把其中之一作为主元素rCn，另一方法，先从n个r1元素中选出一个主元素，再从剩余的n-1个元素中选取r-1个元素nCn1。 123n用之可证明人教B版选修2-3P32T6：Cn2Cn3CnnCnn2n1。

0n1（证明一：倒序相加；证明二：从左往右结合2n1Cn1Cn1；证明三：122nn

x1） (1+x)n=C0nCnxCnxCnx两端求导并令123n

Cn2Cn3CnnCnn2n1的推广：

nmk0

mkmnmmnm时，Cn。 CmCnk2

解释：考虑从n人中选出m名正式代表及若干名列席代表的选法（列席代表不限人数，可以为0）.

m

一方面，先选定正式代表，有Cn种方法，然后从nm个人选列席代表，有2

nm

种方法，

共有2

nm

m

种。 Cn

另一方面，可以先选出mk人（k0,1,2,,nm），然后再从中选出m名正式代表，其余的k人为列席代表。对于每个k,这样的选法有Cn

mk

m

Cmk种，从而，总选法的种数为

nmk0

C

mknmCmk。从而得证。

rr1rmmrmrr1

另：rCn的推广：，m=1时即为nCnCCCCrCnC1nrnnmnn1。

构造组合模型巧证组合恒等式

数论中埃米特恒等式证明

证明会计恒等式1[推荐]

项目的组合管理在企业IT中的应用

导数在不等式证明中的应用

导数在证明不等式中的应用

导数在不等式证明中的应用

EXCEL在投资组合理论教学中的应用（材料）

钢铝组合结构在幕墙设计中的应用

组合支护形式在地铁车站围护中的应用.

《算两次在证明组合恒等式中的应用.doc》

将本文的Word文档下载到电脑，方便编辑。

推荐度：

点击下载文档