【科学知识】排列组合的基本理论和公式

【科学知识】排列组合的基本理论和公式 排列组合 排列组合是组合学最基本的概念。所谓排列就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素不考虑排序。排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。 排列组合与古典概率论关系密切。 排列组合公式 定义 排列 公式P是排列公式从N个元素取M个进行排列即排序. P是旧用法现在教材上多用A即Arrangement 组合 公式C是组合公式从N个元素取R个不进行排列即不排序。 符号 常见的一道题目 C-组合数 P-排列数 现在教材为A N-元素的总个数 R-参与选择的元素个数 -阶乘 如55×4×3×2×1120 C-Combination 组合 P-Permutation排列 现在教材为A-Arrangement 一些组合恒等式 组合恒等式 排列组合常见公式 排列组合常见公式 历史 1772年旺德蒙德以np表示由n个不同的元素中每次取p个的排列数。而欧拉则于1771年以 及于1778年以表示由n个不同元素中每次取出p个元素的组合数。至1872年埃汀肖森引入了 以表相同之意这组合符号Signs of Combinations一直 沿用至今。 1830年皮科克引入符号Cr以表示由n个元素中每次取出 r个元素的组合数 表示由n个元素中每次取r个元素的排列数1869年或稍早些剑桥的古德文以符号nPr 这用法亦延用至今。按此法nPn便相当於现在的n。 1880年鲍茨以nCr及nPr分别表示由n个元素取出r个的组合数与排列数六年后惠特渥斯以及表示相同之意而且他还以表示可重复的组合数。至1899年克里斯托尔以nPr及nCr分别表示由n个不同元素中 每次取出r个不重复之元素的排列数与组合数并以nHr表示相同意义下之可重复的排列数这三种符号也通用至今。 1904年内托为一本百科辞典所写的辞条中以 表示上述nPr之意以表示上述nCr之意后者亦同时采用了。这些符号也一直用到现代。 组合数的奇偶 奇偶定义 对组合数Cnk nk将nk分别化为二进制若某二进制位对应的n为0而k为1 则Cnk为偶数否则为奇数。 判定方法 组合数的奇偶性判定方法为: 结论 对于Cnk若nk k 则cnk为奇数否则为偶数。 证明 利用数学归纳法 由Cnk Cn-1k Cn-1k-1 对应于杨辉三角 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 ……………… 可以验证前面几层及k 0时满足结论下面证明在Cn-1k和Cn-1k-1 k 0 满足结论的情况下 Cnk满足结论。 1.假设Cn-1k和Cn-1k-1为奇数 则有n-1k k n-1k-1 k-1 由于k和k-1的最后一位在这里的位指的是二进制的位下同必然是不同的所以n-1的最后一位必然是1 。 现假设nk k。 则同样因为n-1和n的最后一位不同推出k的最后一位是1。 因为n-1的最后一位是1则n的最后一位是0所以nk k与假设矛盾。 所以得nk k。 2.假设Cn-1k和Cn-1k-1为偶数 则有n-1k k n-1k-1 k-1 现假设nk k. 则对于k最后一位为1的情况 此时n最后一位也为1所以有n-1k-1 k-1与假设矛盾。 而对于k最后一位为0的情况 则k的末尾必有一部分形如10 代表任意个0。 相应的n对应的部分为 1 代表0或1。 而若n对应的中只要有一个为1则n-1k k成立所以n对应部分也应该是10。 则相应的k-1和n-1的末尾部分均为01所以n-1k-1 k-1 成立与假设矛盾。 所以得nk k。 由1和2得出当Cnk是偶数时nk k。 3.假设Cn-1k为奇数而Cn-1k-1为偶数 则有n-1k k n-1k-1 k-1 显然k的最后一位只能是0否则由n-1k k即可推出n-1k-1 k-1。 所以k的末尾必有一部分形如10 相应的n-1的对应部分为 1 相应的k-1的对应部分为 01 则若要使得n-1k-1 k-1 则要求n-1对应的中至少有一个是0. 所以n的对应部分也就为 1 不会因为进位变1为0 所以 nk k。 4.假设Cn-1k为偶数而Cn-1k-1为奇数 则有n-1k k n-1k-1 k-1 分两种情况 当k-1的最后一位为0时: 则k-1的末尾必有一部分形如: 10 相应的k的对应部分为 : 11 相应的n-1的对应部分 为 : 10 若为11则n-1k k 相应的n的对应部分为 : 11 所以nk k。 当k-1的最后一位为1时: 则k-1的末尾必有一部分形如: 01 前面的0可以是附加上去的 相应的k的对应部分为 : 10 相应的n-1的对应部分为 : 01 若为11则n-1k k 相应的n的对应部分为 : 10 所以nk k。 由34得出当Cnk为奇数时nk k。 综上结论得证 排列组合的基本理论和公式 排列与元素的顺序有关组合与顺序无关如231与213是两个排列231的和与213的和是一个组合 一两个基本原理是排列和组合的基础 1加法原理做一件事完成它可以有n类办法在第一类办法中有m1种不同的方法在第二类办法中有m2种不同的方法……在第n类办法中有mn种不同的方法那么完成这件事共有Nm1m2m3…mn种不同方法 2乘法原理做一件事完成它需要分成n个步骤做第一步有m1种不同的方法做第 二步有m2种不同的方法……做第n步有mn种不同的方法那么完成这件事共有Nm1×m2×m3×…×mn种不同的方法 这里要注意区分两个原理要做一件事完成它若是有n类办法是分类问题第一类中的方法都是独立的因此用加法原理做一件事需要分n个步骤步与步之间是连续的只有将分成的若干个互相联系的 ”和步骤依次相继完成这件事才算完成因此用乘法原理 这样完成一件事的分“类“步”是有本质区别的因此也将两个原理区分开来 二排列和排列数 1排列从n个不同元素中任取mm?n个元素按照一定的顺序排成一列叫做从n个不同元素中取出m个元素的一个排列 从排列的意义可知如果两个排列相同不仅这两个排列的元素必须完全相同而且排列的顺序必须完全相同这就告诉了我们如何判断两个排列是否相同的 排列数公式从n个不同元素中取出mm?n个元素的所有排列 当mn时为全排列方法 2 Pnnnn1n2…3?2?1n 三组合和组合数 1组合从n个不同元素中任取mm?n个元素并成一组叫做从 n个不同元素中取出m个元素的一个组合 从组合的定义知如果两个组合中的元素完全相同不管元素的顺序如何都是相同的组合只有当两个组合中的元素不完全相同时才是不同的组合 2组合数从n个不同元素中取出mm?n个元素的所有组合的个 这里要注意排列和组合的区别和联系从n个不同元素中任取mm?n个元素“按照一定的顺序排成一列”与“不管怎样的顺序并成一组”这是有本质区别的 一、排列组合部分是中学数学中的难点之一 原因在于 1从千差万别的实际问题中抽象出几种特定的数学模型需要较强的抽象思维能力 2限制条件有时比较隐晦需要我们对问题中的关键性词特别是逻辑关联词和量词准确理解 3计算手段简单与旧知识联系少但选择正确合理的计算 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 时需要的思维量较大 4计算方案是否正确往往不可用直观方法来检验要求我们搞清概念、原理并具有较强的分析能力。 二、两个基本计数原理及应用 1加法原理和分类计数法 1加法原理 2加法原理的集合形式 3分类的要求 每一类中的每一种方法都可以独立地完成此任务两类不同办法中的具体方法互不相同即分类不重完成此任务的任何一种方法都属于某一类即分类不漏 2乘法原理和分步计数法 1乘法原理 2合理分步的要求 任何一步的一种方法都不能完成此任务必须且只须连续完成这n步才能完成此任务各步计数相互独立只要有一步中所采取的方法不同则对应的完成此事的方法也不同 例题分析 排列组合思维方法选讲 1首先明确任务的意义 例1. 从1、2、3、……、20这二十个数中任取三个不同的数组成等差数列这样的不同等差数列有________个。 分析首先要把复杂的生活背景或其它数学背景转化为一个明确的排列组合问题。 设abc成等差? 2bac 可知b由ac决定 又? 2b是偶数? ac同奇或同偶即分别从135……19或2468……20这十个数中选出两个数进行排列由此就可确定等差数列C2102P22因而本题为180。 例2. 某城市有 4条东西街道和6条南北的街道街道之间的间距相同如图。若规定只能向东或向北两个方向沿图中路线前进则从M到N有多少种不同的走法 分析对实际背景的分析可以逐层深入 一从M到N必须向上走三步向右走五步共走八步。 二每一步是向上还是向右决定了不同的走法。 三事实上当把向上的步骤决定后剩下的步骤只能向右。 从而任务可叙述为从八个步骤中选出哪三步是向上走就可以确定走法数 ? 本题答案为56。 2分析是分类还是分步是排列还是组合 注意加法原理与乘法原理的特点分析是分类还是分步是排列还是组合 例3在一块并排的10垄田地中选择二垄分别种植AB两种作物每种种植一垄为有利于作物生长要求AB两种作物的间隔不少于6垄不同的选法共有______种。 分析条件中“要求A、B两种作物的间隔不少于6垄”这个条件不容易用一个包含排列数组合数的式子表示因而采取分类的方法。 第一类A在第一垄B有3种选择 第二类A在第二垄B有2种选择 第三类A在第三垄B有一种选择 同理A、B位置互换 共12种。 例4从6双不同颜色的手字腥稳?只其中恰好有一双同色的取法有________。 A240 B180 C120 D60 分析显然本题应分步解决。 一从6双中 种方法 二从剩下的十只手套中任选一只有10种方法。 三从选出一双同色的手套有6 除前所涉及的两双手套之外的八只手套中任选一只有8种方法 四由于选取与顺序无关因二三中的选法重复一次因而共240种。 例5身高互不相同的6个人排成2横行3纵列在第一行的每一个人都比他同列的身后的人个子矮则所有不同的排法种数为_______。 分析每一纵列中的两人只要选定则他们只有一种站位方法因而每一纵列 种。 例6在11名工人中有5人只的排队方法只与人的选法有关系共有三纵列从而有90 能当钳工4人只能当车工另外2人能当钳工也能当车工。现从11人中选出4人当钳工4人当车工问共有多少种不同的选法 分析采用加法原理首先要做到分类不重不漏如何做到这一点分类的标准必须前后统一。 以两个全能的工人为分类的对象考虑以他们 当中有几个去当钳工为分类标准。 第一类这两个人都去当钳工有10种 第二类这两人有一个去当钳工有100种 第三类这两人都不去当钳工有75种。 因而共有185种。 例7现有印着0l3579的六张卡片如果允许9可以作6用那么从中任意抽出三张可以组成多少个不同的三位数 分析有同学认为只要把0l3579的排法数乘以2即为所求但实际上抽出的三个数中有9的话才可能用6替换因而必须分类。 抽出的三数含0含9有32种方法 抽出的三数含0不含9有24种方法 抽出的三数含9不含0有72种方法 抽出的三数不含9也不含0有24种方法。 因此共有32247224152种方法。 例8停车场划一排12个停车位置今有8辆车需要停乓 罂粘滴涣 谝黄鸩煌 耐,捣椒ㄊ莀_______种。 分析把空车位看成一个元素和8辆车共九个元素排列因而共有362880种停车方法。 3特殊优先 特殊元素优先处理特殊位置优先考虑 例9六人站成一排求 1甲不在排头乙不在排尾的排列数 2甲不在排头乙不在排尾且甲乙不相邻的排法数 分析1先考虑排头排尾但这两个要求相互有影响因而考虑分类。 第一类乙在排头有p55种站法。 第二类乙不在排头当然他也不能在排尾有4X4XP44种站法 共p554X4XP44种站法。 2第一类甲在排尾乙在排头有P44种方法。 第二类甲在排尾乙不在排头有3XP44种方法。 第三类乙在排头甲不在排头有4XP44种方法。 第四类甲不在排尾乙不在排头有P33XP44种方法。 共P443XP444XP44P33XP44312种。 例10对某件产品的6件不同正品和4件不同次品进行一一测试至区分出所有次品为止。若所有次品恰好在第五次测试时被全部发现则这样的测试方法有多少种可能 分析本题意指第五次测试的产品一定是次品并且是最后一个次品因而第五次测试应算是特殊位置了分步完 成。 第一步第五次测试的有C4.1种可能 第二步前四次有一件正品有C6.1中可能。 第三步前四次有P4.4种可能。 ? 共有种可能。 4捆绑与插空 例11. 8人排成一队 1甲乙必须相邻 2甲乙不相邻 3甲乙必须相邻且与丙不相邻 4甲乙必须相邻丙丁必须相邻 5甲乙不相邻丙丁不相邻 分析1甲乙必须相邻就是把甲乙 捆绑甲乙可交换 和7人排列 P7.72 2甲乙不相邻P8.8-P7.72。 3甲乙必须相邻且与丙不相邻先求甲乙必须相邻且与丙相邻 P6.622 甲乙必须相邻且与丙不相邻 P7.72-P6.622 4甲乙必须相邻丙丁必须相邻 P6.622 5甲乙不相邻丙丁不相邻P8.8-P7.722P6.622 例12. 某人射击8枪命中4枪恰好有三枪连续命中有多少种不同的情况 分析? 连续命中的三枪与单独命中的一枪不能相邻因而这是一个插空问题。另外没有命中的之间没有区 别不必计数。即在四发空枪之间形成的5个空中选出2个的排列即P5.2。 例13. 马路上有编号为l23……10 十个路灯为节约用电又看清路面可以把其中的三只灯关掉但不能同时关掉相邻的两只或三只在两端的灯也不能关掉的情况下求满足条件的关灯方法共有多少种 分析即关掉的灯不能相邻也不能在两端。又因为灯与灯之间没有区别因而问题为在7盏亮着的灯形成的不包含两端的6个空中选出3个空放置熄灭的灯。 ? 共C6.320种方法。 5间接计数法 .1排除法 例14. 三行三列共九个点以这些点为顶点可组成多少个三角形 分析有些问题正面求解有一定困难可以采用间接法。 所求问题的方法数任意三个点的组合数-共线三点的方法数 ? 共种。 例15正方体8个顶点中取出4个可组成多少个四面体 分析所求问题的方法数任意选四点的组合数-共面四点的方法数C8.4-1270-1258个。 例16. l23……9中取出两个分别作为对数的 ? 共 底数和真数可组成多少个不同数值的对数 分析由于底数不能为1。 1当1选上时1必为真数? 有一种情况。 2当不选1时从2--9中任取两个分别作为底数真数共其中log2为底4log3为底9log4为底2log9为底3 log2为底3log4为底9 log3为底2log9为底4. 因而一共有53个。 3补上一个阶段转化为熟悉的问题 例17. 六人排成一排要求甲在乙的前面不一定相邻共有多少种不同的方法 如果要求甲乙丙按从左到右依次排列呢 分析一实际上甲在乙的前面和甲在乙的后面两种情况对称具有相同的排法数。因而有360种。 二先考虑六人全排列其次甲乙丙三人实际上只能按照一种顺序站位因而前面的排法数重复了种 ? 共120种。 例185男4女排成一排要求男生必须按从高到矮的顺序共有多少种不同的方法 分析首先不考虑男生的站位要求共P9.9种男生从左至右按从高到矮的顺序只有一种站法因而上述站法重复了次。因而有9×8×7×63024种。 若男生从右至左按从高到矮的顺序只有一种站法 同理也有3024种综上有6048种。 例19. 三个相同的红球和两个不同的白球排成一行共有多少种不同的方法 分析先认为三个红球互不相同共种方法。而由于三个红球所占位置相同的情况下共有变化因而共20种。 6挡板的使用 例2010个名额分配到八个班每班至少一个名额问有多少种不同的分配方法 分析把10个名额看成十个元素在这十个元素之间形成的九个空中选出七个位置放置档板则每一种放置方式就相当于一种分配方式。因而共36种。 7注意排列组合的区别与联系 所有的排列都可以看作是先取组合再做全排列同样组合如补充一个阶段排序可转化为排列问题。 例21. 从0l2……9中取出2个偶数数字3个奇数数字可组成多少个无重复数字的五位数 分析先选后排。另外还要考虑特 殊元素0的选取。 一两个选出的偶数含0则有种。 二两个选出的偶数字不含0则有种。 例22. 电梯有7位乘客在10层楼房的每一层停留如果三位乘客从同一层出去另外两位在同一层出去最后两人各从不同的楼层出去有多少种不同的下楼方法 分 析一先把7位乘客分成3人2人一人一人四组有种。 二选择10层中的四层下楼有种。 ? 共有种。 例23. 用数字012345组成没有重复数字的四位数 1可组成多少个不同的四位数 2可组成多少个不同的四位偶数 3可组成多少个能被3整除的四位数 4将1中的四位数按从小到大的顺序排成一数列问第85项是什么 分析1有个。 2分为两类0在末位则有种0不在末位则有种。 ? 共种。 3先把四个相加能被3整除的四个数从小到大列举出来即先选 0123 0135 0234 0345 1245 它们排列出来的数一定可以被3整除再排列有4×96种。 4首位为1的有60个。 前两位为20的有12个。 前两位为21的有12个。 因而第85项是前两位为23的最小数即为2301。 8分组问题 例24. 6本不同的书 1 分给甲乙丙三人每人两本有多少种不同的分法 2 分成三堆每堆两本有多少种不同的分法 3 分成三堆一堆一本一堆两本一堆三本有多少种不同的分法 4 甲一本乙两本丙三本有多少种不同的分法 5 分给甲乙丙三人其中一人一本一人两本第三人三本有多少种不同的分法 分析1有中。 2即在1的基础上除去顺序有种。 3有种。由于这是不平均分组因而不包含顺序。 4有种。同3原因是甲乙丙持有量确定。 有种。 例25. 6人分乘两辆不同的车每车最多乘4人则不同的乘车方法为_______。 5 分析一考虑先把6人分成2人和4人3人和3人各两组。 第一类平均分成3人一组有种方法。 第二类分成2人4人各一组有种方法。 二再考虑分别上两辆不同的车。 综合一二有种。 例26. 5名学生分配到4个不同的科技小组参加活动每个科技小组至少有一名学生参加则分配方法共有________种. 分析一先把5个学生分成二人一人一人一 个元素三个板人各一组。 其中涉及到平均分成四组有C53种分组方法。 可以看成5不空的隔板法 二再考虑分配到四个不同的科技小组有A44种 由一二可知共240种。 在八卦中亦运用到了排列组合 音乐专辑 专辑中文名: 排列组合 歌手: 这位太太 音乐风格: 流行 发行时间: 2010年02月27日 地区: 台湾 语言: 普通话 唱片公司喜玛拉雅 专辑介绍 不需要说太多离别的话我们要跟大家暂别了。你可以说天下没有不散的筵席也可以说未来仍有无限可能总之我们要休息好一阵子。想要快快乐乐跟太太去买菜的朋友们就在今夜了压箱宝陈年老歌独门密技通通不会少喔 关于《排列组合》如果太太不是六个人如果太太再电一点就如同名称所示这张迷你专辑是由太太团员以2-3人为单位重新排列组合以电子声响为主各自翻玩出歌曲的不同面貌2008年在第一张专辑《是谁》与第二张专辑《我是不是还不够好》中间男太太从军的日子里我们做了一些小尝试。如果大家还记得《而我眼已垂落》中的电气节奏那么你或许会期待这张以合成器手蛋为主搭配其他团员所激荡出的不同火花。迷你专辑中包含5首旧歌的重新编曲另外加上从未发表过的新歌《花瓶》以及回到六人乐团编制的冬日必备暗恋曲《口袋》满满7首歌限量1000张 《排列组合》专辑使用主唱阿牧画家母亲“金芬华”的油画画作母女首度合作 专辑曲目 01. 情歌 Electric 02. 不是不想念 Bleep 03. 花瓶 04. 错 Snow 05. 口袋 06. 十八岁 Shuffle 07. 立场 Remix