13第十三章排列组合与概率【讲义】(数学试题竞赛模拟)

1、第十三章排列组合与概率一、基础知识1加法原理：做一件事有 n 类办法，在第 1类办法中有 m 种不同的方法，在第2 类办法中有 m 种不同的12方法， ，在第 n 类办法中有 mn 种不同的方法，那么完成这件事一共有N=m1+m2+ +mn 种不同的方法。2乘法原理：做一件事，完成它需要分n 个步骤，第 1 步有 m1 种不同的方法， 第 2 步有 m 种不同的方法， ，2第 n 步有 m 种不同的方法，那么完成这件事共有N=mm m 种不同的方法。n12n3排列与排列数：从 n 个不同元素中，任取m(mn) 个元素，按照一定顺序排成一列，叫做从n 个不同元素中取出 m个元素的一个排列，从n

2、个不同元素中取出m个(mn) 元素的所有排列个数，叫做从n 个不同元素中取出 m个元素的排列数，用Anm 表示， Anm =n(n-1) (n-m+1)=n!, 其中 m,nN,m n,(nm)!注：一般地 An0 =1，0！=1， Ann =n! 。4 N 个不同元素的圆周排列数为Ann=(n-1)!。n5组合与组合数：一般地，从n 个不同元素中，任取m(m n) 个元素并成一组，叫做从 n 个不同元素中取出 m个元素的一个组合，即从n 个不同元素中不计顺序地取出m个构成原集合的一个子集。从n 个不同元素中取出 m(m n) 个元素的所有组合的个数，叫做从n 个不同元素中取出m个元素的组合数

3、，用Cnm 表示：C nmn( n 1)( nm 1)n!.m!m!(nm)!6 组合数的基本性质：（ 1 ） CnmCnnm ；（ 2） Cnm1n01nk2n （； 5） kkC nC nC nC nCkCk 1k 0CnmCnn 1 ；（ 3 ） n C nk11C nk ；（ 4 ）kCkkm Ckkm11 （； 6）Cnk CkmCnn mk 。7定理 1：不定方程 x1+x2 + +xn=r 的正整数解的个数为 Crn11 。 证明 将 r 个相同的小球装入 n 个不同的盒子的装法构成的集合为A，不定方程 x1 +x2 + +xn=r 的正整数解构成的集合为 B，A 的每个装法对应

4、 B 的唯一一个解，因而构成映射，不同的装法对应的解也不同，因此为单射。反之 B 中每一个解 (x 1,x 2 , ,x n), 将 xi 作为第 i个盒子中球的个数， i=1,2,n ，便得到 A 的一个装法，因此为满射， 所以是一一映射， 将 r 个小球从左到右排成一列，每种装法相当于从 r-1 个空格中选 n-1个，将球分 n 份，共有 Crn11 种。故定理得证。推论 1不定方程 x1 +x2 + +xn =r 的非负整数解的个数为Cnrr 1.推论 2从 n 个不同元素中任取 m个允许元素重复出现的组合叫做n 个不同元素的 m可重组合，其组合数为 Cnm m 1 .8二项式定理：若n

5、 N+, 则(a+b) n= Cn0 a nCn1a n 1b Cn2 an 2b2Cnr a n r brCnn bn . 其rn rrr中第 r+1 项 Tr+1 = Cn ab , Cn 叫二项式系数。9随机事件：在一定条件下可能发生也可能不发生的事件叫随机事件。在大量重复进行同一试验时，事件A 发生的频率m 总是接近于某个常数，在它附近摆动，这个常数叫做事件A 发生的概率，记作p(A),0 np(A) 1.10. 等可能事件的概率， 如果一次试验中共有 n 种等可能出现的结果， 其中事件 A 包含的结果有 m种，那么事件 A 的概率为 p(A)= m .n11. 互斥事件：不可能同时发

