第四章 排列与组合.doc

第四章 排列与组合一、考核知识点： 加法原理、乘法原理初等排列组合，可重复的排列与组合模型与公式筛法原理抽屉原理 二、考核要求：1. 理解加法原理和乘法原理。熟练掌握初等排列和组合。2. 掌握可重复排列与组合。了解排列组合模型，熟练掌握排列组合公式。3. 理解筛法原理，掌握其初等证明方法及其简单应用。4.了解递推公式原理、扰乱排列等的概念。 5.知道抽屉原理，会简单应用。三、重点难点解析一、 初等排列、组合与模型1. 加法原理 完成一件事，有几种方式，第一种方式有n1种方法，第二种方式有n2种方法，第r种方式有nr种方法，不管采用哪种方法都能完成这件事，则完成这件事的方法数为n1+n2+nr2. 乘法原理 完成一件事，有几个步骤，第一步有n1种方法，第2步有n2种方法，第r步有nr种方法，要完成这件事，必须通过r个步骤，那末完成这件事的总方法数为n1n2nr3（可重复的排列）n个元素的集合S的r样本总数为例1 设有4个学生，分配到3个不同车间实习，共有多少种不同的分配方法解 对于第一个学生来说它有3种选择，对于第二个学生来说也有3种选择，第三个学生和第四个学生都有3种选择由乘法原理可知，共有34种分配方法4 （不可重复的排列）n个元素的集合S的r排列总数为5 （不可重复的组合）n个元素的集合S的r组合总数为6（可重复的组合）从n个元素中取出r个元素的组合数为例2 有4套相同的课本，每套有6本不同的书籍，从每一套中取一本书，共有多少种取法？解 实际就是6本书里取4本书，且允许重复取，所以，共有 种例3 投掷两个均匀的骰子，一共能投出多少种不同的情况解 每一个骰子有6个面（由16点组成），所求的问题相当于从6个元素取2个元素（允许重复取）的方法数，所以为种方法7 含有n个不同元素S的r个分类的数为8 （可重复的排列）S中含有个相同的，个相同的，个相同的，且 +=，则S中的全排列个数为例4 将展开合并同类项后，问一共有多少项，其中的系数为多少解 展开后每一项都是7次的项，它的不同项实际上是从三个元素x,y,z取7个元素（允许重复取）的方法数，因而为，所以一共有36项而的系数，为从3个元素x,y,z中取2个x，3个y，2个z的排列总数，即为，所以的系数这210例5 若有4个3，4个5，2个6和2个7，这12个数字共能组成多少个不同的12位数解 实际上是12个元素其中有4个相同的3，4个相同的5，2个相同的6和2个相同的7的全排列个数，因而为例6. 将标号为1,2,3,4,5,6,7的七个彩球按下列要求排成一排，分别有多少种排法？(1) 1,2号彩球必须排在两端；(2) 1不能排在左端，2不能排在右端解：(1)将 1,2号彩球必须排在两端有排法，其余5个彩球任意排列，有种排法， 于是，所求的排列=2120=240； （2）全部彩球排列，共有种排法。其中1号在左端的排列有种，2号在左端的排列也有种，同时1号在左端且2号在右端的排列有种于是，所求为-2+=5040-2720+120=3720 9 排列组合典型模型与公式典型模型将r个可以区分的小球投入n个盒中，每盒容量不限，共有种投球方法。将r个可以区分的小球投入n个盒中，每盒不超过1个球，将r个不可以区分的小球投入n个盒中，每盒不超过1个球（nr），共有种投球方法。将r个可以不区分的小球投入n个盒中，每盒容量不限，投球方法数是方程是非负整数解的个数（表示第i个盒中盛球的个数）。此方程的解的个数为10 排列组合公式 说明 1. 熟炼掌握加法原理、乘法原理。掌握初等排列、组合的定理性质，计算公式，并能应用它们计算一些初等的排列组合问题。2 点掌握 n个元素集合S的r-可重复组合数，无重复元素的圆排列（参见教材285页）等结论。3 能够熟练区分不同的排列组合典型模型及公式的简单推倒，并会应用。二、筛法原理1筛法原理也称容斥原理（定理参见教材256页）2定理（容斥原理）设A1，A2，Am是有限集合S的子集合，则 例6 求不大于100而又能被2或3整除的自然数的个数和不能被2或3整除的自然数的个数解 设，分别表示能被2或3整除而不大于100的自然数集合，这时 根据容斥定理则所求能被2或3整除的自然数的个数为=50+33-16=67不能被2或3整除的自然数的个数为例7 由数字1,2和3组成n位数，要求n位数中1,2和3每个数字至少出现一次，求这样的n位数共有多少个解 由数字1,2,3所构成的n位数共有|S|=3n个设S中不含有数字1的n位数集合为A，S中不含有数字2的n位数集合为B,S中不含有数字3的n位数集合为C，则 |A|=|B|=|C|=2n显然为所求集合但是=S-（ABC）所以 = S（ABC） =3n|A|+|B|+|C|AB|AC|BC|+|ABC| =3n32n+3因为|AB|=|BC|=|AC|=1，|A|=|B|=|C|=2n，而|ABC|=0三、递推公式和扰乱排列1递推公式f(n)=f(n1)+f(n2) 由递推公式得出的数列称为斐波那契数列（参见教材290 291页）例 8 某人从楼下到楼上要走11阶楼梯，每步可走一阶或二阶，问有多少种不同走法解 第一步有两种情况： 则f(n)=f(n1)+f(n2) f(11)=f(10)+f(9) 最后，得f(11)=144 定理1 设表示从n个字码取k个字码（但不许取连续两个字码）的方法数，则 定理2 设表示从n个字码取k个字码，但不允许取连续两个字码（n和1算连续字码）的方法数，那么 2扰乱排列 例9 5个数码1,2,5的扰乱排列总数是 （）四、抽屉原理如果把n+1件物品放入n个抽屉里，则至少有1个抽屉里的物品不少于2件。例10 在一个正方形内，任意给定5点，则其中必有两点之间的距离不大于