《排列组合精讲》word版.docx

排列组合 百科名片排列组合是组合学最基本的概念。所谓排列，就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。 排列组合与古典概率论关系密切。 目录隐藏定义 1. 排列 2. 组合 3. 符号 4. 历史组合数的奇偶 1. 奇偶定义 2. 判定方法排列组合的基本理论和公式 1. (一)两个基本原理是排列和组合的基础 2. (二)排列和排列数 3. (三)组合和组合数 4. 一、排列组合部分是中学数学中的难点之一 5. 二、两个基本计数原理及应用例题分析 1. 1首先明确任务的意义 2. 2分析是分类还是分步，是排列还是组合 3. 3特殊优先 4. 4捆绑与插空 5. 5间接计数法 6. 6挡板的使用 7. 7注意排列组合的区别与联系： 8. 8分组问题音乐专辑 1. 专辑介绍 2. 专辑曲目定义 1. 排列 2. 组合 3. 符号 4. 历史组合数的奇偶 1. 奇偶定义 2. 判定方法排列组合的基本理论和公式 1. (一)两个基本原理是排列和组合的基础 2. (二)排列和排列数 3. (三)组合和组合数 4. 一、排列组合部分是中学数学中的难点之一 5. 二、两个基本计数原理及应用例题分析 1. 1首先明确任务的意义 2. 2分析是分类还是分步，是排列还是组合 3. 3特殊优先 4. 4捆绑与插空 5. 5间接计数法 6. 6挡板的使用 7. 7注意排列组合的区别与联系： 8. 8分组问题音乐专辑 1. 专辑介绍 2. 专辑曲目 排列组合公式编辑本段定义排列公式P是排列公式，从N个元素取R个进行排列（即排序）. （P是旧用法，现在教材上多用A，即Arrangement） 组合公式C是组合公式，从N个元素取R个，不进行排列（即不排序）。 符号 常见的一道题目C-组合数 P-排列数 （现在教材为A） N-元素的总个数 R-参与选择的元素个数 !-阶乘 ，如5！=54321=120 C-Combination 组合 P-Permutation排列 (现在教材为A-Arrangement) 一些组合恒等式 组合恒等式排列组合常见公式 排列组合常见公式历史1772年，旺德蒙德以np表示由n个不同的元素中每次取p个的排列数。而欧拉则于1771年以 及于1778年以表示由n个不同元素中每次取出p个元素的组合数。至1872年，埃汀肖森引入了 以表相同之意，这组合符号（Signs of Combinations）一直 沿用至今。 1830年，皮科克引入符号Cr以表示由n个元素中每次取出 r个元素的组合数；1869年或稍早些，剑桥的古德文以符号nPr 表示由n个元素中每次取r个元素的排列数，这用法亦延用至今。按此法，nPn便相当於现在的n!。 1880年，鲍茨以nCr及nPr分别表示由n个元素取出r个的组合数与排列数；六年后，惠特渥斯以及表示相同之意，而且，他还以表示可重复的组合数。至1899年，克里斯托尔以nPr及nCr分别表示由n个不同元素中 每次取出r个不重复之元素的排列数与组合数，并以nHr表示相同意义下之可重复的排列数，这三种符号也通用至今。 1904年，内托为一本百科辞典所写的辞条中，以 表示上述nPr之意，以表示上述nCr之意，后者亦同时采用了。这些符号也一直用到现代。 编辑本段组合数的奇偶奇偶定义对组合数C(n,k) (n=k)：将n,k分别化为二进制，若某二进制位对应的n为0，而k为1 ，则C(n,k)为偶数；否则为奇数。 判定方法组合数的奇偶性判定方法为: 结论： 对于C(n,k),若n&k = k 则c(n,k)为奇数，否则为偶数。 证明： 利用数学归纳法： 由C(n,k) = C(n-1,k) + C(n-1,k-1); 对应于杨辉三角： 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 可以验证前面几层及k = 0时满足结论，下面证明在C(n-1,k)和C(n-1,k-1) (k 0) 满足结论的情况下， C(n,k)满足结论。 1).假设C(n-1,k)和C(n-1,k-1)为奇数： 则有：(n-1)&k = k; (n-1)&(k-1) = k-1; 由于k和k-1的最后一位(在这里的位指的是二进制的位，下同)必然是不同的，所以n-1的最后一位必然是1 。 现假设n&k = k。 则同样因为n-1和n的最后一位不同推出k的最后一位是1。 因为n-1的最后一位是1，则n的最后一位是0，所以n&k != k，与假设矛盾。 所以得n&k != k。 2).假设C(n-1,k)和C(n-1,k-1)为偶数： 则有：(n-1)&k != k; (n-1)&(k-1) != k-1; 现假设n&k = k. 则对于k最后一位为1的情况： 此时n最后一位也为1，所以有(n-1)&(k-1) = k-1，与假设矛盾。 而对于k最后一位为0的情况： 则k的末尾必有一部分形如：10; 代表任意个0。 相应的，n对应的部分为： 1*; *代表0或1。 而若n对应的*中只要有一个为1，则(n-1)&k = k成立，所以n对应部分也应该是10。 则相应的，k-1和n-1的末尾部分均为01,所以(n-1)&(k-1) = k-1 成立，与假设矛盾。 所以得n&k != k。 由1)和2)得出当C(n,k)是偶数时，n&k != k。 3).假设C(n-1,k)为奇数而C(n-1,k-1)为偶数： 则有：(n-1)&k = k; (n-1)&(k-1) != k-1; 显然，k的最后一位只能是0，否则由(n-1)&k = k即可推出(n-1)&(k-1) = k-1。 所以k的末尾必有一部分形如：10; 相应的，n-1的对应部分为： 1*; 相应的，k-1的对应部分为： 01; 则若要使得(n-1)&(k-1) != k-1 则要求n-1对应的*中至少有一个是0. 所以n的对应部分也就为 ： 1*; (不会因为进位变1为0) 所以 n&k = k。 4).假设C(n-1,k)为偶数而C(n-1,k-1)为奇数： 则有：(n-1)&k != k; (n-1)&(k-1) = k-1; 分两种情况： 当k-1的最后一位为0时: 则k-1的末尾必有一部分形如: 10; 相应的，k的对应部分为 : 11; 相应的，n-1的对应部分为 : 1*0; (若为1*1,则(n-1)&k = k) 相应的，n的对应部分为 : 1*1; 所以n&k = k。 当k-1的最后一位为1时: 则k-1的末尾必有一部分形如: 01; (前面的0可以是附加上去的) 相应的，k的对应部分为 : 10; 相应的，n-1的对应部分为 : 01; (若为11，则(n-1)&k = k) 相应的，n的对应部分为 : 10; 所以n&k = k。 由3),4)得出当C(n,k)为奇数时，n&k = k。 综上，结论得证! 编辑本段排列组合的基本理论和公式排列与元素的顺序有关，组合与顺序无关如231与213是两个排列，231的和与213的和是一个组合 (一)两个基本原理是排列和组合的基础(1)加法原理：做一件事，完成它可以有n类办法，在第一类办法中有m1种不同的方法，在第二类办法中有m2种不同的方法，在第n类办法中有mn种不同的方法，那么完成这件事共有Nm1m2m3mn种不同方法 (2)乘法原理：做一件事，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法，做第n步有mn种不同的方法，那么完成这件事共有Nm1m2m3mn种不同的方法 这里要注意区分两个原理，要做一件事，完成它若是有n类办法，是分类问题，第一类中的方法都是独立的，因此用加法原理；做一件事，需要分n个步骤，步与步之间是连续的，只有将分成的若干个互相联系的步骤，依次相继完成，这件事才算完成，因此用乘法原理 这样完成一件事的分“类”和“步”是有本质区别的，因此也将两个原理区分开来 (二)排列和排列数(1)排列：从n个不同元素中，任取m(mn)个元素，按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列 从排列的意义可知，如果两个排列相同，不仅这两个排列的元素必须完全相同，而且排列的顺序必须完全相同，这就告诉了我们如何判断两个排列是否相同的方法 (2)排列数公式：从n个不同元素中取出m(mn)个元素的所有排列 当mn时，为全排列Pnn=n(n1)(n2)321n！ (三)组合和组合数(1)组合：从n个不同元素中，任取m(mn)个元素并成一组，叫做从 n个不同元素中取出m个元素的一个组合 从组合的定义知，如果两个组合中的元素完全相同，不管元素的顺序如何，都是相同的组合；只有当两个组合中的元素不完全相同时，才是不同的组合 (2)组合数：从n个不同元素中取出m(mn)个元素的所有组合的个 这里要注意排列和组合的区别和联系，从n个不同元素中，任取m(mn)个元素，“按照一定的顺序排成一列”与“不管怎样的顺序并成一组”这是有本质区别的 一、排列组合部分是中学数学中的难点之一原因在于 (1)从千差万别的实际问题中抽象出几种特定的数学模型，需要较强的抽象思维能力； (2)限制条件有时比较隐晦，需要我们对问题中的关键性词(特别是逻辑关联词和量词)准确理解； (3)计算手段简单，与旧知识联系少，但选择正确合理的计算方案时需要的思维量较大； (4)计算方案是否正确，往往不可用直观方法来检验，要求我们搞清概念、原理，并具有较强的分析能力。 二、两个基本计数原理及应用(1)加法原理和分类计数法 1加法原理 2加法原理的集合形式 3分类的要求 每一类中的每一种方法都可以独立地完成此任务；两类不同办法中的具体方法，互不相同(即分类不重)；完成此任务的任何一种方法，都属于某一类(即分类不漏) (2)乘法原理和分步计数法 1乘法原理 2合理分步的要求 任何一步的一种方法都不能完成此任务，必须且只须连续完成这n步才能完成此任务；各步计数相互独立；只要有一步中所采取的方法不同，则对应的完成此事的方法也不同 编辑本段例题分析排列组合思维方法选讲 1首先明确任务的意义例1. 从1、2、3、20这二十个数中任取三个不同的数组成等差数列，这样的不同等差数列有_个。 分析：首先要把复杂的生活背景或其它数学背景转化为一个明确的排列组合问题。 设a,b,c成等差， 2b=a+c, 可知b由a,c决定， 又 2b是偶数， a,c同奇或同偶，即：分别从1，3，5，19或2，4，6，8，20这十个数中选出两个数进行排列，由此就可确定等差数列，C（2,10）*2*P（2,2），因而本题为180。 例2. 某城市有4条东西街道和6条南北的街道，街道之间的间距相同，如图。若规定只能向东或向北两个方向沿图中路线前进，则从M到N有多少种不同的走法? 分析：对实际背景的分析可以逐层深入 （一）从M到N必须向上走三步，向右走五步，共走八步。 （二）每一步是向上还是向右，决定了不同的走法。 （三）事实上，当把向上的步骤决定后，剩下的步骤只能向右。 从而，任务可叙述为：从八个步骤中选出哪三步是向上走，就可以确定走法数， 本题答案为：=56。 2分析是分类还是分步，是排列还是组合注意加法原理与乘法原理的特点，分析是分类还是分步，是排列还是组合 例3在一块并排的10垄田地中，选择二垄分别种植A，B两种作物，每种种植一垄，为有利于作物生长，要求A，B两种作物的间隔不少于6垄，不同的选法共有_种。 分析：条件中“要求A、B两种作物的间隔不少于6垄”这个条件不容易用一个包含排列数，组合数的式子表示，因而采取分类的方法。 第一类：A在第一垄，B有3种选择； 第二类：A在第二垄，B有2种选择； 第三类：A在第三垄，B有一种选择， 同理A、B位置互换 ，共12种。 例4从6双不同颜色的手套中任取4只，其中恰好有一双同色的取法有_。 (A)240 (B)180 (C)120 (D)60 分析：显然本题应分步解决。 （一）从6双中选出一双同色的手套，有6种方法； （二）从剩下的十只手套中任选一只，有10种方法。 （三）从除前所涉及的两双手套之外的八只手套中任选一只，有8种方法； （四）由于选取与顺序无关，因（二）（三）中的选法重复一次，因而共240种。 例5身高互不相同的6个人排成2横行3纵列，在第一行的每一个人都比他同列的身后的人个子矮，则所有不同的排法种数为_。 分析：每一纵列中的两人只要选定，则他们只有一种站位方法，因而每一纵列的排队方法只与人的选法有关系，共有三纵列，从而有=90种。 例6在11名工人中，有5人只能当钳工，4人只能当车工，另外2人能当钳工也能当车工。现从11人中选出4人当钳工，4人当车工，问共有多少种不同的选法? 分析：采用加法原理首先要做到分类不重不漏，如何做到这一点？分类的标准必须前后统一。 以两个全能的工人为分类的对象，考虑以他们当中有几个去当钳工为分类标准。 第一类：这两个人都去当钳工，有10种； 第二类：这两人有一个去当钳工，有100种； 第三类：这两人都不去当钳工，有75种。 因而共有185种。 例7现有印着0，l，3，5，7，9的六张卡片，如果允许9可以作6用，那么从中任意抽出三张可以组成多少个不同的三位数? 分析：有同学认为只要把0，l，3，5，7，9的排法数乘以2即为所求，但实际上抽出的三个数中有9的话才可能用6替换，因而必须分类。 抽出的三数含0，含9，有32种方法； 抽出的三数含0不含9，有24种方法； 抽出的三数含9不含0，有72种方法； 抽出的三数不含9也不含0，有24种方法。 因此共有32+24+72+24=152种方法。 例8停车场划一排12个停车位置，今有8辆车需要停放，要求空车位连在一起，不同的停车方法是_种。 分析：把空车位看成一个元素，和8辆车共九个元素排列，因而共有362880种停车方法。 3特殊优先特殊元素，优先处理；特殊位置，优先考虑 例9六人站成一排，求 (1)甲不在排头，乙不在排尾的排列数 (2)甲不在排头，乙不在排尾，且甲乙不相邻的排法数 分析：（1）先考虑排头，排尾，但这两个要求相互有影响，因而考虑分类。 第一类：乙在排头，有p(5,5)种站法。 第二类：乙不在排头，当然他也不能在排尾，有4X4XP(4,4)种站法， 共p(5,5)+4X4XP(4,4)种站法。 （2）第一类：甲在排尾，乙在排头，有P(4,4)种方法。 第二类：甲在排尾，乙不在排头，有3XP(4,4)种方法。 第三类：乙在排头，甲不在排头，有4XP(4,4)种方法。 第四类：甲不在排尾，乙不在排头，有P(3,3)XP(4,4)种方法。 共P(4,4)+3XP(4,4)+4XP(4,4)+P(3,3)XP(4,4)=312种。 例10对某件产品的6件不同正品和4件不同次品进行一一测试，至区分出所有次品为止。若所有次品恰好在第五次测试时被全部发现，则这样的测试方法有多少种可能? 分析：本题意指第五次测试的产品一定是次品，并且是最后一个次品，因而第五次测试应算是特殊位置了，分步完成。 第一步：第五次测试的有C(4.1)种可能； 第二步：前四次有一件正品有C(6.1)中可能。 第三步：前四次有P(4.4)种可能。 共有种可能。 4捆绑与插空例11. 8人排成一队 (1)甲乙必须相邻 (2)甲乙不相邻 (3)甲乙必须相邻且与丙不相邻 (4)甲乙必须相邻，丙丁必须相邻 (5)甲乙不相邻，丙丁不相邻 分析：（1）甲乙必须相邻，就是把甲乙 捆绑(甲乙可交换) 和7人排列 P(7.7)*2 （2）甲乙不相邻，P(8.8)-P(7.7)*2。 （3）甲乙必须相邻且与丙不相邻，先求甲乙必须相邻且与丙相邻 P(6.6)*2*2 甲乙必须相邻且与丙不相邻 P(7.7)*2-P(6.6)*2*2 （4）甲乙必须相邻，丙丁必须相邻 P(6.6)*2*2 （5）甲乙不相邻，丙丁不相邻，P(8.8)-P(7.7)*2*2+P(6.6)*2*2 例12. 某人射击8枪，命中4枪，恰好有三枪连续命中，有多少种不同的情况? 分析： 连续命中的三枪与单独命中的一枪不能相邻，因而这是一个插空问题。另外没有命中的之间没有区别，不必计数。即在四发空枪之间形成的5个空中选出2个的排列，即P(5.2)。 例13. 马路上有编号为l，2，3，10 十个路灯，为节约用电又看清路面，可以把其中的三只灯关掉，但不能同时关掉相邻的两只或三只，在两端的灯也不能关掉的情况下，求满足条件的关灯方法共有多少种? 分析：即关掉的灯不能相邻，也不能在两端。又因为灯与灯之间没有区别，因而问题为在7盏亮着的灯形成的不包含两端的6个空中选出3个空放置熄灭的灯。 共C(6.3)=20种方法。 5间接计数法.(1)排除法 例14. 三行三列共九个点，以这些点为顶点可组成多少个三角形? 分析：有些问题正面求解有一定困难，可以采用间接法。 所求问题的方法数=任意三个点的组合数-共线三点的方法数， 共种。 例15正方体8个顶点中取出4个，可组成多少个四面体? 分析：所求问题的方法数=任意选四点的组合数-共面四点的方法数， 共C(8.4)-12=70-12=58个。 例16. l，2，3，9中取出两个分别作为对数的底数和真数，可组成多少个不同数值的对数? 分析：由于底数不能为1。 （1）当1选上时，1必为真数， 有一种情况。 （2）当不选1时，从2-9中任取两个分别作为底数，真数，共，其中log2为底4=log3为底9，log4为底2=log9为底3, log2为底3=log4为底9, log3为底2=log9为底4. 因而一共有53个。 (3)补上一个阶段，转化为熟悉的问题 例17. 六人排成一排，要求甲在乙的前面，(不一定相邻)，共有多少种不同的方法? 如果要求甲乙丙按从左到右依次排列呢? 分析：（一）实际上，甲在乙的前面和甲在乙的后面两种情况对称，具有相同的排法数。因而有=360种。 （二）先考虑六人全排列；其次甲乙丙三人实际上只能按照一种顺序站位，因而前面的排法数重复了种， 共=120种。 例185男4女排成一排，要求男生必须按从高到矮的顺序，共有多少种不同的方法? 分析：首先不考虑男生的站位要求，共P(9.9)种；男生从左至右按从高到矮的顺序，只有一种站法，因而上述站法重复了次。因而有=9876=3024种。 若男生从右至左按从高到矮的顺序，只有一种站法， 同理也有3024种，综上，有6048种。 例19. 三个相同的红球和两个不同的白球排成一行，共有多少种不同的方法? 分析：先认为三个红球互不相同，共种方法。而由于三个红球所占位置相同的情况下，共有变化，因而共=20种。 6挡板的使用例2010个名额分配到八个班，每班至少一个名额，问有多少种不同的分配方法? 分析：把10个名额看成十个元素，在这十个元素之间形成的九个空中，选出七个位置放置档板，则每一种放置方式就相当于一种分配方式。因而共36种。 7注意排列组合的区别与联系：所有的排列都可以看作是先取组合，再做全排列；同样，组合如补充一个阶段(排序)可转化为排列问题。 例21. 从0，l，2，9中取出2个偶数数字，3个奇数数字，可组成多少个无重复数字的五位数? 分析：先选后排。另外还要考虑特殊元素0的选取。 （一）两个选出的偶数含0，则有种。 （二）两个选出的偶数字不含0，则有种。 例22. 电梯有7位乘客，在10层楼房的每一层停留，如果三位乘客从同一层出去，另外两位在同一层出去，最后两人各从不同的楼层出去，有多少种不同的下楼方法? 分析：（一）先把7位乘客分成3人，2人，一人，一人四组，有种。 （二）选择10层中的四层下楼有种。 共有种。 例23. 用数字0，1，2，3，4