6、生的两个事件，叫做互斥事件，也叫不相容事件。如果事件A1，A2 ， ， An 彼此互斥，那么A1， A2 ， ， An 中至少有一个发生的概率为p(A 1+A2+An)= p(A1)+p(A2)+p(An ).12对立事件：事件A，B 为互斥事件，且必有一个发生，则A，B 叫对立事件，记A 的对立事件为A 。由定义知 p(A)+p(A )=1.13相互独立事件：事件A（或 B）是否发生对事件B（或 A）发生的概率没有影响，这样的两个事件叫做相互独立事件。14相互独立事件同时发生的概率：两个相互独立事件同时发生的概率，等于每个事件发生的概率的积。即p(A?B)=p(A) ?p(B).若事件A1

7、，A2 ， ， An 相互独立, 那么这n 个事件同时发生的概率为p(A1 ?A2 ?An)=p(A 1 ) ?p(A 2 ) ?p(A n ).15. 独立重复试验: 若 n 次重复试验中, 每次试验结果的概率都不依赖于其他各次试验的结果, 则称这n 次试验是独立的.16. 独立重复试验的概率 : 如果在一次试验中, 某事件发生的概率为p, 那么在 n 次独立重复试验中 , 这个事件恰好发生 k 次的概率为 pn(k)= Cnk ?pk (1-p)n-k .17离散型随机为量的分布列： 如果随机试验的结果可以用一个变量来表示， 那么这样的变量叫随机变量，例如一次射击命中的环数 就是一个随机变

8、量， 可以取的值有 0,1,2, ,10 。如果随机变量的可能取值可以一一列出，这样的随机变量叫离散型随机变量。一般地，设离散型随机变量 可能取的值为 x1 ,x 2 , ,x i, , 取每一个值 x i (i=1,2,) 的概率 p( =xi )=p i ，则称表x 1x2x3xipp1p2p3pi为随机变量 的概率分布，简称 的分布列，称E =x1 p1 +x2 p2 +xnpn+ 为 的数学期望或平均值、均值、简称期望，称 D =(x 1 -E )2 ?p1 +(x 2-E )2 ?p2 + +(x n -E )2p n+ 为 的均方差，简称方差。D 叫随机变量 的标准差。18二项分布

9、：如果在一次试验中某事件发生的概率是p，那么在 n 次独立重复试验中，这个事件恰好发生 k 次的概率为 p( =k)= Cnk p k qn k , 的分布列为01x iNpCn0 p0 qnCn1 p1 q n 1Cnk pk q n kCnn pn此时称 服从二项分布，记作 B(n,p).若 B(n,p) ，则 E=np,D =npq, 以上 q=1-p.19. 几何分布： 在独立重复试验中，某事件第一次发生时所做试验的次数也是一个随机变量，若在一次试验中该事件发生的概率为p ，则p( =k)=q k-1 p(k=1,2,) ， 的分布服从几何分布，E =1， Dp=q (q=1-p).p

10、 2二、方法与例题1乘法原理。例 1有 2n 个人参加收发电报培训，每两个人结为一对互发互收，有多少种不同的结对方式？ 解 将整个结对过程分n 步，第一步，考虑其中任意一个人的配对者，有2n-1种选则；这一对结好后，再从余下的2n-2人中任意确定一个。第二步考虑他的配对者，有2n-3种选择， 这样一直进行下去，经 n 步恰好结n 对，由乘法原理，不同的结对方式有(2n-1) (2n-3) 31=(2n)!n2(n!).2加法原理。例 2图 13-1 所示中没有电流通过电流表，其原因仅因为电阻断路的可能性共有几种？解 断路共分 4 类：1）一个电阻断路，有 1 种可能，只能是R4 ；2）有 2

11、个电阻断路，有 C42 -1=5 种可能； 3） 3 个电阻断路，有C43=4 种； 4）有 4 个电阻断路，有1 种。从而一共有 1+5+4+1=11 种可能。3插空法。例 3 10 个节目中有 6 个演唱 4 个舞蹈，要求每两个舞蹈之间至少安排一个演唱，有多少种不同的安排节目演出顺序的方式？ 解 先将 6个演唱节目任意排成一列有A66种排法，再从演唱节目之间和前后一共7 个位置中选出 4 个安排舞蹈有 A74种方法，故共有 A66A74=604800 种方式。4映射法。例 4如果从 1，2， ， 14 中，按从小到大的顺序取出a1 ,a 2,a 3 使同时满足： a2 -a 1 3,a 3

