第十章概率与统计初步§10.1排列与组合.doc

第十章概率与统计初步 有一个人生了病，到一位医生那里去就诊医生检查后，与病人进行了如下的对话： “你生的病可谓九死一生啊！” “啊?!” “幸好你到我这里来就诊！” “喔！” “在你之前我已经看了九个这种病例，” “大夫经验丰富” “可是他们都死了，” “.!” “你是第十个，因此一定看得好” 要你是那位病人的话，你肯定不会相信那位医生的胡诌，拔脚开溜了电视上几乎天天有交通事故伤亡的报道，那些罹难者除了极个别者外，不会自己去送死，但是不幸还是降临到了他们的头上因此你每次上街都在冒伤亡的风险，但是你不会因此就不上街吧？ 第一个笑话中的那位病人，如果真的留下来请医生治疗，也不见得必死无疑，或许真的给医生治好了；第二个调侃中的你，也不见得每次外出必定安全返回，或许真有那么一次直奔急诊室去了因为这两个事件有一个公共特点：都带有不确定的因素，发生或是不发生是随机的，差别仅在于这种随机事件发生的可能性有多大笑话中的那位病人，估计继续治疗是凶多吉少，治愈的可能性太小了，因此开溜为上；第二则调侃中的你，预计出车祸的可能性微乎其微，因此不必每次上街都抱着英勇赴难的决心这种预计、估计的依据是生活经验 有没有可能把随机事件发生的可能性数字化，提出一个明确的大小呢？如何把随机事件发生的可能性数字化，才是科学可信的呢？这就是你在本章中所要学习的内容概率与统计10.1排列与组合重点排列与组合的概念选排列数公式和全排列数公式组合数公式难点区分排列与组合组合数的性质排列与组合在实际中的应用学习要求能准确区分排列与组合掌握排列数、组合数计算公式在实际中能准确区分不太复杂的排列于组合问题初步会应用组合数的性质，解决一些计算或证明问题 接着上面的话题，你之所以每次上街不担心出车祸，是因为你知道出车祸的可能性极小，所谓极小，从数量上分析，无非是上街几万次、甚至几十万次，才可能会发生一次不测事件如果上街十次就会发生一次车祸，你每次上街就得非常小心了；如果上街百次会发生一次车祸，你会定心一些；上街千次会发生一次车祸，你会更定心一些；现在是几万甚至几十万，所以你就笃定无忧“十次”“百次”“千次”.，实际上是一个计数问题要从数量上分析随机事件发生的可能性，必须首先要对发生的事件计数因此我们首先学习计数的有关知识 你可能会觉得好笑，计数这么一个老古董，原始人就知道结绳记事；还没有上小学，我就会数数；对已经掌握了许多代数、几何知识的我，还得炒这碗“冷饭”？且慢得意，你马上就会发现，就是在你身边发生的、日常生活中的一些计数问题，你未必能顺利解决 1. 排列 (1)选排列 选排列和选排列数 先来看一个简单的实例在1,2,3三个数码中，取出二个组成一个二位数，可以组成几个不同的二位数？你立即能给出答案：12,13; 21,23; 31,32，共6个；稍为复杂一些，数码增加为1,2,3,4四个，还是难不倒你：12,13,14; 21,23,24; 31,32,34; 41,42,43，共12个；问题再变一下：在四个数码1,2,3,4中，选取三个组成一个三位数，能组成几个不同的三位数？你可能要多花一点时间，但还是能得到答案： 123, 124, 132, 134, 142, 143；213, 214, 231, 234, 241, 243； 312, 314, 321, 324, 341, 342；412, 413, 421, 423, 431, 432共24个把问题改成下面这样，你恐怕要失去找答案的勇气了：在9个数码1,2,3,4,5,6,7,8,9中，选取7个数码组成一个7位数，能组成多少个不同的数？你失去勇气的原因，可能不是不会，而是怕繁，因为你已经预计到，把所有可能的7位数写出来再计个数，将是一个庞大的数字 其实我们只是要你回答可以组成多少个7位数，并没有说要你写出所有的7位数，再去统计个数能不写出具体的7位数，直接得到所要求的个数吗？ 设7位数的总个数是7位数中的第一位，可以在19中任挑一个，共有9种可能的选择；对第一位的每一种选择，后面的6位数，将在余下的8个数码中选取6个组成，这样的6位数总个数是；因此7位数的个数是=9；类比分析，同样又有=8，是在7个数码中选5个组成5位数的个数；依此类推，得到 =9=98=987=.=987.4是最后余下的三个数码中选一个组成一位数的个数，当然仅有3个于是最终得到 =9876543=181440 抽象上面的实例，可以提出这样的问题：在n个不同的元素中，选取其中的k个(kn)，按选取的顺序组成一列，共有几种不同的结果？称这样的问题为n个元素选k个的选排列问题；每一种选取的结果称为一个排列；所有不同结果的个数，称为选排列数，记作 选排列问题就是求注意，之所以称为选排列，一则是“选”：k个元素是从n个元素中选出来的，二则“排”：选取的元素即使相同，但选取的顺序不同，应该认为是两个不同的结果也就是说，一个选排列，除了选哪些元素之外，还有一个选出元素的排列问题 这种选排列问题，在生活实际中随处可见 例1 把下列问题归结为选排列问题： (1)北京、上海、广州、重庆四地间的直航飞机票，需要有多少种？ (2)年底，10位同学互寄贺卡，共寄多少张？ (3)30位学生组成的班级中，选正、副班长、生活委员、文体委员、学习委员各一人，组成班委，有多少种不同的组成方法？ 解 (1)四地是四个不同的元素；每张机票要选取两个元素(地方)；从甲地飞往乙地与从乙地飞往甲地，是两种不同的机票，因此与选取元素的排列顺序有关，因此是4选2的选排列需要机票种数为 (2)10位同学是10个元素；一份贺卡是两个同学之间的行为，因此一份贺卡要选两个元素(同学)；甲寄给乙与乙寄给甲是两份不同的贺卡，因此与选取元素的排列顺序有关，因此是10选2的选排列需要贺卡数为 (3)30位学生是30个不同的元素；班委由5人组成，因此是30选5；选出的5人，各人担任不同的职务，是不同的组成方法，因此与排列顺序有关，因此是30选5的选排列所以组成方法的个数是 课内练习11. 把下列问题归结为选排列问题： (1)铁路沿线有20个车站，需准备多少种车票？ (2)16支球队举行比赛，采用主客场循环比赛制，即每个球队必须与其余 球队在主客场各比赛一次，共需比赛多少场？ (3)10个人互写一封信，共要写多少封信？ (4)10个人中选正副组长各一名，共有多少种选法？ (5)由19可组成多少个没有重复数字的四位数？ 选排列数计算公式 n个元素选k个的选排列数，可以完全仿照实例的(1)那样分析出来：第一个元素有n种选取方法；余下的是n-1个元素选取k-1个的选排列数，所以 =n；依此类推，得：=n(n-1)=n(n-1)(n-2)=.最后得到 = n(n-1)(n-2). n-(k-1) (10-1-1) 在具体计算时，当连乘的项数较多，即使用计算器计算，也是很不方便的因此把公式(10-1-2)改写一下： =，引进一个运算记号： n!=n(n-1)(n-2).321，称为n的阶乘；当n=0，规定0!=1于是(10-1-2)可以写成 = (10-1-2)因为计算器有计算n!的功能键，把选排列数的公式写成(10-1-2)后，可以应用计算器计算但是阶乘运算的增加速度是非常快的，一般的10位计算器可以以十进制表示13!的结果，14!或更大的数的阶乘，只得以科学记数法表示，从而给的计算带来误差因此14以上的阶乘应当用电脑计算 例2 对例1各题求出结果 解 (1)机票数=4(4-1)=12 (2)贺卡数=10(10-1)=90 (3)班委组成数=30(30-1)(30-2)(30-3)(30-4)=17100720 例3 计算(1) ；(2) ；(3) 解 (1)=5!=54321=120 (2)=0 (3)=65 例4 若(1)=30；(2)=56n，求n 解 (1)=n(n-1)=n2-n=30，即n2-n-30=0，或 (n-6)(n+5)=0，得n=6或n=-5，舍去负根，得n=6 (2) =n(n-1)=n2-n=56n，即n2-57n=0，或 n(n-57)=0，得n=57或n=0，舍去零根，得n=57 例5 证明：(1)=(n-k+1)；(2) 证明 (1)右= =左 (2)左=右 课内练习21. 算出课内练习1第1题各小题的结果2. 计算(1)；(2)；(3)；(4)3. 已知(1)；(2)，求n (2)全排列 我们来分析例5第(2)小题 根据记号的含义，刻板地诠释，它表示n个不同元素中选n个的选排列但一共只有n个元素，你就取n个排列，还谈得上什么选？那不就是全部参加排列吗？因此对不能再理解为选排列，我们称它是n个元素的全排列的排列数；也就是说，称n个不同元素的一种排序方式，为一个全排列；全部可能排列方式的总数，为全排列数，记作同时它的计算公式也含在例5第(2)小题中了： =n!=n(n-1)(n-2).321 (10-1-3) 全排列问题，在实际中也屡见不鲜 例6 信号弹有红、绿、黄三种颜色，如果向天空连发3枪表示一个信号如果规定连续发射的三枪必须是不同的颜色，那么共能表示多少种不同的信号？如果允许有相同的颜色呢？ 解 三种颜色是三个不同的元素 如果规定连续发射的三枪必须是不同的颜色，那么是三个元素的全排列，因此可以表达信号数 =3!=321=6； 若允许有相同的颜色，那情况要复杂得多了： 总信号数=三色信号数+二色信号数+单色信号数， 三色信号数=6；单色信号数=3(三红或三绿或三黄) 对二色信号数，重复的颜色有有三种不同的选择，例如红色重复的信号有：红红绿，红绿红，绿红红；绿改黄同样有三种，所以二色信号数为332=18种 合之，总信号数=6+3+18=27 本例允许有相同元素的情况，称为有重复的全排列，即参加排列的元素允许有相同、甚至全部相同可以证明，n个元素有重复的全排列数=nn，本例中n=3,所以排列数=33=27当然对选排列也可以考虑有元素重复的方式，情况就更复杂了我们在后文中将会有简单的介绍 例7 以所有26个英文字符组成一个26位的密码，规定在一个密码中不出现相同的字符，那么可以组成多少种不同的密码？以单台计算机去解密，若计算机解密的速度是每秒种能检查107个不同的密码，那么最坏的情况下，需要多少时间才能解密？ 解 26个英文字符是26个不同的元素，一个密码是26个元素的一个全排列，总计密码数是26的全排列数，所以 组成的密码数=26!4.03291026 计算机解密的最坏情况，是直到最后一个才检查到设置的密码，此时耗时T为 T=4.03291026107=4.03291019(s)1.1202541016 (h)1.27881012(年)，即约12788.3亿年 你可以想像一下，如果密码中的字符还允许重复，这将是一个何等巨大的数字！在高科技飞速发展的现代，如何设置不易被破译的密码，已经成为一门专门学科密码学，有些密码长达40位，但还有人竟然能予以破译，你不得不佩服这些高手课内练习31. 写出字母a,b,c的全排列2. 填表：n45678910n!3. 古代兵营以白天挂彩旗、黑夜挂彩灯的方式传递信息，现有若使用7面 不同颜色的彩旗或7只不同的颜色的彩灯，从上至下挂成一列来表达要传 递的信息，那么可以表示多少种不同的信息？4. (1)7人排队，甲必须站在正中间有多少种排法？ (2)7人排队，甲、乙必须站头尾有多少种排法？5. 6位同学站一列，要求甲必须在乙前面，共有多少种排法？6. 证明n=(n+1)!-n! 2. 组合 (1)组合的概念 我们还从一个简单的问题谈起从甲、乙、丙三人中选2人做代表，显然只有甲与乙、乙与丙、丙与甲，共3种方法；同样地，从甲,乙,丙,丁4人中选两人做代表，有：甲乙,甲丙,甲丁,乙丙,乙丁,丙丁，共有6种方法 与选排列问题比较，这类问题也有一个从全部元素中选取部分元素的问题，但排列问题与选取顺序有关，例如甲、乙、丙三人中选2人做代表，先选出者为首席代表，则先选甲、后选乙和先选乙后选甲是不同的组成；现在的情况却与选取顺序无关，只要选出两人组成代表团，无首席、一般之分因此这是有别于选排列问题的另一类选取方案个数问题，我们称之为组合问题具体来说，从n个不同的元素中取出k(kn)个元素并成一组，称为从n个不同元素中取出k个元素的一个组合；组合的总数称为组合数，记作 例8 把下面的问题归结为排列或组合问题： (1)在人数为50人的班级中，选举正、副班长、学习委员、生活委员和文体委员各一人，组成班委，求可能的组成方案数 (2)在人数为50人的班级中，选举五人组成班委，然后在班委内部分工，确定正、副班长、学习委员、生活委员和文体委员，求可能的组成方案数 (3)由20人组成的足球队中，除守门员外，还需选10人作为首发阵容，求可组成多少个不同的首发阵容又在50名啦啦队员中要挑选20人前往助阵，有几种挑选方案？ (4)10份内容相同的信函，发给20个人中的10人，每人一份，有几种发信的方案？ 解 (1)50位学生中选出5人；因不同分工是班委的不同组成方案，因此与顺序有关，所以组成班委的方案数为 (2)50位学生中选出5人；因为选出班委后再分工，所以与选取顺序无关，所以组成班委的方案数为 (3)去掉守门员，19位球员中选10人出阵；因为10人担当后卫、前锋等角色不同，是不同的组成方案，因此与选取顺序有关，所以可组成的首发阵容数为；选助阵啦啦队员无顺序问题，故挑选方案数为 (4)因为信函只有10封，人数有20人，因此只能从中挑选10人发予信函；因信函内容相同，故与选取顺序无关，所以发信的方案数为 课内练习41. 把下面的问题能归结为排列或组合问题吗？如果能，请写出排列数或组 合数的记号，如果不能，请说明理由： (1)在人数为60人的班级中，分成各30名学生的两个助残公益活动小组， 可以有多少种分法？ (2)有一个由6人组成的全能乐队，每人都能玩6种乐器要挑选5名队 员参加某次演出，可以组建多少种不同的演出阵容？ (3)6个朋友互相握手道别，共握手多少次？ (4)5道习题任意选做3题，有多少不同的选法？ (5)10支球队进行循环赛，共需安排多少场比赛？ (6)某种饮料是混合四种原料配制而成现在每种原料都有9种不同品牌 可供选择，共有几种选择原料的方案？ (7)一个正16边形，能连成几条对角线？ (2)组合数的计算公式组合数的计算与排列数的计算有紧密联系还是从一个简单的例子看起你已经知道，在数码19中取k个(k9)组成k位数的个数=；在19中取k个(k9)组成含有k个数码的数集，则数集的个数是 与的差别在哪里呢？k个数码组成数集，只与数码本身有关，与这k个数码的次序无关；但是同一个数集中的k个数码，按不同次序排列，却是不同的k位数，k个数码可以组成=k!个不同的k位数，那就是说，每一个数集，在将对应于中k!个排列，因此是的k!倍，即 =，= 同理，在一般情况下，中由k个元素组成的每一个组合，可以有个不同的排列，因此 =，=以=k!, =代入，得到 = (10-1-4)这就是组合数的计算公式 例9 计算例8中属于组合问题的各题的组合数 解 例8(2)组成班委的方案数为 =2118760； 例8(3)助阵啦啦队员挑选方案数为 =4.71013； 例8(4)发信的方案数为 =184756； 例10 据下面的等式，求出n或k： (1) ；(2) 解 (1)，两式相等，有 =1，解得n=8 (2)，两式相等，有 ，解得k=4 例11求证 证明 右边=(k+1)= =(n-k)=左边你也可以试试从等式左边证到右边 课内练习51. 把课内练习4中，属于组合问题的组合数计算出来2. 写出从a, b, c, d四个字母中取两个字母的可能组合3. 计算，4. 计算+5. 据下面的等式，求出n或k： (1)；(2)6. 证明：(1) =；(2)+=7. 证明：(1) ； (2) (3)组合数的两个重要性质 在上述一些形式不同的组合数相等的结论中，有两个特别有用的等式，我们把它们单独列出来 对偶原则 在课内练习5的第6题(1)中，你曾经证明计算过从组合数的含义来看，这个等式可以得到一个简单的解释：从10个元素中选出7个元素的组合数，与从10个元素中选留3个元素的组合数当然是相等的 在一般情况下也是如此：从n个元素中选取k个元素的组合数，与从n个元素中选留n-k个元素的组合数是相等的因此有等式 (10-1-5)把“选出”改为“选留”，是一种意义相反的对偶，因此可以把(10-1-5)称为对偶原则 在n个元素中取n个的组合数，当然仅有一种，因此=1；用(10-1-5)，其中的k=n，即有=1按照的含义，表示在n个元素中一个元素也不取的组合数，既然什么也不取，还侈谈什么组合数？因此本来是没有意义的，但是我们仍然规定=1，这样(10-1-5)对kn都成立这就像0!=1一样，是一个数学上的规定，这种规定既合乎逻辑，又方便 增一原则 在课内练习5的第6题(2)，你曾经证明+=，这个等式的特点是同一个n=9、k从2增1成为k=3的组合数之和，与n增1、k增1的组合数相等这不是一种巧合，从组合数的含义来看，也能得到简单的解释例如，在0,1,.,9这10个数码中取3个、构成含有3个数码的数集的组合数，等于不含数码0的数集个数m1与含数码0的数集个数m2之和；前者是在1,.,9中选取3个，构成3个数码的数集的组合数，即m1=；后者中的每个数集，是0与1,.,9中选取2个构成，可能选取方法有个，即m2=，所以=m1+m2=+把数码换成一般的元素，数集换成一般的组合，数码0换成其它实际含义的另类元素，道理完全是一样的 把这个浅显的道理，推广到一般的情况，就得到组合数的第二个重要性质： (10-1-6)这个公式的左边是n不变，k增加1；右边则是n, k都增加1，因此可以形象地称它为增一原则课内练习71. 有100件礼品，其中有一件礼品是一只手表允许你挑选其中的9件礼 品以手表作为另类礼品，请从你可选9件礼品的方案数，分析出等式 2. 你的班级有50位同学，现在要选出6位组成班委，组成的方案数是试 从你入选班委和你未入选班委两种情况，分析组成的可能方案数，得出结 论 (4)组合数性质在计算中的应用 从组合数计算公式(10-1-4)可以看出，当n稍大、且k又与n比较接近时，的分子分母各有k项相乘，计算起来是很繁的但此时n-k却比较小了，公式(10-1-5)告诉我们是一样的，你可以以计算来得到，而计算，分子分母各只有n-k项相乘，计算起来要简单得多这就是公式(10-1-5)之重要性所在 例12 求下列组合数： (1) ；(2