基本计数问题.ppt

第二章 基本计数问题 2.1 加法原则和乘法原则 2.2 排列 相异元素不允许重复的排列 圆周排列（循环排列） 相异元素允许重复的排列（重复数无限） 多重集的排列 2.2.1 相异元素不允许重复的排列 n元集合S的一个r排列是指先从S中选出r个元素，然后将其按次序排列。一般用P(n,r)表示n元集合的r排列数。 2.2.2 圆周排列（循环排列） 在m个相异元素中，每次取n个元素（这n个元素也要求不能有重复）排在一个圆周上，叫做一个圆周排列。 2.2.3 相异元素允许重复的排列 2.2.4 多重集的排列 2.3 组合 相异元素不允许重复的组合 相异元素允许重复的组合（重复数无限） 相异元素允许重复的组合（重复数有限） 2.3.1 相异元素不允许重复的组合 2.3.2 相异元素允许重复的组合（重复数无限） 计数问题是组合学中研究最多的内容，它出现在所有的数学分支中，事实上，差不多任何一门学科都要涉及计数问题。对于计算机科学来说，计数问题更具有它特殊的意义。计算机科学需要研究算法，必须对算法所需的运算量和存储单元作出估计，即算法的时间复杂性和空间复杂性分析。在这一章里，我们先介绍两个一般性的原则——加法原则和乘法原则，然后提出几类最基本的计数问题，给出相应的计数公式，并指出它们与各类分配问题之间的联系。 应用加法原理的技巧在于把集合A划分为“不太多的易于处理的部分。” 加法原理：合理分类，按元素性质分类，分类标准明确。 乘法原理：准确分步，按事情发生连续过程分步，分步层次清楚。 加法原理和乘法原理是两个即浅显又十分重要的计数原理。在应用加法原理时，需要格外注意的是各个部分的互斥性，否则无法应用加法原理。此外，应用加法原理的技巧在于把要计数的集合划分成“不太多的易于处理的部分”。而应用乘法原理的关键则在于如何设计计数的步骤。 在许多计数问题中，既要应用加法原理，也要应用乘法原理，至于何时应用，如何应用则需要通过大量的解题实践去积累经验。可以说，精通加法原理和乘法原理对成为专业的计数专家是必不可少的。 显然有 P(n,r)=0（rn）； P(n,1)=n（n≥1）； 例1：将数码1，2，3，4，5，6进行排列，问： （1）使得数码2正好在数码5的左邻的排列有多少种？ （2）使得数码2在数码5的左边的排列有多少种？ （3）将标号为1，2，…，n的n个球进行排列，在1号球和2号球之间恰有r个球的排列有多少种？ 例2：从{1,2, …,9}中选出不同的7个数字组成的七位数，要求5与6不相邻，问有多少种方法？ 从m+1个元素里，每次取出n个元素进行排列，则 （1）有多少种排列？ （2）其中不含某一元素的排列有多少种？ （3）其中一定含某一元素的排列有多少种？ （4）从上面的结果，可以得出怎么样的关系式？ 例1：8个围在一圆桌开会，其中正副组长各1个，记录1人。若正副组长相邻而坐，有多少种坐法？若记录人坐于正副组长中间，有多少种坐法？ 例2：10个男生和5个女生聚餐，围坐在圆桌旁，任意两个女生不相邻的坐法有多少种？ 例3：由20颗不同颜色的珍珠可以串成多少种不同的项链？ 例4：六男六女围坐一桌，如果男女交替围坐，可有多少种围坐方式？ 例5：10个人要围一圆桌就坐，其中有两人不愿彼此挨着，问共有多少种不同就坐方法？ 例6：将6个红珠，8个黄珠，1个白珠串成一项链，则项链可能出现的种类共有多少？ 例7：8个女孩，25个男孩围成一个圆圈，每两个女孩子之间至少站2个男孩，共有多少种不同的排列方法？ 从k个相异元素里，每次取出允许重复使用的r个元素，按照一定的顺序排列一列，叫做k个相异元素允许重复的r元排列，简称重复排列。 利用复合集的概念，我们也可以如下叙述： 设S为具有k个不同元素，且每个元素的重复数都是无穷的一个复合集，则从S中任取r个元素的排列种数为kr . 例1：用26个英文字母可以构造出多少个包含4个元音字母、长度为8的字符串？ 例2：不超过四位的三进制数共有多少个？ 例1：将6个蓝球，5个红球，4个白球，3个黄球排成一行，要求黄球不挨着，问有多少种排列方式？ 例2：求集合{3·a,2·b,4·c}的8排列个数。 例1：系里欲将6名保送研究生推荐给3个单位，每个单位2名，问有多少种方案？ 例2：系里欲将6名学生分成三个小组，每组两个学生，有多少种方案？ 例3：从1，2，…，100中选出两个不同的数，使其和为偶数，问有多少种取法？ 例4：如果每个词包含3，4或5个元音，那么用字母表中的26个字母可以构造多少个8-字母词？ 例5：求至少出现一个6且能被3整除的五位数的个数。 例6：用组合数性质推导1--n的平方和公式。 例7：用组合