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

数学奥赛辅导 第八讲

组合计数

知识、方法、技能

组合计数就是计算集合的元素个数。它是组合数学的重要组成部分.

在具体问题中给出的集合各式各样，都具有实际意义，而且集体中的元素是由某些条件所确定的，要判定一个元素是否属于某集合A，已非易事，要确定A的元素个数就更难了.这正是研究计算问题的原因。

解决组合计算问题虽然不需要高深理论知识，却需要重要的计算原理与思想方法. Ⅰ．几种特殊的排列、组合 1．圆排列

定义1：从几个元素中任取r个不同元素仅按元素之间的相对位置而不分首尾排成一个

r

圆圈，这种排列称为n个不同元素的r——圆排列。r——圆排列数记为Kn.

Pnr

. 定理1：K r

rn

证：对n个不同元素取r个的任一圆排列，均有r种不同的方式展开成r个不同的直线

r

排列，且不同的圆排列展开的直线排列也彼此不同，故有r·Kn=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个元素的不全相异元素的全排列个数为

n!.

.

n1!n2! nk!

证：先把每组中的元素看做是不相同的，则n个不同元素的全排列数为n!，然后分别将每个组的元素还其本来面目看成是相同的，则在这n!个全排列中，每个排列都重复出现了n1！

n2! nk！次，所以不全相异元素的全排列数

4．多组组合

n!.

.

n1!n2! nk!

定义4：将n个不同的元素分成k组的组合称为n个不同元素的k——组合.

定理4：对于一个n个不同元素的k——组合，若第i组有ni个元素（i=1, 2, ，k），则不同的分组方法数为

n!.

.

n1!n2! nk!

n

证：我们把分组的过程安排成相继的k个步骤.第一步，从n个不同元素中选n1个，有Cn1

2

种方法；第二步，从n－n1个元素中选n2个有Cn n1种方法； ；第k步，从n－（n1+n2+

n

+nk－1）个元素中选nk个元素，有Cnk－（n1+n2+ +nk－1）种方法，再由乘法原理得证.

5．重重组合

定义5：从n个不同元素中任取r个允许元素重复出现的组合称为n个不同元素的r——可重组合.

定理5：n个不同元素的r——可重组合的个数为Crn+r－1 .

证：设（a1 , a2 , ，ar）是取自{1，2， ，n}中的任一r可重复组合，并设a1≤a2≤ ≤ar .令 bi=ai+i－1(1≤i≤r).

从而b1=a1 , b2=a2+1 , b3=a3+2, , br=a+r－1r . 显然下面两组数是一对一的：a1≤a2≤a3≤ ≤ar , 1≤a1<a2+1<a3+2< <ar+r－1≤n+r－1.

设 A={（a1 , a2 , ，ar）|ai∈{1，2， ，n}，a1≤a2≤ ≤ar }， B={（b1, b2, ，br）|bi∈{1，2， ，n+r－1}，b1< b2< <br}. 则由A、B之间存在一一对应，故|A|=|B|=Crn+r－1 .

Ⅱ．枚举法

所谓枚举法就是把集合A中的元素一一列举出来，从而计算出集体A的元素个数。它是最基本，也是最简单的计算数方法。应用枚举法计数的关键在于一一列举集合中的元素时必须做到既不重又不漏。

Ⅲ．映射法（略，见第一讲） Ⅳ．分类计数原理与分步计数原理

分类计算原理 完成一件事，有几种方式，第一种方式有m种方法，第二种方式有n种方法， 最后一种方式有r种方法.不管采取哪一种方法都能完成这件事，则完成这件事的方法总数为m+n+ +r .

n

分步计数原理 完成一件事，有几个步骤，第一步有m种方法，第二步有n种方法， ，最后一步有r种方法，要完成这件事，必须通过每一步，则完成这件事的方法总数为m·n r.

应用分类计数原理的关键在于分划，即把一个所要计数的集合S分划成一些两两不交的小集合，且使每个小集合都便于计数.

应用分步计数原理的关键在于分解，即把一个所要计数的集合S分解成若干个集合的乘积.

对一个集合S 的分划或分解，没有一般方法，应由具体问题而定，而这正是应用两个原理解题的难点与技巧所在.

Ⅴ．递推方法

将与正整数有关的数字问题，通过寻求递推公式，或通过递推公式，而使问题得到解决的方法，叫做递推方法.

递推方法几乎对所有数学分支都具有重要的作用，当然对组合计数就更不例外了，它是组合计数的常用方法.

应用递推方法解题，会遇到如下两类问题：一是如何找到满足题设条件的递推公式，二是推理计算.详见例题.

