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

导语：构造组合模型巧证组合恒等式一文来源于网友上传，不代表本站观点，若需要原创文章可咨询客服老师，欢迎参考。

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

例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．原式成立．

对于某些组合恒等式，有时其左右两边所表示的意义都不易看出，但是如果根据组合数的特点仔细分析，或对原式进行一些适当的变形，往往可以巧妙地构造一个组合问题做为模型，证明就可化难为易．

例5证明C1n＋2C2n＋3C3n＋…＋nCnn＝n2n－1．

分析：注意，原式左端等价于C11C1n＋C12C2n＋…＋C1nCnn，这里C1iCin可表示先在n个元素里选i个，再在这i个元素里选一个的组合数，可设一个班有n个同学，选出若干人（至少1人）组成一个代表团，并指定一人为团长．把这种选法按取到的人数i分类（i＝1，2，…，n），则选法总数即为原式左端．今换一种选法，先选团长，有n种选法，再决定剩下的n－1人是否参加，每人都有两种可能，所以团员的选法有2n－1种．即选法总数为n2n－1种．显然两种选法是一致的．

这里应注意2n的意义，并能用组合意义证明ni＝0Cin＝2n．

例6证明

C1n＋22C2n＋32C3n＋…＋n2Cnn＝n（n＋1）2n－2．

分析：本题左边与例5左边类似，不同的是例5左边为ni＝1iCin，而本题为ni＝1i2Cin．只要在例5构造的模型中加上同时还要选一个干事，并且干事和团长可以是同一个人，即可符合原式左边．对原式右边我们可分为团长和干事是否是同一个人两类情况．若团长和干事是同一个人，则有n2n－1种选法；若团长和干事不是同一个人，则有n（n－1）2n－1种选法．所以，共有n2n－1＋n（n－1）2n－2＝n（n＋1）2n－2种选法．

例7证明

（C1n）2＋2（C2n）2＋3（C3n）2＋…＋n（Cnn）2＝nCn－12n－1．

分析：注意到（Cin）2＝CinCn－in，可设一个班有n个男生与n个女生，在这2n个学生中选n个同学（至少有1名男生）组成一个代表团，并指定其中一名男生为团长，按选出的男生人数i（i＝1，2，…，n）分类，这一类有iCinCn－in＝i（Cin）2种选法，总的选法有ni＝1i（Cin）2种．原式右边的组合意义是明显的，即直接在n个男生中选一名团长，有n种选法，再从剩下的2n－1人中选出n－1人为团员，共有nCn－12n－1种选法．

掌握了用组合意义证明组合恒等式这种方法后，还可通过构造一个组合问题的模型，编拟组合恒等式习题．如在例5中除了要选一名团长外，还要选一名干事和一名联络员（可以兼职）便可得ni＝1i3Cin＝n2（n＋3）·2n－3．具体证法可参照例5与例6．又如，在例7中除了在2n个同学中选出n个团员及指定一名男生为团长外，还要有一名男生担任联络员（可以兼职），则可得组合恒等式：ni＝1i2（Cin）2＝nCn－12n－1＋n（n－1）Cn－22n－2．若在例7中要求，留下的女生中再选一名负责人，则有组合恒等式ni＝1i2（Cin）2＝n2Cn－12n－2．具体证明读者可自己完成．实际上习题的编拟过程就是用组合意义证明恒等式的过程．

若把恒等式中较简单的一边去掉，变为化简组合式，用此法同样能完成化简，读者可自己体会．

用组合数的意义证明组合恒等式，除了对提高学生的智力及观察分析问题的能力有帮助外，还有它独到的好处，那就是把抽象的组合数还原为实际问题，能提高学生应用数学知识解决实际问题的能力，把枯燥的公式还原为有趣的实例，能提高学生的学习兴趣．所以，老师在教学过程中适当介绍一些这方面的内容，将是大有益处的．