12、 -a 2 3，那么所有符合要求的不同取法有多少种？ 解 设 S=1,2,14， S =1， 2 ， ， 10 ； T=(a 1 ,a 2 ,a 3)|a1 ,a 2 ,a 3 S,a 2 -a 1 3,a 3-a 2 3,T =(a1 ,a2, a3) S| a1 , a2 , a3S, a1a2a3,若 ( a1 , a2 , a3 ) T ， 令a1a1 , a2a22,a3a34，则(a 1,a2 ,a 3) T, 这样就建立了从T 到 T 的映射， 它显然是单射，其次若 (a 1,a 2 ,a3) T, 令 a1a1, a2a22, a3a34 ，则 (a1, a2 ,a3 )T ，

13、从而此映射也是满射，因此是一一映射，所以|T|= | T |C103=120，所以不同取法有120种。5贡献法。例 5已知集合 A=1， 2，3， ， 10 ，求 A 的所有非空子集的元素个数之和。 解 设所求的和为 x ，因为 A 的每个元素 a，含 a 的 A 的子集有 29 个，所以 a 对 x 的贡献为29 ，又|A|=10 。所以 x=1029 . 另解A 的 k元 子 集 共 有 C10k个 ， k=1,2,10，因此，A的子集的元素个数之和为C1012C10210C101010(C90C91C99 )102 。96容斥原理。例 6由数字 1，2，3 组成 n 位数 (n 3) ，

14、且在 n 位数中， 1，2，3 每一个至少出现1 次，问：这样的 n 位数有多少个？ 解 用 I表示由 1， 2， 3 组成的 n 位数集合，则 |I|=3n ，用 A1，A2 ，A3 分别表示不含 1，不含 2，不含 3的由 1，2，3 组成的 n 位数的集合， 则 |A 1 |=|A2 |=|A 3 |=2 n ，|A 1A2 |=|A 2A3 |=|A 1A3|=1 。|A 1A2A3 |=0 。3| Ai| AiAj| |A1A2A3|=3 2n-3.所以由容斥原理 |A 1A2A3 |=所以满足条件i1ij的 n 位数有 |I|-|A 1A2A3|=3 n-3 2n+3 个。7递推方

15、法。例 7用 1，2，3 三个数字来构造n 位数，但不允许有两个紧挨着的1 出现在 n 位数中，问：能构造出多少个这样的 n 位数？ 解 设能构造 an 个符合要求的 n 位数，则 a1=3，由乘法原理知 a2=3 3-1=8. 当 n 3 时： 1）如果 n 位数的第一个数字是 2 或 3，那么这样的 n 位数有 2an-1 ；2）如果 n 位数的第一个数字是1，那么第二位只能是2 或 3，这样的 n 位数有 2an-2 ，所以 an =2(a n-1+an-2 )(n 3). 这里数列 a n 的特征方程为x2=2x+2，它的两根为x1 =1+3 ,x 2 =1- 3 , 故 an =c1

16、(1+3 ) n + c 2(1+ 3 ) n , 由 a1 =3,a 2 =8 得 c123, c232，所2323以 an1 (13) n 2(13) n2 .438算两次。例 8 m,n,rN+，证明： C nrmCn0CmrCn1 Cmr 1Cn2 Cmr 2Cnr Cm0 .证明从 n 位太太与 m位先生中选出 r位的方法有 Cnrm 种；另一方面，从这n+m人中选出 k 位太太与r-k 位 先 生 的 方 法 有 Cnk Cmrk种 ， k=0,1,r。所以从这n+m 人 中 选 出 r位的方法有Cn0 CmrCn1Cmr 1Cnr Cm0 种。综合两个方面，即得式。9母函数。例