Ⅵ．母函数法

母函数是一种非常有用的方法.这种方法的最早系统叙述见于Laplace在1812年出版的名著《概率解析理论》中.这种方法思想简单，把离散数列和幂级数一一对应起来，把离散数列间的相互结合关系对应成幂级数间的运算关系，最后由幂级数来确定离散数列的构造。

简要地说，母函数方法是将一个有限或无限的数列 {ak}={a0, a1, a2 , , ak , } 和如下形式的多项式

f(x)= a0+a1x +a2 x2+ + akxk + 联系起来，构成对应关系 {ak}←→f(x)

这个f(x)就称为{ak}的母函数或生产函数.意思是这个数列{ak}是由多项f(x)产生的. 例如：组合数列Cn,Cn, ,Cn的母函数是(1 x).因为由二项式定理可得

01nn (1 x)=Cn Cnx Cnx

nn

01nn

(1 x)是最常见的母函数.

设{an}与{bn}是两个结定的数列，为了确定它们之间的某种关系，可分别写出二者所对应的母函数，再研究这两个母函数间的某种关系从而确定两个数列之间的关系，这便是母函数方法解题的基本思想.

内容需要下载文档才能查看

Ⅶ．子集类

一个n元素合X有2n个子集A1，A2， A2n，如果以它的部分子集作为元素，又可得到一个集合F={A1，A2， ，Ak}（1≤k≤2n），这个集合F的称为原来集合X的一个子集类.

应用子集类知识可以帮助我们解决如下二类问题：

a．什么时候可以把一个整数（集合）写成若干个满足一定条件的整数（子集）之和（并）. b．在可以写的情况上有多少种写法.前者是存在性问题，后者组合计数问题. Ⅷ．数学归纳法

塞题精讲

例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种，

P33

这样的三个数字组成的三位数共有，这样构成的首位为1的四位数共有

2

1

C92 C2 P33

N2 （个）.

2

因此，符合题意的四位数共有N=N1+N2=432（个）.

例2 在xy平面上，顶点的坐标（x ,y）满足1≤x≤4，1≤y≤4，且x ,y是整数的三角形有多少个？

（第44届AHSME试题，1993年）

【解】由题设知，在xy平面上有16个整点，共有C316=560个三点组，要从中减去那些三点共线的.

平面上有4条垂直线和4条水平线，每条上有4个点，这8条线上含有8C43=32个三点共线的三点组（如图I—3—3—1）.

类似的，在斜率为±1的线上三点共线的三点组有2C43+4C33=8+4=12（个）（如图I—3—3—2）.

此外，没有其他的三点共线的三点组，所以，组成的三角形的个数是 560－32－12=516（个）.

例3 方程2x1+x2+x3+ +x10=3有多少个非负整数解.

【解】设（x1, x2, ,x10）是原方程组的一个非负整数解，由于xi≥0（i=1, 2, 10）， 因此，

2x1≤2x1+x2+x3+x4+x5+x6+x7+x8+x9+x10=3 即2x1≤3，所以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（个）.

如果某个xi≠3，若某个xi=2，则必有一个xj=1，i≠j，2≤i, j≤9，这样解有C19·C18=72（个）.

如果对每个xi≠2，3，则x2, x3， ，x10中必有三个x（为1，这样解有C93=84i2≤i≤10）（个）.

（2）x1=1，则x2+x3+ +x10=1, 因此x1，x2，x3 x10中仅有一个是1，这样解有C19=9（个）.

11131

于是原方程组有C9 C9 C8 C9 C9 174个非负整数解.

例4 设S={1，2， ，n}，A为至少含有两项的、公并非为正的等差数列，其项部都在S中，且添加S 的其他元素等于A后均不能构成与A有相同公差的等差数列，求这种A的个数（这里只有两项的数列也看做等差数列）.

（全国高中数学联赛，1991年）

【解】构造具有如下要求的集合A：把A中的元素按从小到大的次序排好后，在其最大元素后面添上S的任何元素均不能构成具有原公差的等差数列。这时，当A的首项与公差一旦确定，其整个集合A也即确定，不妨设A的首项为a，公差为d，则

a=1, d=1, 2, , n－1时的集A有n－1个； a=2, d=1, 2, , n－2时的集A有n－2个；

a= n－1，d=1时的集A有1个.

因此，所求A的总个数为1+2+ +（n－1）=

n(n 1)

. 2

例5 在扔硬币时，如果用Z表示正面朝上，F表示反面朝上，那么扔硬币的序列就表