(排列组合)专题汇总
一、分步乘法原则
李健在参加《我是歌手》节目时曾被问道，7位歌手一共有多少种出场顺序。
首先，我们从第一位出场的歌手考虑，有7种可能。当第一位确定后，第二位出场的歌手就只有6种可能。当第二位确定后，第三位出场的歌手就只有5种可能......以此类推，一共有7×6×5×4×3×2×1=5040种出场顺序。
对于同一个事件，将其分为n个步骤，每个步骤分别有m1,m2,m3,...,mn种可能，那么这一事件总共就有m1×m2×m3×...×mn种可能。这就是【分步乘法原则】。
作业：1.若某手机的开机密码共有6位数，则该密码一共有多少种可能？2.六位数的正整数一共有多少个？
解答：
第一题：10^6=1000000（一百万）；
第二题：9×10×10×10×10×10=900000（九十万）。
二、分类加法原则
现有2只金毛，3只萨摩耶和4只阿拉斯加，任选其中一只狗作为宠物，共有多少种可能？
将本题分为三类情况，第一类情况是选金毛（2种可能），第二类情况是选萨摩耶（3种可能），第三类情况是选阿拉斯加（4种可能）。因此，共有2+3+4=9种可能。
这个解答过程看似理所当然，实际上却反映了另一个重要的基本原则，即“分类加法原则”——将同一个事件分为n类情况，每类情况分别有m1,m2,...,mn种可能，那么这一事件总共就有m1+m2+...+mn种可能。
需要强调的是：这两个原理非常重要，以下所有内容都以此为基础。
三、阶乘
阶乘用数学符号“!”（感叹号）表示。规定0!=1，对于正整数n，n!=1×2×3×...×n。
四、排列数与组合数
排列数用字母A（Arrangement）和两个角标表示，读作“A,n,m”（详见下图）。规定n为正整数，m为自然数，且n≥m。由于不方便输入角标，以下我就用A(n,m)表示。
排列数
它的含义是指：在n个【互不相同的】元素中，任取其中m个元素【有顺序地】进行排列。
比如，第一期中的问题“7位歌手总共有多少种出场顺序”，就可以表示为A(7,7)=7!=5040。现在将本题稍微变化一下：7位歌手只需要其中任意6位出场（有1位歌手不用出场），总共有多少种顺序？这时就可以表示为A(7,6)=5040。
作业：1.若某手机的开机密码共有6位各不相同的数，则该密码一共有多少种可能？
2.每位数各不相同的六位数共有多少个？
解答：
第一题：A(10,6)=151200；
第二题：9×9×8×7×6×5=136080。
组合数用字母C（Combination）和两个角标表示，读作“C,n,m”（详见下图）。规定n为正整数，m为自然数，且n≥m。由于不方便输入角标，以下我就用C(n,m)表示。
排列数
它的含义是指在n个【互不相同的】元素中，任取其中m个元素【无顺序地】进行组合。
作业：某女生寝室共有6人，假设她们中至少3人才能创建一个QQ群，问该寝室最多会有几个QQ群？（提示：要用分类加法原则）
解答：C(6,3)+C(6,4)+C(6,5)+C(6,6)=20+15+6+1=42。
请大家多多留意本题！下面我会用【二项式定理】再给出一种的解法。
五、消序法
在排列数和组合数的定义中，我强调了是“n个互不相同的元素”。但实际应用中经常会出现含有相同元素的情况，这时就要用【消序法】。
比如，b、e、e三个字母共有几种排序？
首先，将b、e、e看作是3个不同的元素，就有A(3,3)=6种排序。由于我们假设了两个e是不同的元素，因此将它们两进行排序，就有A(2,2)=2种可能。最后，设实际的排序共有x种可能，根据分步乘法原则，2x=6，即x=3。这3种排序分别是bee、ebe和eeb。
因为两个e是完全相同的元素，所以排序时显然不能直接用A(3,3)，而必须通过上述的【消序法】修改计算公式，才能得到正确的结果。
作业：afternoon这9个字母共有几种排序？
解答：A(9,9)÷[A(2,2)×A(2,2)]=90720。
六、练习巩固
1.英语考试中某阅读题共有5道单选题（每题4个选项），请问恰好蒙对4道题的概率是多少？
2.英语考试中某阅读题共有5道单选题（每题4个选项），请问恰好蒙对前4道题的概率是多少？
3.英语考试中某道多选题共有4个选项，请问蒙对该题的概率是多少？.
4.英语考试中某排序题共有5题，但选项共有7个，请问全蒙对的概率是多少？
解答：
第一题：首先，蒙对一道题的概率为1/4，蒙错一道题的概率为3/4。在这5道题中任选其中4道，共有C(5,4)=5种情况，因此答案为5×(1/4)×(1/4)×(1/4)×(1/4)×(3/4)=15/1024。
第二题：它与第一题的不同之处在于——要求蒙对的是前4道题。也就是说，问题给定了具体的元素，不需要再在这5道题中进行选择了。答案为(1/4)×(1/4)×(1/4)×(1/4)×(3/4)=3/1024。
第三题：与女生寝室那道题相似。分为3类情况——正确答案有2个选项；有3个选项；有4个选项。因此，总共有C(4,2)+C(4,3)+C(4,4)=6+4+1=11种组合，答案为1/11。
第四题：共有A(7,5)=2520种排序，答案为1/2520。
七、二项式定理与杨辉三角
首先，我们来研究一下如何计算(a+b)²的展开式。
第一步，让两个(a+b)的a相乘，共有C(2,2)=1种组合，得a²。第二步，让其中一个(a+b)的a与另一个(a+b)的b相乘，这时对a就有C(2,1)=2种选择。并且一旦选定了某个a，另一个b也就确定了，因此共有2种选择，得2ab。最后，让两个(a+b)的b相乘，也有C(2,2)=1种组合，得b²。综上，(a+b)²=a²+2ab+b²。
同理，可以计算出(a+b)³的展开式，详见下图。
以此类推，可得(a+b)∧n(n为正整数)的展开式，这就是【二项式定理】。
从n=0开始，依次将二项式定理中的所有系数列出，就可以得到【杨辉三角】。
它最早由我国的北宋数学家贾宪（生卒年不详）发现，后来被南宋数学家杨辉（生卒年不详）引用，并流传至今。在欧洲，它最早由法国科学家帕斯卡（1623-1662，同时也是压强的单位）发现，但比我国晚了数百年。
令a=b=1，可得一个重要公式，详见下图。
因此，对于这道习题：某女生寝室共有6人，假设她们中至少3人才能建一个QQ群，问这个寝室最多能有几个QQ群？就有一个更快捷的计算方法！
解答：C(6,3)+C(6,4)+C(6,5)+C(6,6)=2∧6-C(6,0)-C(6,1)-C(6,2)=64-1-6-15=42。
八、二项分布与超几何分布
本节将简要介绍排列组合在概率统计中的应用。
我们来回顾一下这道习题：英语考试中某阅读题共有5道单选题（每题4个选项），请问恰好蒙对4道的概率是多少？
我们有理由将“蒙5道题”看作“5次独立重复的试验”。因为每蒙一道题对蒙对（或蒙错）下一题的概率没有任何影响，所以这5次重复试验是相互独立的。这样的过程就是【独立重复试验】。
类似地，对于抛n次硬币，因为每抛一次硬币对下一次抛硬币是正面（或反面）的概率没有任何影响，所以抛n次硬币就是n次独立重复试验。
如果随机变量X表示n次独立重复试验中某事件(比如蒙对一道题、硬币反面向上)发生的次数，那么X服从【二项分布】。
现有5个白球和5个红球在黑箱中，不放回地依次抽取。不难发现，第一次抽到红球的概率和第二次抽到红球的概率就不一样，这不再是独立重复试验。此时，随机变量X就服从【超几何分布】。
以上就是（(排列组合)专题汇总）全部内容，收藏起来下次访问不迷路！
