组合计数问题 上师大附中 余建国
知识拓展：
1、计数问题：常用的方法为：枚举法、利用两个基本原理、算两次方法、利用容斥原理。 我们着重了解（1）不尽相异元素的排列问题；（2）圆排列问题。 （1）不尽相异元素的全排列：
关于一类不尽相异元素的排列问题的表述是这样的：设有n个对象,其中只有m种类型(m?n),同种类型的对象之间没有区别,不同种类型的对象之间可以辨别.已知第一种类型的对象有k1个, 第二种类型的对象有k2个,···, 第m种类型的对象有km个, k1?k2????km?n.要将它们排成一列,可以有
n!种不同排列方式.
k1!?k2!???km!（2）圆排列：
（a）由A?{a1,a2,a3,?,an}的n个元素中，每次取出r个元素排在一个圆环上，叫做一个圆排列（或叫环状排列）．
（b）圆排列有三个特点：（i）无头无尾；（ii）按照同一方向转换后仍是同一排列；（iii）两个圆排列只有在元素不同或者元素虽然相同，但元素之间的顺序不同，才是不同的圆排列．
（c）定理：在A?{a1,a2,a3,?,an}的n个元素中，每次取出r个不同的元素进行圆排列，圆排列数为
Pnrr．
2、组合恒等式：常用方法为：母函数方法、组合模型法。 （1）母函数定义：定义对于任意的实数系列，?a0a1a2?an??，构造一形式幂级函数
f?x???ak?0k?kxk，则称f(x)是数列?a0a1a2?an??的母函数，又称生成函数或发生函数。
（2）六个基本的组合恒等是： a) Cn?Cnkn?k
k?1b) Cn?Cn?1?Cn?1 c) kCn?nCn?1 d) CnCk?CnCn?m e) Cn?Cn?????Cn?2
01nnkmmk?mkk?1kf) Cn?Cn?Cn?????(?1)Cn?0
在证明组合恒等式时，有时构造一个组合问题的模型，在等式两边看成一个组合问题的两种计算方法，由组合个数相等证出要证明的组合等式，这种证明方法构思精巧，把枯燥地的公式还原为有趣的实例，能激发学习兴趣。 例题精选
例1．10层楼梯分8步走,每步只能走1层或2层,共有多少种不同走法?
解：问题一定是6步走1层,2步走两层.我们可以看成第一种类型为1步,共有6个对象；第二种类型为2步,共有2个对象，则有
012nn8!6!2!?28种不同的走法.
例2.（2011“卓越联盟”自主招生考题）数列{an}共有11项，a1?0,a11?4，且
ak?1?ak?1,k?1,2,???,10.满足这种条件的不同数列的个数为（ ）.
A.100 B.120 C.140 D.160 解
：
依
题
意
，
ak?1?ak?1或
ak?1?ak??1，依题意知：
a11?a1?(a11?a10)?(a10?a9)?????(a2?a1)，我们首先关心这10个“差值”中有多少个1和?1：
设有x个1，则有10?x个?1，由题意：4?x?(10?x)?x?7.
上述问题显然是一个不尽相异元素的排列问题，第一种类型为含1的元素特征，共有7个对象；第二种类型为含?1的元素特征，共有3个对象.故共有
10!7!?3!?120种不同的数列个数.
例3．有6名先生和6名女士围坐一个圆桌就餐，要求男女交替就坐，则有多少种不同的排坐方式？ 解：6男全排列6!；6女全排列6！；6女插入6男的前6个空或者后6个空，即女打头或男打头6!?6!?2；再除以围圈重复得
6!?6!?212?6!?5!
或：男6的圆排列为5！，对每个男的排列，女要在他们之间的6个位置，进行线性排列6！（而不是5！）。 （圆排列可以通过线性排列来解决） 例4．求证： CnCk?CnCn?m
证明：等式左边可看作一个班有n个同学，从中选出k个同学组成兴趣小组，在选出的k个同学中，m个同学参加数学兴趣小组，余下的k-m个参加物理兴趣小组的选法数；等式右边可看成直接从n个同学中选出m个同学参加数学兴趣小组，在余下的n-m个同学中选出k-m个同学参加物理兴趣小组的选法数，显然这两种选法是一致的，故左边=右边，等式成立。
思考：请用上述利用组合数学的模型来证明要证明的组合恒等式证明思路解释：
1．Cn?Cn1kn?kkmmk?m 2．Cn?Cn?1?Cn?1
2232nn?2kkk?1例5．求证：Cn?2Cn?3Cn???nCn?n?(n?1)22
证明一：?kC?n?kC2knk?1k?1nnk?1n?1?n?(k?1)Ck?1nn?1n?1?n?Ck?1k?1nk?1n?1k?1n?1 （1） )?n?(k?1)Cn?1?n2k?1n对右边的和式再用一次基本恒等式（c）：(k?1)Cn?1?(n?1)Cn?2 则：?(k?1)Ck?2nk?1n?1k?2n?2 ?(n?1)?Cn?2?(n?1)2k?1nk?2代入（1）式：?kCn?n(n?1)22kk?12inn?2?n2n?1?n(n?1)2n?2
1i证明二（构造模型法）：由iCn?CiCiCn可表示n个元素里选i个，再从i个元素里先两个（可重复）的组合数，所以等式左边可看成例2中指定1个为组长的基础上，再指定一个人为副组长（可兼职）
的组合数。
对原式右边我们可以看成分组长和副组长是否相同两种情报况，若组长和副组长是同一人，则有
1n?2n?1种选取法；若不是一个人，则有n?(n?1)2n?2种选法。故n?2n?1+n?(n?1)2n?2?n?(n?1)2n?2
显然两种选法是一致的，故左边=右边，等式成立。 例6．（2006年复旦）证明：?(Cn)?C2n
k2nk?0nn证明一（母函数法）：由二项式定理：(1?x)?n?Ck?0knxk
得：
01nn01(1?x)2n?(Cn?Cnx?????Cnx)(Cn?Cnx?????Cnnxn)?????(CC?CC2n0nnn1nn?1n?????CC)x????0nnn1nn?1nnn0nnn0nn
即(1?x)的展开式中x的系数为CC?CCn?????CC)??CCknk?0nn?knk2??(Cn) k?0n又(1?x)2nnkknC，即的系数为x??C2x2n n2nk?0由此得：?(Cn)?C2n
k2nk?0n注意：本题的基本思维使用比较系数法。实际上对问题从不同的角度思维两次（算两次）。
证明二（构造模型法）：可以这样理解：某班共有2n名学生，现从中选出n个学生参加某项活动，显然共有C2n中选择；另一反面，将这2n个学生分成A,B两组每组n个学生，
第1类：A组中取0个元素取，B组中取n个元素，共有Cn?Cn?(Cn) 第2类：A组中取1个元素，B组中取n-1个元素，共有Cn?Cn1n?112?(Cn)
n0n02第3类：A组中取2个元素，B组中取n-2个元素，共有C2n?2n?Cn?(C22n)
??
第n+1类：A组中取n个元素，B组中取0个元素，共有Cn0n2n?Cn?(Cn) n由分类计数原理得：?(Ck2nn)?C2n
k?0注：本题的一般情形： 求证： C0m1m?1rCn?CrCn?C2rCm?2n???Cm0mrCn?Cn?r(n,m?N?,r?m,n?m)
例7、在由若干个南方球队和北方球队参加的排球单循环赛中，已知南方球队比北方球队多9支方球队总得分是北方球队的9倍，求证 冠军是一支南方球队（胜得1分 败得0分） 解：设北方球队共有x支，则南方球队有x+9支 所有球队总得分为C2x?9)(2x?8)2x?9?(22?(2x?9)(x?4) 南方球队总得分为9(2x?9)(2x?8)?9(x?9)(x?4)10210 北方球队总得分为(2x?9)(x?4)10 南方球队内部比赛总得分C2x?9 北方球队内部比赛总得分C2x (2x?9)(x?4)x?1)10?x(2?0 解得：11?22911?163?x?11?2293?3?9 因为(2x?9)(x?4)10为整数 x=6或x=8 当x=6时 南 2所有球队总得分为C2x?9?(2x?9)(2x?8)2??(2x?9)(x?4)=210 南方球队总得分为9(2x?9)(2x?8)1029(x?9)(x?4)10=189 北方球队总得分为(2x?9)(x?4)102=21 南方球队内部比赛总得分Cx?9=105 北方球队内部比赛总得分Cx=15 北方胜南方得分=21-15=6 北方球队最高得分=5+6=11 因为11×15=165<189 所以南方球队中至少有一支得分超过11分． 冠军在南方球队中 当x=8时 2所有球队总得分为C2x?9?2(2x?9)(2x?8)2??(2x?9)(x?4)=300 南方球队总得分为9(2x?9)(2x?8)1029(x?9)(x?4)10=270 北方球队总得分为(2x?9)(x?4)102=30 南方球队内部比赛总得分Cx?9=136 北方球队内部比赛总得分Cx=28 北方胜南方得分=30-28=2 北方球队最高得分=7+2=9 2