文档介绍：构造组合模型巧证组合恒等式
//--> 证明组合恒等式,一般是利用组合数的性质、数学归纳法、二项式定理等,,很多组合恒等式,,把等式两边看成同一组问题的两种计算方法,由解的唯一性,即可证明组合恒等式.
m--1m-1.
分析::把满足条件的组合分为两类,一类为不取某个元素a1,有Cnm-1种取法.-1m-.
m·Cpn=-pm-p.
分析:原式左端可看成一个班有m个人,从中选出n个人打扫卫生,在选出的n个人中,p人打扫教室,余下的n-,在余下的m-p人中再选出n-,两种算法计算的是同一个问题,结果当然是一致的.
以上两例虽然简单,但它揭示了用组合数的意义证明组合恒等式的一般思路:先由恒等式中意义比较明显的一边构造一个组合问题的模型,(组合数)相加的形式,可以把构造的组合问题进行适当分类,如例1,若是几个数(组合数)相乘的形式,则应进行适当的分步计算,如例2,当然,很多情况下是两者结合使用的.
例3证明Ckm+n=C0mCkn+C1mCk-1n+C2mCk-2n+…+CkmC0n,其中当p>q时Cpq=0.
证明:原式左边为m++n个元素分成两组,第一组为m个元素,剩下的n个元素为第二组,把取出的k个元素,按在第一组取出的元素个数i(i=0,1,2,…,k)进行分类,这一类的取法数为CimCk-,在m+n个元素中取k个元素的取法数又可写成ki=0CimCk-.
例4证明
n+n+2+…+Cnn++1n+m+1.
证明:原式右边为m+n+1个元素中取n+1个,元素的组合数,不失一般性,可以认为是在1,2,3,…,m+n,m+n+1,共m+n+1个数中取n++1个数a1,a2
…,an+1由小到大排列,即设a1<a2<an+1,按取出的最大数an+1=k+1分类,显然k=n,n+1,…,n+=n+i时(i=0,1,2,…,m),n+i,以取法总数又等于mi=0Cnn+.//-->
对于某些组合恒等式,有时其左右两边表示的意义都不易看出,但是如果根据组合数的特点仔细分析,或对原式进行一些适当的变形,往往可以巧妙地构造一个组合问题做为模型,证明就可化难为易.
例5证明C1n+2C2n+3C3n+…+nCnn=n2n-1.
分析:注意,原式左端等价于C11C1n+C12C2n+…+n,这里C1iCin可表示先在n个元素里选i个,再在这i个元素里选一个的组合数,可设一个班有n个同学,选出若干人(至少1人)组成一个代表团,(i=1,2,…,n),,先选团长,有n种选法,再决定剩下的n-1人是否参加,每人都有两种可能,以团员的选法有2n--.
这里应注意2n的意义,并能用