高中数学奥赛辅导第八讲组合计数

1、数学奥赛辅导 第八讲 组合计数知识、方法、技能组合计数就是计算集合的元素个数。它是组合数学的重要组成部分.在具体问题中给出的集合各式各样，都具有实际意义，而且集体中的元素是由某些条件所确定的，要判定一个元素是否属于某集合A，已非易事，要确定A的元素个数就更难了.这正是研究计算问题的原因。解决组合计算问题虽然不需要高深理论知识，却需要重要的计算原理与思想方法.几种特殊的排列、组合1圆排列定义1：从几个元素中任取r个不同元素仅按元素之间的相对位置而不分首尾排成一个圆圈，这种排列称为n个不同元素的r圆排列。r圆排列数记为.定理1：证：对n个不同元素取r个的任一圆排列，均有r种不同的方式展开成r个不同

2、的直线排列，且不同的圆排列展开的直线排列也彼此不同，故有r·=Prn，得正.2重复排列定义2：从n个不同元素中允许重复的任取r个元素排成一列，称为n个不同元素的r可重复排列.定理2：n个不同元素的r可重排列数为nr.证：在按顺序选取的r个元素中，每个元素都有n种不同的选法，故由乘法原理有，其排列数为nr.3不全相异元素的全排列定义3：设n个元素可分为k组，每一组中的元素是相同的，不同组间的元素是不同的，其中第i组的元素个数为ni(i=1, 2, , k ), n1+n2+nk=n . 则这n个元素的全排列称为不全相异元素的全排列.定理3：n个元素的不全相异元素的全排列个数为证：先把每

3、组中的元素看做是不相同的，则n个不同元素的全排列数为n!，然后分别将每个组的元素还其本来面目看成是相同的，则在这n!个全排列中，每个排列都重复出现了n1！n2!nk！次，所以不全相异元素的全排列数4多组组合定义4：将n个不同的元素分成k组的组合称为n个不同元素的k组合.定理4：对于一个n个不同元素的k组合，若第i组有ni个元素（i=1, 2, ，k），则不同的分组方法数为证：我们把分组的过程安排成相继的k个步骤.第一步，从n个不同元素中选n1个，有种方法；第二步，从nn1个元素中选n2个有种方法；第k步，从n（n1+n2+nk1）个元素中选nk个元素，有（n1+n2+nk1）种方法，再由乘法原

4、理得证.5重重组合定义5：从n个不同元素中任取r个允许元素重复出现的组合称为n个不同元素的r可重组合.定理5：n个不同元素的r可重组合的个数为Crn+r1 .证：设（a1 , a2 ,，ar）是取自1，2，n中的任一r可重复组合，并设a1a2ar .令 bi=ai+i1(1ir).从而b1=a1 , b2=a2+1 , b3=a3+2, br=a+r1r .显然下面两组数是一对一的：a1a2a3ar ,1a1<a2+1<a3+2<<ar+r1n+r1.设 A=（a1 , a2 ,，ar）|ai1，2，n，a1a2ar ， B=（b1, b2,，br）|bi1，2，n+r

5、1，b1< b2<<br.则由A、B之间存在一一对应，故|A|=|B|=Crn+r1 .枚举法所谓枚举法就是把集合A中的元素一一列举出来，从而计算出集体A的元素个数。它是最基本，也是最简单的计算数方法。应用枚举法计数的关键在于一一列举集合中的元素时必须做到既不重又不漏。映射法（略，见第一讲）分类计数原理与分步计数原理分类计算原理 完成一件事，有几种方式，第一种方式有m种方法，第二种方式有n种方法，最后一种方式有r种方法.不管采取哪一种方法都能完成这件事，则完成这件事的方法总数为m+n+r .分步计数原理 完成一件事，有几个步骤，第一步有m种方法，第二步有n种方法，最后一步有r

