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

        证明组合恒等式，一般是利用组合数的性质、数学归纳法、二项式定理等，通过一些适当的计算或化简来完成。但是，很多组合恒等式，也可直接利用组合数的意义来证明。即构造一个组合问题的模型，把等式两边看成同一组问题的两种计算方法，由解的唯一性，即可证明组合恒等式。
        例１证明Cnm ＝ Cnm － 1m ＋ Cn － 1m －１。分析：原式左端为ｍ个元素中取ｎ个的组合数。原式右端可看成是同一问题的另一种算法：把满足条件的组合分为两类，一类为不取某个元素ａ１，有Ｃｎｍ－１种取法。一类为必取ａ１有Cn － 1m － 1 种取法。由加法原理可知原式成立。
        例２证明Cnm·Cpm ＝ Cpm·Cn － pm －ｐ。
        分析：原式左端可看成一个班有ｍ个人，从中选出ｎ个人打扫卫生，在选出的ｎ个人中，ｐ人打扫教室，余下的n － p 人打扫环境卫生的选法数。原式右端可看成直接在ｍ人中选出ｐ人打扫教室，在余下的m － p 人中再选出n － p 人打扫环境卫生。显然，两种算法计算的是同一个问题，结果当然是一致的。
        以上两例虽然简单，但它揭示了用组合数的意义证明组合恒等式的一般思路：先由恒等式中意义比较明显的一边构造一个组合问题的模型，再根据加法原理或乘法原理对另一边进行分析。若是几个数（组合数）相加的形式，可以把构造的组合问题进行适当分类，如例１，若是几个数（组合数）相乘的形式，则应进行适当的分步计算，如例２，当然，很多情况下是两者结合使用的。
        例３证明Ckm ＋ n ＝ C0mCkn ＋ C1mCK － 1n ＋ C2mck － 2n ＋…＋ CkmC0m，其中当p ＞ q 时Cpq ＝０。
        证明：原式左边为m ＋ n 个元素中选ｋ个元素的组合数。今将这m ＋ n 个元素分成两组，第一组为ｍ个元素，剩下的n 个元素为第二组，把取出的ｋ个元素，按在第一组取出的元素个数ｉ（i ＝ 0，1，2，…，k）进行分类，这一类的取法数为CimCk － in。于是，在ｍ＋ｎ个元素中取ｋ个元素的取法数又可写成ki ＝０CimCk －in。故原式成立。
        例４证明
        Cnn ＋ Cnn ＋ 1 ＋ Cnn ＋ 2 ＋…＋ Cnn ＋ m ＝ Cn ＋ 1n ＋ m ＋ 1。
        证明：原式右边为m ＋ n ＋ 1 个元素中取n ＋ 1 个，元素的组合数，不失一般性，可以认为是在１，２，３，…，m ＋ n，m ＋ n ＋ 1，共m ＋ n ＋ 1 个数中取n ＋ 1 个数。将取出的n ＋ 1个数al，a2…，an ＋１由小到大排列，即设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 ＝０Cnn ＋ i。原式成立。