排列组合及概率统计基础

►►►第10讲排列组合及概率统计基础129第10讲排列组合及概率统计基础考纲解析排列组合及概率论部分的内容是比较重要的，因为它很容易和别的部分的知识结合起来，例如条件概率或一些概率分布很容易运用在可靠性计算及图、路径和一些相应的算法问题上，所以在复习中一定要灵活掌握，从原理出发，活学活用，能够根据例题将知识运用到别的方面上。资源链接本讲对应CIU视频资源：概率论及数理统计.jbl。本讲内容10.1排列组合基础10.1.1排列的基本概念及实例从n个不同的元素中，任取m(m≤n)个元素（被取元素各不相同）按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列。如果元素和顺序至少有一个不同。则叫做不同的排列。元素和顺序都相同的排列则叫做相同的排列。排列数的计算公式为)1()2)(1(mnnnnAmn（其中m≤n，m，nZ）。1100..11（1）7位同学站成一排，共有多少种不同的排法？解：问题可以看作7个元素的全排列——77A=5040。（2）7位同学站成两排（前3后4），共有多少种不同的排法？解：根据分步计数原理7×6×5×4×3×2×1=7！=5040。（3）7位同学站成一排，其中甲站在中间的位置，共有多少种不同的排法？解：问题可以看作余下的6个元素的全排列——66A=720。（4）7位同学站成一排，甲、乙只能站在两端的排法共有多少种？解：根据分步计数原理，第一步，甲、乙站在两端有22A种；第二步，余下的5名同学进行全排列有55A种，则共有22A55A=240种排列方法。（5）7位同学站成一排，甲、乙不能站在排头和排尾的排法共有多少种？这类问题在各种考试中出现得都比较多，关键在于熟练，同时要注意审题，题意是可能设置陷阱的地方。对于这类问题，要掌握常用的方法，对于“在”与“不在”的问题，常常直接使用“直接法”或“排除法”，对特殊元素可优先考虑。软件设计师应试教程◄◄◄130解法一（直接法）：第一步，从（除去甲、乙）其余的5位同学中选2位同学站在排头和排尾有25A种方法；第二步，从余下的5位同学中选5位进行排列（全排列）有55A种方法，所以一共有22A55A=2400种排列方法。解法二：（排除法）若甲站在排头有66A种方法；若乙站在排尾有66A种方法；若甲站在排头，且乙站在排尾则有55A种方法。所以甲不能站在排头，乙不能排在排尾的排法共有77A－662A＋55A=2400种。1100..227位同学站成一排。（1）甲、乙两同学必须相邻的排法共有多少种？解：先将甲、乙两位同学“捆绑”在一起看成一个元素与其余的5个元素（同学）一起进行全排列有66A种方法；再将甲、乙两个同学“松绑”进行排列有22A种方法。所以这样的排法一共有66A22A=1440种。（2）甲、乙和丙三个同学都相邻的排法共有多少种？解：方法同上，一共有55A33A=720种。（3）甲、乙两同学必须相邻，而且丙不能站在排头和排尾的排法有多少种？解法一：将甲、乙两同学“捆绑”在一起看成一个元素，此时一共有6个元素，因为丙不能站在排头和排尾，所以可以从其余的5个元素中选取2个元素放在排头和排尾，有25A种方法；将剩下的4个元素进行全排列有44A种方法；最后将甲、乙两个同学“松绑”进行排列有22A种方法。所以这样的排法一共有25A44A22A=960种方法。解法二：将甲、乙两同学“捆绑”在一起看成一个元素，此时一共有6个元素，若丙站在排头或排尾有255A种方法，所以丙不能站在排头和排尾的排法有960)2(225566AAA种方法。解法三：将甲、乙两同学“捆绑”在一起看成一个元素，此时一共有6个元素，因为丙不能站在排头和排尾，所以可以从其余的四个位置选择共有14A种方法，再将其余的5个元素进行全排列共有55A种方法，最后将甲、乙两同学“松绑”，所以这样的排法一共有14A55A22A=960种方法。10.1.2组合的基本概念及实例一般地，从n个不同元素中取出m（m≤n）个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合。从n个不同元素中取出m（m≤n）个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。用符号mnC表示。组合数的计算公式为：!)1()2)(1(mmnnnnAACmmmnmn或!)(!!mnmnCmn（n，mN*，且m≤n）组合数还具有下面的性质：mnnmnCC。一般地，从n个不同元素中取出m个元素后，剩下nm个元素。因为从n个不同元素中取出m个元素的每一个组合，与剩下的nm个元素的每一个组合一一对应，所以从n个不同元素中取出m个元素的组合数，等于从这n个元素中取出nm个元素的组合数，即：mnnmnCC。在这里，主要体现：“取法”与“剩法”是“一一对应”的思想。对于相邻问题，常采用“捆绑法”，即先绑后松，关键在于怎么选择绑定的对象。►►►第10讲排列组合及概率统计基础131注：1．规定10nC。2．等式特点：等式两边下标同，上标之和等于下标。3．此性质作用：当2nm时，计算mnC可变为计算mnnC，能够使运算简化。例如：20012002C=200120022002C=12002C=2002。4．ynxnCCyx或nyx。1100..33一个口袋内装有大小相同的7个白球和1个黑球。（1）从口袋内取出3个球，共有多少种取法？（2）从口袋内取出3个球，使其中含有1个黑球，有多少种取法？（3）从口袋内取出3个球，使其中不含黑球，有多少种取法？解：（1）5638C（2）2127C（3）3537C可发现：38C27C37C。因为从口袋内的8个球中所取出的3个球，可以分为两类：一类含有1个黑球，一类不含有黑球。因此根据分类计数原理，上述等式成立。一般地，从121,,,naaa这n+1个不同元素中取出m个元素的组合数是mnC1，这些组合可以分为两类：一类含有元素a1，一类不含有a1。含有a1的组合是从132,,,naaa这n个元素中取出m1个元素与a1组成的，共有1mnC个；不含有a1的组合是从132,,,naaa这n个元素中取出m个元素组成的，共有mnC个。1100..446本不同的书，按下列要求各有多少种不同的选法。（1）分给甲、乙和丙三人，每人两本；（2）分为三份，每份两本；（3）分为三份，一份一本，一份两本，一份三本；（4）分给甲、乙和丙三人，一人一本，一人两本，一人三本；（5）分给甲、乙和丙三人，每人至少一本。解：（1）根据分步计数原理得到90222426CCC种。（2）分给甲、乙和丙三人，每人两本有222426CCC种方法。这个过程可以分两步完成：第一步分为三份，每份两本，设有x种方法；第二步再将这三份分给甲、乙和丙三名同学有33A种方法。根据分步计数原理可得：33222426xCCCC，所以1533222426ACCCx。因此分为三份，每份两本一共有15种方法。（3）这是“不均匀分组”问题，一共有60332516CCC种方法。（4）在（3）的基础上再进行全排列，所以一共有36033332516ACCC种方法。（5）可以分为三类情况：①“2、2、2型”即（1）中的分配情况，有90222426CCC种方法；②“1、2、3型”即（4）中的分配情况，有36033332516ACCC种方法；③“1、1、4型”，有903346AC种方法。所以一共有90+360+90=540种方法。注意利用组合数的这些性质，在使用中往往可以起到简化计算的效果。组合问题的关键在于分类，怎样对情况进行划分。注意这里的不均匀分组和全排列的问题。软件设计师应试教程◄◄◄13210.2概率论及应用数理统计基础概率论作为一门数学分支，它所研究的内容一般包括随机事件的概率、统计独立性和更深层次上的规律性。概率是随机事件发生的可能性的数量指标。在独立随机事件中，如果某一事件在全部事件中出现的频率，在更大的范围内比较明显的稳定在某一固定常数附近。就可以认为这个事件发生的概率为这个常数。任何事件的概率值一定介于0和1之间。有一类随机事件，它具有两个特点：第一，只有有限个可能的结果；第二，各个结果发生的可能性相同。具有这两个特点的随机现象叫做“古典概型”。在客观世界中，存在大量的随机现象，其产生的结果构成了随机事件。如果用变量来描述随机现象的各个结果，就叫做随机变量。随机变量分为有限和无限，一般又根据变量的取值情况分成离散型随机变量和非离散型随机变量。一切可能的取值能够按一定次序一一列举，这样的随机变量叫做离散型随机变量；如果可能的取值充满了一个区间，无法按次序一一列举，这种随机变量就叫做非离散型随机变量。在离散型随机变量的概率分布中，比较简单而应用广泛的是二项式分布。如果随机变量是连续的，那么它有一个分布曲线，实践和理论都证明：有一种特殊而常用的分布，其分布曲线是有规律的，这就是正态分布。正态分布曲线取决于这个随机变量的一些表征数，其中最重要的是平均值和差异度。平均值也叫数学期望，差异度也叫标准方差。10.2.1古典概率所谓事件A的概率是指事件A发生可能性程度的数值度量，记为P(A)。规定P(A)≥0，P(Ω)=1。满足下列两条件的试验模型称为古典概型：（1）所有基本事件是有限个；（2）各基本事件发生的可能性相同。在古典概型中，设其样本空间Ω所含的样本点总数，即试验的基本事件总数为N，而事件A所含的样本数，即有利于事件A发生的基本事件数为NA，则事件A的概率便定义为：基本事件总数包含基本事件数ANNAPA)(。1100..55（取球问题）袋中有5个白球，3个黑球，分别按下列三种取法在袋中取球。（1）有放回地取球：从袋中取三次球，每次取一个，看后放回袋中，再取下一个球。（2）无放回地取球：从袋中取三次球，每次取一个，看后不再放回袋中，再取下一个球。（3）一次取球：从袋中任取3个球。在以上取法中均求A={恰好取得2个白球}的概率。解：（1）有放回取球N=8×8×8=83=512（袋中八个球，不论什么颜色，取到每个球的概率相等）22535233552312AN（先从三个球里取两个白球，第一次取白球有5种情况，第二次取白球还有五种情况注意是有放回，第三次取黑球只有三种情况），44.0512225NNAPA。（2）无放回取球N=876=38A=336，18023345231325AANA，故54.0336180NNAPA。（3）一次取球5631518138AN，301325AN，要理解概率的意义，所谓概率就是某一事件发生的可能性相对于所有的可能性来说所占的比值。古典概率围绕事件进行，注意样本空间的概念，所谓样本空间就是所有的可能性，而样本点就是某一种可能性。注意取球问题是一个非常典型的应用，关键就是要把握是否有放回。►►►第10讲排列组合及概率统计基础133故。54.05630381325NNAPA古典概率具有下面的性质。若AB，则P(B-A)=P(B)-P(A)。即差的概率等于概率之差。若AB，则P(A)≤P(B)。即概率的单调性。P(A)≤1，对任意事件A，P(A)=1-P(A)。对任意事件A，B，有P(AUB)=P(A)+P(B)-P(AB)。1100..66设A，B，C为三个事件，已知P(A)=P(B)=P(C)=0.25，P(AB)=0，P(AC)=0，P(BC)=0.125，求A，B，C至少有一个发生的概率。解：由于ABCAB，故0≤P(ABC)≤P(AB)=0，从而P(ABC)=0。所求概率为P(ABC)=P(A)+P(B)+P(C)P(AB)P(AC)P(BC)+P(ABC)850810041414110.2.2条件概率在实际问题中，常常需要计算在某个事件B已发生的条