6、种方法，要完成这件事，必须通过每一步，则完成这件事的方法总数为m·nr.应用分类计数原理的关键在于分划，即把一个所要计数的集合S分划成一些两两不交的小集合，且使每个小集合都便于计数.应用分步计数原理的关键在于分解，即把一个所要计数的集合S分解成若干个集合的乘积.对一个集合S 的分划或分解，没有一般方法，应由具体问题而定，而这正是应用两个原理解题的难点与技巧所在.递推方法将与正整数有关的数字问题，通过寻求递推公式，或通过递推公式，而使问题得到解决的方法，叫做递推方法.递推方法几乎对所有数学分支都具有重要的作用，当然对组合计数就更不例外了，它是组合计数的常用方法.应用递推方法解题，会遇到

7、如下两类问题：一是如何找到满足题设条件的递推公式，二是推理计算.详见例题.母函数法母函数是一种非常有用的方法.这种方法的最早系统叙述见于Laplace在1812年出版的名著概率解析理论中.这种方法思想简单，把离散数列和幂级数一一对应起来，把离散数列间的相互结合关系对应成幂级数间的运算关系，最后由幂级数来确定离散数列的构造。简要地说，母函数方法是将一个有限或无限的数列ak=a0, a1, a2 , ak , 和如下形式的多项式f(x)= a0+a1x +a2 x2+ akxk + 联系起来，构成对应关系 akf(x)这个f(x)就称为ak的母函数或生产函数.意思是这个数列ak是由多项f(x)产生

8、的.例如：组合数列的母函数是.因为由二项式定理可得 = 是最常见的母函数.设an与bn是两个结定的数列，为了确定它们之间的某种关系，可分别写出二者所对应的母函数，再研究这两个母函数间的某种关系从而确定两个数列之间的关系，这便是母函数方法解题的基本思想.子集类一个n元素合X有2n个子集A1，A2，如果以它的部分子集作为元素，又可得到一个集合F=A1，A2，Ak（1k2n），这个集合F的称为原来集合X的一个子集类.应用子集类知识可以帮助我们解决如下二类问题：a什么时候可以把一个整数（集合）写成若干个满足一定条件的整数（子集）之和（并）.b在可以写的情况上有多少种写法.前者是存在性问题，后者组合计数

9、问题.数学归纳法塞题精讲例1 数1447，1005和1231有某些共同点，即每个数都是首位为1的四位数，且每个四位数中恰有两个数字相同，这样的四位数共有多少个？（第1届AIME试题，1983年）【解】符合条件的四位数必含有一个1或者两个1.（1）含有两个1的情形从除1之外的其余9个数字中任取两个，有C29种取法，再与其中的一个1组成任意排列的三位数，有P33种，这样构成的首位为1的四位数共有N1= C29 P33（个）.（2）只含有一个1的情形从其余的9个数字中任取两个，有C29 种取法，其中一个数字被重复选出，有C12种，这样的三个数字组成的三位数共有，这样构成的首位为1的四位数共有（个）.

10、因此，符合题意的四位数共有N=N1+N2=432（个）.例2 在xy平面上，顶点的坐标（x ,y）满足1x4，1y4，且x ,y是整数的三角形有多少个？（第44届AHSME试题，1993年）【解】由题设知，在xy平面上有16个整点，共有C316=560个三点组，要从中减去那些三点共线的.平面上有4条垂直线和4条水平线，每条上有4个点，这8条线上含有8C43=32个三点共线的三点组（如图I331）.类似的，在斜率为±1的线上三点共线的三点组有2C43+4C33=8+4=12（个）（如图I332）.此外，没有其他的三点共线的三点组，所以，组成的三角形的个数是5603212=516（个）.

11、例3 方程2x1+x2+x3+x10=3有多少个非负整数解.【解】设（x1, x2,x10）是原方程组的一个非负整数解，由于xi0（i=1, 2, 10），因此，2x12x1+x2+x3+x4+x5+x6+x7+x8+x9+x10=3即2x13，所以x1=0，1.下面分两种情形：（1）x1=0，则x2+x3+x10=3, 所以xi=0 , 1, 2 , 3 （i=2, 3 , ，10）.如果有某个xi=3，则其他xi=0，这样解有C19=9（个）.如果某个xi3，若某个xi=2，则必有一个xj=1，ij，2i, j9，这样解有C19·C18=72（个）.如果对每个xi2，3，则x2,

