推荐文档列表

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

时间:2021-10-02 14:37:08 数学论文 我要投稿

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

证明组合恒等式,一般是利用组合数的性质、数学归纳法、二项式定理等,通过一些适当的计算或化简来完成.但是,很多组合恒等式,也可直接利用组合数的意义来证明.即构造一个组合问题的模型,把等式两边看成同一组问题的两种计算方法,由解的唯一性,即可证明组合恒等式.

例1证明Cnm=Cnm-1+Cn-1m-1.

分析:原式左端为m个元素中取n个的组合数.原式右端可看成是同一问题的另一种算法:把满足条件的组合分为两类,一类为不取某个元素a1,有Cnm-1种取法.一类为必取a1有Cn-1m-1种取法.由加法原理可知原式成立.

例2证明Cnm·Cpn=Cpm·Cn-pm-p.

分析:原式左端可看成一个班有m个人,从中选出n个人打扫卫生,在选出的n个人中,p人打扫教室,余下的n-p人打扫环境卫生的选法数.原式右端可看成直接在m人中选出p人打扫教室,在余下的m-p人中再选出n-p人打扫环境卫生.显然,两种算法计算的是同一个问题,结果当然是一致的.

以上两例虽然简单,但它揭示了用组合数的意义证明组合恒等式的一般思路:先由恒等式中意义比较明显的一边构造一个组合问题的模型,再根据加法原理或乘法原理对另一边进行分析.若是几个数(组合数)相加的形式,可以把构造的组合问题进行适当分类,如例1,若是几个数(组合数)相乘的形式,则应进行适当的分步计算,如例2,当然,很多情况下是两者结合使用的.

例3证明Ckm+n=C0mCkn+C1mCk-1n+C2mCk-2n+…+CkmC0n,其中当p>q时Cpq=0.

证明:原式左边为m+n个元素中选k个元素的组合数.今将这m+n个元素分成两组,第一组为m个元素,剩下的n个元素为第二组,把取出的k个元素,按在第一组取出的元素个数i(i=0,1,2,…,k)进行分类,这一类的取法数为CimCk-in.于是,在m+n个元素中取k个元素的取法数又可写成?ki=0CimCk-in.故原式成立.

例4证明

Cnn+Cnn+1+Cnn+2+…+Cnn+m=Cn+1n+m+1.

证明:原式右边为m+n+1个元素中取n+1个,元素的组合数,不失一般性,可以认为是在1,2,3,…,m+n,m+n+1,共m+n+1个数中取n+1个数.将取出的n+1个数a1,a2…,an+1由小到大排列,即设a1<a2<an+1,按取出的最大数an+1=k+1分类,显然k=n,n+1,…,n+m.当k=n+i时(i=0,1,2,…,m),这一类取法数为Cnn+i,所以取法总数又等于?mi=0Cnn+i.原式成立.

对于某些组合恒等式,有时其左右两边所表示的意义都不易看出,但是如果根据组合数的特点仔细分析,或

[1] [2] [3]