排列与组合(原汁原味orange).doc

排列与组合 一、考核知识点： 加法原理、乘法原理 初等排列组合，可重复的排列与组合 模型与公式 筛法原理 抽屉原理 二、考核要求： 1. 理解加法原理和乘法原理。熟练掌握初等排列和组合。 2. 掌握可重复排列与组合。了解排列组合模型，熟练掌握排列组合公式。 3. 理解筛法原理，掌握其初等证明方法及其简单应用。 4.了解递推公式原理、扰乱排列等的概念。  5.知道抽屉原理，会简单应用。 三、重点难点解析 初等排列、组合与模型 1. 加法原理 完成一件事，有几种方式，第一种方式有n1种方法，第二种方式有n2种方法，……，第r种方式有nr种方法，不管采用哪种方法都能完成这件事，则完成这件事的方法数为n1+n2+…+nr． 2. 乘法原理 完成一件事，有几个步骤，第一步有n1种方法，第2步有n2种方法，……，第r步有nr种方法，要完成这件事，必须通过r个步骤，那末完成这件事的总方法数为n1×n2×…×nr． 3．（可重复的排列）n个元素的集合S的r－样本总数为 例1 设有4个学生，分配到3个不同车间实习，共有多少种不同的分配方法． 解 对于第一个学生来说它有3种选择，对于第二个学生来说也有3种选择，第三个学生和第四个学生都有3种选择．由乘法原理可知，共有34种分配方法． （不可重复的排列）n个元素的集合S的r－排列总数为 （不可重复的组合）n个元素的集合S的r－组合总数为 6．（可重复的组合）从n个元素中取出r个元素的组合数为 例2 有4套相同的课本，每套有6本不同的书籍，从每一套中取一本书，共有多少种取法？ 解 实际就是6本书里取4本书，且允许重复取，所以，共有 种． 例3 投掷两个均匀的骰子，一共能投出多少种不同的情况． 解 每一个骰子有6个面（由1～6点组成），所求的问题相当于从6个元素取2个元素（允许重复取）的方法数，所以为种方法． 含有n个不同元素S的r个分类的数为 （可重复的排列）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个彩球任意排列，有种排法， 于是，所求的排列×=2×120=240； （2）全部彩球排列，共有种排法。其中1号在左端的排列有种，2号在左端的排列也有种，同时1号在左端且2号在右端的排列有种． 于是，所求为-2+=5040-2×720+120=3720 排列组合典型模型与公式 典型模型 ①将r个可以区分的小球投入n个盒中，每盒容量不限，共有种投球方法。 ②将r个可以区分的小球投入n个盒中，每盒不超过1个球， ③将r个不可以区分的小球投入n个盒中，每盒不超过1个球（n≥r），共有种投球方法。 ④将r个可以不区分的小球投入n个盒中，每盒容量不限，投球方法数是方程是非负整数解的个数（表示第i个盒中盛球的个数）。 此方程的解的个数为 排列组合公式 ① ② ③ ④ ⑤ ⑥ ⑦ 说明 1. 熟炼掌握加法原理、乘法原理。掌握初等排列、组合的定理性质，计算公式，并能应用它们计算一些初等的排列组合问题。 点掌握 n个元素集合S的r-可重复组合数，无重复元素的圆排列（参见教材285页）等结论。 能够熟练区分不同的排列组合典型模型及公式的简单推倒，并会应用。 二、筛法原理 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