12、 x3，x10中必有三个xi（2i10）为1，这样解有C93=84（个）.（2）x1=1，则x2+x3+x10=1, 因此x1，x2，x3x10中仅有一个是1，这样解有C19=9（个）.于是原方程组有个非负整数解.例4 设S=1，2，n，A为至少含有两项的、公并非为正的等差数列，其项部都在S中，且添加S 的其他元素等于A后均不能构成与A有相同公差的等差数列，求这种A的个数（这里只有两项的数列也看做等差数列）.（全国高中数学联赛，1991年）【解】构造具有如下要求的集合A：把A中的元素按从小到大的次序排好后，在其最大元素后面添上S的任何元素均不能构成具有原公差的等差数列。这时，当A的首项与公差一

13、旦确定，其整个集合A也即确定，不妨设A的首项为a，公差为d，则a=1, d=1, 2, , n1时的集A有n1个；a=2, d=1, 2, , n2时的集A有n2个；a= n1，d=1时的集A有1个.因此，所求A的总个数为1+2+（n1）=例5 在扔硬币时，如果用Z表示正面朝上，F表示反面朝上，那么扔硬币的序列就表示为用Z和F组成的串，我们可以统计在这种序列中正面紧跟着反面（ZF）的出现次数，正面紧跟着正面（ZZ）的出现次数，例如序列ZZFFZZZZFZZFFFF是15次扔币的结果，其中有5个ZZ，3个ZF，2个FZ，4个FF.问：有多少个15次扔硬币的序列，恰好有2个ZZ，3个ZF，4个FZ

14、，5个FF？（第4届AIME试题，1986年）【解】符合题意的序列具有如下两种可能形式：（1）F带头的：FFZZF；（2）Z带头的：ZZFFZZFF.由于题设要求的序列恰有3个ZF，则序列属于第（ii）类的，应具有如下形式ZZFFZZFFZZFF.其中只有2个FZ，达不到4个FZ，故不可能，所以符合题设的序列只能是第（i）种形式.由于序列恰有4个FZ，则在考虑序列中恰有两个ZZ的情况下可分为如下两类： ZZZ Z Z Z， ZZ ZZ Z Z.以及Z的不同位置，其中的空格之处应填F.设每个空格处填F的个数依次为x1 , x2 , x3 , x4，则 x1 + x2 + x3 + x4=9这相当

15、于求其正整数解的个数，显然有C38=56.另一方面，对于，ZZZ的位置有4种，对，ZZ，ZZ，Z，Z的排列方法有6种，所以Z的排列方法有10种.所以，符合题意的序列有10×56=560（个）.例6 ABC的顶点为A=（0，0），B=（0，420），C=（560，0），一个骰子的六个面分别标上两个“A”，两个“B”，两个“C”.从ABC内部选出一点P1=（k , m），重复扔骰子，依下列法则选出点P2，P3，：如骰子露出标记L的那面LA，B，C，且刚刚选为Pn，那么Pn+1选为的中点，已知P7=（14，92），问k+m=?（第11届AIME试题，1993年）【解】首先应注意到因P1在A

16、BC内，则以后的所有Pk在ABC内.下面，我们将证明一旦任何后继的Pk给出，则可惟一地确定P1.假定PK=(xk , yk)，因Pk在ABC内，则有0<xk<560 , 0<yk<420,0<420xk+560 yk<420·560.若掷出A，则于是Pk+1所在的可能范围被限制在原三角形的之内（图I333中的一部分），显然Pk+1在I内，从而有420xk+1+560yk+1<×420×560.同样掷出B，则Pk+1在II内，yk+1>210.若掷出C，则Pk+1在内，xk+1>280.所以，对k2，Pk必在I，

17、II，III之一内，且由它的前一点惟一确定.例如，若Pk（xk , yk），位于II内，则Pk必为BPk1的中点，这时Pk1=2PkB=(2 xk , 2yk420).所以，若k2，Pk=（xk , yk），有下面，我们可以由P7推出P1：P7=（14，92）P6=（28，184）P5=（56，368）P4=（112，316）P3=（224，212）P2=（448，4）P1=（336，8）.k+m=336+8=344.例7 已知定义在非负整数集上的函数f(n)由下列条件确定：f(0)=0, f(1)=0, f(2n)=2f(n)+1(n>0)及f(2n+1)=f(2n)1,求最小正整数m