17、9一副三色牌共有32 张，红、黄、蓝各10 张，编号为1， 2， ， 10，另有大、小王各一张，编号均为 0。从这副牌中任取若干张牌，按如下规则计算分值：每张编号为k 的牌计为2k 分，若它们的分值之和为 2004 ，则称这些牌为一个“好牌”组，求好牌组的个数。 解 对于 n1,2,2004, 用 an表示分值之和为n的牌组的数目，则an 等于函数 f(x)=(1+x2 0)2?(1+ x 21)3 ? ?(1+ x 210)3 的展开式中xn 的系数（约定|x|1），由于 f(x)=1 (1+ x 20)(1+x 21)?1x?( 1+ x210)3 =1x) 3(1x 211) 3 =1(

18、1 x 211 ) 3。(1x)(1(1x 2 )(1x) 2而0 2004211， 所 以an等 于1的 展 开 式 中 x n 的 系 数 ， 又 由 于(1 x 2 )(1 x)21=1?1=(1+x 2 +x3+ +x2k+ )1+2x+3x 2+ +(2k+1)x 2k + , 所以 x2k 在展(1x2 )(1 x) 21x2(1x) 2开式中的系数为 a2k =1+3+5+(2k+1)=(k+1)2,k=1,2, 从而，所求的“好牌”组的个数为 a2004 =10032=1006009.10组合数 Cnk 的性质。例 10 证明： C2km 1 是奇数 (k 1).证明C2km

19、1 = (2 m1)(2m2) (2m1 k1) 2 m1 2m22mk令1 2k12ki= 2ti?pi(1 ik) ，pi 为奇数，则2mi2m 2tipi2m tipi，它的分子、分母均为奇数，i2t ipipik是整数，所以它只能是若干奇数的积，即为奇数。因 Cm12例 11对 n 2, 证明： 2 nC2nn4 n . 证明1 ） 当 n=2时 ， 2 C42 =64 ； 2 ） 假 设 n=k时 ，有 2 C2kk4k, 当 n=k+1 时 ，因 为22kC 2k( k11) 2( k 1)!2(2k1)!2(2k1)C2kk .(k1)! (k1)!(k 1)! k!k1又 22

20、(2k1) 4，所以 2k+1 2C2kkC2k(k11)4C2kk4 k1 .k1所以结论对一切n 2 成立。11二项式定理的应用。n例 12若 n N, n 2，求证： 2113.n1nCn1 111证明首 先1Cn0Cn2Cnn2,其次因为nnn 2nn1n(n 1)(nk1)11111nC nk(k2)， 所 以1nknkk!k! k (k 1)k 1 kn2+C n21C nn12111111313.得证。n 2nn1223n 1 nnnmhhm 1(hn).例 13m证明：C nkCkCn1k0证明首先，对于每个确定的k ，等式左边的每一项都是两个组合数的乘积，其中Cnm kh 是

21、 (1+x) n-k 的展开式中 xm-h 的系数。 Ckh 是(1+y)k的展开式中yk 的系数。从而 Cnm kh ?Ckh 就是 (1+x)n-k ?(1+y) k 的展开式中xm-hy h 的系数。nnmhh(1x)n k(1y)km-hh于是，C n kC k就是展开式中 xy的系数。k 0k 0n 1n1nx) nk (1y) k(1x)n 1(1y)n 1C nk1 xkC nk 1 y k另一方面，(1=k0xk0=k 0(1 x)(1y)yn 11xk ? xkykn 1Cnkx=C nk1 (x k-1+xk-2y+ +yk-1)，上式中， x m-hyh 项的系数恰为 C

22、nm11 。k 0yk 0nm hhm 1所以C n kC kC n 1 .k012概率问题的解法。例 14如果某批产品中有a 件次品和 b 件正品，采用有放回的抽样方式从中抽取n 件产品，问：恰好有k件是次品的概率是多少？ 解 把 k 件产品进行编号，有放回抽n 次，把可能的重复排列作为基本事件，总数为(a+b)n（即所有的可能结果）。设事件 A 表示取出的 n 件产品中恰好有k 件是次品，则事件 A 所包含的基本事件总数为Cnk ?akbn-k，故所求的概率为 p(A)=Cnk ak b nk(a b) n .例 15 将一枚硬币掷 5 次，正面朝上恰好一次的概率不为 0，而且与正面朝上恰

23、好两次的概率相同，求恰好三次正面朝上的概率。 解 设 每 次 抛 硬 币 正 面 朝 上 的 概 率 为 p ， 则 掷 5次 恰 好 有 k 次 正 面 朝 上 的 概 率 为C5k p k (1-p) 5-k(k=0,1,2, ,5)，由题设 C52 p 2 (1p) 3C51 p(1 p)4，且 0p1，化简得 p1，所以332恰好有 3 次正面朝上的概率为31240 .C533343例 16甲、乙两个乒乓球运动员进行乒乓球比赛，已知每一局甲胜的概率为0.6，乙胜的概率为0.4，比赛时可以用三局二胜或五局三胜制，问：在哪一种比赛制度下，甲获胜的可能性大？ 解 （1）如果采用三局两胜制，则

24、甲在下列两种情况下获胜：A 1 2：0（甲净胜二局）， A2 2： 1（前二局甲一胜一负，第三局甲胜）. p(A 1)=0. 6 0.6=0.36,p(A2)= C210.6 0.4 0.6=0.288.因为 A1 与 A2 互斥，所以甲胜概率为p(A1 +A2)=0.648.(2) 如果采用五局三胜制，则甲在下列三种情况下获胜：B1 3：0（甲净胜3 局），B2 3：1（前 3 局甲 2 胜1 负，第四局甲胜） ， B3 3：2（前四局各胜 2 局，第五局甲胜） 。因为 B1， B2，B2 互斥，所以甲胜概率为p(B 1+B2+B3)=p(B 1)+p(B 2)+p(B 3 )=0.6 3

25、+ C32 0.62 0.4 0.6+ C42 0.620.4 2 0.6=0.68256.由（ 1），（2）可知在五局三胜制下，甲获胜的可能性大。例 17有 A， B 两个口袋， A 袋中有 6 张卡片，其中1 张写有0，2 张写有 1， 3 张写有 2；B 袋中有 7 张卡片，其中 4 张写有 0，1 张写有 1， 2 张写有 2。从 A 袋中取出1 张卡片， B 袋中取 2 张卡片，共3 张卡片。求：（1）取出3 张卡片都写0 的概率；（2）取出的3 张卡片数字之积是4 的概率；（ 3）取出的3 张卡片数字之积的数学期望。 解 （1） pC11 C421C21 C22C31 C11 C2

26、14C61 C72；（2） pC61 C72；（3）记 为取出的 3 张卡2163片的数字之积，则 的分布为0248p3724142636342所以 E03722448132 .4263634263三、基础训练题1三边长均为整数且最大边长为11 的三角形有 _个。2在正 2006 边形中，当所有边均不平行的对角线的条数为_。3用 1，2，3， ， 9这九个数字可组成 _个数字不重复且8 和 9 不相邻的七位数。4 10 个人参加乒乓球赛，分五组，每组两个人有_种分组方法。5以长方体的顶点为顶点的三棱锥的个数是_。6今天是星期二，再过101000 天是星期 _。7由 (3x3 2)100展开式所

27、得的 x 的多项式中，系数为有理数的共有_项。8如果凸 n 边形 (n 4) 的任意三条对角线不共点，那么这些对角线在凸n 边形内共有 _个交点。9袋中有 a 个黑球与 b 个白球，随机地每次从中取出一球（不放回），第 k(1 k a+b) 次取到黑球的概率为_。10一个箱子里有9 张卡片，分别标号为1， 2， ， 9，从中任取2 张，其中至少有一个为奇数的概率是_。11某人拿着 5 把钥匙去开门，有 2 把能打开。他逐个试，试三次之内打开房门的概率是 _。12马路上有编号为 1， 2，3， ， 10 的十盏路灯，要将其中三盏关掉，但不能同时关掉相邻的两盏或三盏，也不能关掉两端的路灯，则满足条

28、件的关灯方法种数是 _。13 a,b,c,d,e五个人安排在一个圆桌周围就坐，若a,b不相邻有_种安排方式。14已知i,m,n是正整数，且1(1+n) m.15. 一项“过关游戏”规定：在第n 关要抛掷一颗骰子n 次，如果这n 次抛掷所得到的点数之和大于2n ，则算过关。问：（ 1）某人在这项游戏中最多能过几关？（2）他连过前三关的概率是多少？（注：骰子是一个在各面上分别有1， 2，3，4，5， 6 点数的均匀正方体）四、高考水平训练题1若n1,2,100且 n 是其各位数字和的倍数，则这种n 有_个。2从 -3,-2,-1,0,1,2,3,4中任取 3 个不同元素作为二次函数y=ax 2+b

29、x+c 的系数，能组成过原点，且顶点在第一或第三象限的抛物线有_条。3四面体的顶点和各棱的中点共10 个点，在其中任取 4 个不共面的点，有 _种取法。4三个人传球，从甲开始发球，每次接球后将球传给另外两人中的任意一个，经5 次传球后，球仍回到甲手中的传法有 _种。5一条铁路原有 m个车站（含起点，终点） ，新增加 n 个车站（ n1），客运车票相应地增加了58 种，原有车站有 _个。n6将二项式1的展开式按降幂排列，若前三项系数成等差数列，则该展开式中x 的幂指数xx24是整数的项有 _个。7从 1 到 9 这九个自然数中任取两个分别作为对数的真数和底数，共可得到_种不同的对数值。8二项式

30、(x-2)5 的展开式中系数最大的项为第 _项，系数最小的项为第 _项。9有一批规格相同的均匀圆棒，每根被划分成长度相同的5 节，每节用红、黄、蓝三色之一涂色，可以有_种颜色不同的圆棒？（颠倒后相同的算同一种）10在 1， 2， ， 2006中随机选取 3 个数，能构成递增等差数列的概率是_。11投掷一次骰子，出现点数1，2，3， ， 6 的概率均为1 ，连续掷 6 次，出现的点数之和为35 的概率6为_。12某列火车有n 节旅客车厢，进站后站台上有m(m n) 名旅客候车，每位旅客随意选择车厢上车，则每节车厢都有旅客上车的概率是_。13某地现有耕地10000 公顷，规划10 年后粮食单产比现

31、在增加22%，人均粮食占有量比现在提高10%，如果人口年增长率为1%，那么耕地平均每年至多只能减少多少公顷（精确到1 公顷）？（粮食单产总产量=）耕地面积五、联赛一试水平训练题1若 0abcd500，有 _ 个有序的四元数组（a,b,c,d）满足 a+d=b+c 且 bc-ad=93.2. 已知直线ax+by+c=0 中的a,b,c是取自集合-3,-2,-1,0,1,2,3中的3 个不同的元素，并且该直线倾斜角为锐角，这样的直线条数是_。3已知A=0， 1，2，3，4， 5， 6，7 ，映射f:AA 满足：（ 1）若i j ，则f(i)f(j)；（2）若i+j=7，则 f(i)+f(j)=7，这样的映射的个数为_。41，2，3，4，5 的排列a1,a 2,a 3 ,a 4,a 5 具有性质：对于1i 4,a 1,a 2,a i 不构成1，2， ， i的某个排列，这种排列的个数是_。5骰子的六个面标有1，2， ， 6 这六个数字，相邻两个面上的数字之差的绝对值叫变差，变差的总和叫全变差 V，则全变差V 的最大值为 _，最小值为 _。6某次乒乓球单打比赛中，原计划每两名选手恰比赛一场，但有 3 名选手各比赛2 场之后就退出了， 这样，全部比赛只进行50 场，上述三名选手之间比赛场数为_。7如果 a,b,c,d都属于 1,2,3,4且 ab,b c,c d, d a