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

《数学奥赛辅导_第八讲_组合计数》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、对n个不同元素取r个的任一圆排列，均有r种不同的方式展开成r个不同的直线排列，且不同的圆排列展开的直线排列也彼此不同，故有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

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

4、步骤.第一步，从n个不同元素中选n1个，有种方法；第二步，从n－n1个元素中选n2个有种方法；…；第k步，从n－（n1+n2+…+nk－1）个元素中选nk个元素，有－（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

5、+1,b3=a3+2,…,br=a+r－1r.显然下面两组数是一对一的：a1≤a2≤a3≤…≤ar,1≤a1

6、ai∈{1，2，…，n}，a1≤a2≤…≤ar}，B={（b1,b2,…，br）

7、bi∈{1，2，…，n+r－1}，b1

8、A

9、=

10、B

11、=Crn+r－1.Ⅱ．枚举法所谓枚举法就是把集合A中的元素一一列举出来，从而计算出集体A的元素个数。它是最基本，也是最简单的计算数方法。应用枚举法计数的关键在于一一列

12、举集合中的元素时必须做到既不重又不漏。Ⅲ．映射法（略，见第一讲）Ⅳ．分类计数原理与分步计数原理分类计算原理完成一件事，有几种方式，第一种方式有m种方法，第二种方式有n种方法，……最后一种方式有r种方法.不管采取哪一种方法都能完成这件事，则完成这件事的方法总数为m+n+…+r.分步计数原理完成一件事，有几个步骤，第一步有m种方法，第二步有n13种方法，…，最后一步有r种方法，要完成这件事，必须通过每一步，则完成这件事的方法总数为m·n……r.应用分类计数原理的关键在于分划，即把一个所要计数的集合S分划成一些两两不交的小集合，且使每个小集合都

13、便于计数.应用分步计数原理的关键在于分解，即把一个所要计数的集合S分解成若干个集合的乘积.对一个集合S的分划或分解，没有一般方法，应由具体问题而定，而这正是应用两个原理解题的难点与技巧所在.Ⅴ．递推方法将与正整数有关的数字问题，通过寻求递推公式，或通过递推公式，而使问题得到解决的方法，叫做递推方法.递推方法几乎对所有数学分支都具有重要的作用，当然对组合计数就更不例外了，它是组合计数的常用方法.应用递推方法解题，会遇到如下两类问题：一是如何找到满足题设条件的递推公式，二是推理计算.详见例题.Ⅵ．母函数法母函数是一种非常有用的方法.这种方法的

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