18、，使f(m)=21990+1.【说明】本题的函数由递推关系给出，由递推关系求出函数表达式往往不是一件容易的事，通常情况下，求自变量为某一值时的函数值，只要按递推关系式计算而不必求出函数关系，可现在的问题是已知函数值，要求自变量的最小正整数值，问题就显得难了，复杂了，在此我们可直接借助于递推关系而避开求函数表达式的麻烦.【解】因为 f(2n)=2f(n)+1, f(2n+1)=f(2n)1=(2f(n)+1)1=2f(n)所以偶数的函数值为奇数，奇数的函数值为偶数.因为21990+1是奇数，而f(m)=21990+1，所以m为偶数，可设m=2n1，则 f(m)=f(2n1)=2f(n1)+1=2

19、1990+1，得f(n1)=21989,从而可知n1是奇数，可设n1=2n2+1,则f(n1)=2f(n2)=21989, f(n2)= 21989,从而可知n2是奇数，可设n2=2n3+1,，可得关系式 m=2n1, f(n1)= 21989, n1=2n2+1, f(n2)= 21989, nk=2nk+1, f(nk+1)= 219894, n1988=2n1998+1,f(n1989)=2. 因为f(0)=1, f(1)=0,f(2n)=2f(n)+1, f(2n+1)=f(2n)1, n>0.所以当n=1时， f(2×1)=2f(1)+1=1, f(2×1+

20、1)=f(2×1)1=11=0. 当n=2时， f(2×2)=2f(2)+1=2×1+1=3, f(2×2+1)=f(5)=f(4)1=31=2.因为满足f(n1989)=2的最小正整数是 n1989=2×2+1=5 3·21，递推而上可知 n1988=2 n1989+1=2×5+1=11 3·221， n1987=2 n1988+1=2×11+1=23 3·221即满足f(n1988)=22的最小正整数是 n1988=3×221， 满足f(nk+1)=21989k的最小正整数是 nk

21、=3·21989k1 满足f(n1)=21989的最小正整数是 n1=3·219891.所以，满足f(m)=21990+1的最小正整数是 m=2n1=3·219902.例8 从1，2，n中选出k项的严格递增数列，每相邻两项的差m, m（k1）<n，有多少种不同的选法？【解】设第一个数为 x1+1，第二个数为 （x1+1）+（x2+1）， 第i个数为 （x1+1）+（xi+1）, 第k个数为 （x1+1）+（xk+1）其中 0xim1(2ik) 设 x2+x3+xk=r 则 （x1+1）+（xk+1）n，得 0x1nkr,所以x1可取nkr+1个值.把（1+x

22、+xn1）k1展开，则xr的系数ar就是方程的，满足条件的整数解(x2 , x3 ,，xk)的个数，即（1+x+xm1）k1= 所求的选法共有ar(nkr+1)种.因为ar (nkr+1)=(nk+1) ar rar 所以只要求出ar 与rar 即可.在中令x=1可得 ar=mk1 在中令x=1+y，则的右边成为 ar（1+y）r =ar（1+ry+ay2+）， 由rar 就是上式中y的系数. 别外，的左边成为 比较、可得 由、可得本题答案 例9 设n>1，两个自然数的集合 a1 , a2 , , anb1, b2 , , bn,而集ai+aj|1ijn=bi+bj|1ijn 这里的相等

23、计数及元素的重数，即如果元素S在的左边出k次（用k种方法表示成ai+aj的形式），那么S也在的右边出现k次，证明存在自然数h，使n=2h.【解】考虑母函数（注意，这里的ai与bi不是母函数的系数，而是指数） 同样、中系数表示和出现的次数，由题设知即由于f(1)g(1)=nn=0,所以(x1)|(f(x) g(x),从而存在自然数h1,使 因此即令.由于n>1，所以h1>1,h11为某一自然数，从而有n=2h.例10 设A1，A2，A3是集合1，2，n的具有如下性质的分划：（1）若将每个子集的元素按递增顺序排列，则每两个相邻元素的奇偶性不同；（2）A1，A2和A3中恰有一个最小元素是

24、偶数.试求这种分划的个数.提示 集合的分划是由一族集合A1，A2，A3确定的，它们满足：A1A2A3=1，2，n，A1A2= A2A3= A3A1=.集合的另一排列，如A2，A3，A1和A1，A2，A3是同一划分.（第28届IMO预选题，1987年）【解】显然，题目中的条件（1）和（2）等价于对每个分划集决定可能放入该集的下一个数的奇偶性，而且，如果是还没有放进元素的，则由（2）可知放进它的第一个数必是与A中的最小数有不相同的奇偶性；而对非空子集，下一个数的奇偶性由（1）决定.不失一般性.假设1A1，而A2的最小元素小于A3的最小元素，于是2有两种放法：或放入A1，或放入A2.更进一步地，一旦

25、k1被放入A2后，则k就有两种可能的放法：或放入A2，或放入A3.假设在某一步，k1可放入Ai1或A i2，不仿放入Ai3（i1, i2 , i3 是集合1，2，3的一种排列）.因为k1与k有不同的奇偶性，所以Ai3成为可放入的，而A i2却不能放入，而且k放入Ai1也是可能的。如此继续下一步及有两种可能放法.以上给出了归纳推理的步骤.综上，除1以处，每个数k均有两种放法。所以分划的个数为2n1.例11 试确定具有下述性质的最小正整数A：把从1001至2000的所有正整数任作一个排列，都可以其中找出连续的10项，使这10项之和大于或等于A.（中国台北第1届数学奥林匹克试题）【解】设b1, b2

26、 , b1000是1001, 1002,  , 2000的任一个排列. 则 下面，把1001至2000这1000个自然数排成10行，每行100个数，奇数列从左到右，偶数行从右到左排可得下表：1001 1002 1003 1099 11001200 1199 1198 1102 11011201 1202 1203 1299 1300 1801 1802 1803 1899 19002000 1999 1998 1902 1901从左到右按列的顺序，每一列又从上到下记上述数为a1, a2，a1000。令Si=ai +ai+1+ai+9,（i=1, 2, ，991），则S1=15005，

27、S2=15006,而且容易证明，当i为奇数时, Si=15005，当i为偶数时，Si=15006.所以可得A=15005.例12 （如图I334）将边长为正整数m、n的矩形划分成若干个边长均为正整数的正方形，每个正方形的边长平行于矩形的相应边.试求这些正方形边长之和的最小值.（2001年全国高中联赛二试试题3）【解法1】记所求最小值为f(m,n)可以证明f(m,n)=m+n(m,n).其中（m, n）表示m和n的最大公约数.事实上，不妨设mn.（1）关于m归纳，可以证明存在一种合乎题意的分法，使所得正方形边长之和恰为 m+n(m,n)当m=1时命题显然成立.假设当mk时，结论成立（k1）.当m

28、=k+1时，若n=k+1，则命题成立，若n<k+1，从矩形ABCD中切去正方形AA1D1D（如图I335），由归纳假设矩形A1BCD1有一种方法使得所得正方形边长之和恰为mn+n(mn,n)=m(m,n ).于是原正方形ABCD有一种分法使得所得正方形边长之和为m+n(m , n ).（2）关于m归纳可以证明（*）成立.当m=1时，由于n=1，显然f(m,n)=1=m+n(m , n).假设当mk时，对任意1nm有f(m,n)= m+n(m , n).若m=k+1，当n=k+1时显然f(m,n)=k+1= m+n(m , n).当1nk时，设矩形ABCD按要求分成了P个正方形，其边长分别

29、为a1, a2 , , ap .不妨设a1a2 ap .显然a1=n , 或a1<n .若a1<n ，则在AD与BC之间的与CD平行的任一直线至少穿过二个分成的正方形（或其边界），于是a1+a2+ap不小于AB与CD之和.所以a1+a2+ap2m>m+n(m , n).若a1=n ，则一个边长分别为mn和n的矩形可按题目要求分成边长分别为a2,ap的正方形，归纳假设a2+apmn+n(m n , n )= m(m , n)从而a1+a2+apm+n(m , n)，于是当m=k+1时，f(m, n ) m+n(m , n).再由（1）可知f(m, n ) = m+n(m , n) .【解法2】所求正方形边长之和的最小值为m+nd，的最大公约数，即d