第十三章排列组合与概率(高中数学竞赛标准教材)

1 / 18第十三章排列组合与概率(高中数学竞赛标准教材)本资料为 WoRD 文档，请点击下载地址下载全文下载地址 第十三章排列组合与概率一、基础知识1加法原理：做一件事有 n 类办法，在第 1 类办法中有m1 种不同的方法，在第 2 类办法中有 m2 种不同的方法，在第 n 类办法中有 mn 种不同的方法，那么完成这件事一共有 N=m1+m2+mn 种不同的方法。2乘法原理：做一件事，完成它需要分 n 个步骤，第 1步有 m1 种不同的方法，第 2 步有 m2 种不同的方法，第 n 步有 mn 种不同的方法，那么完成这件事共有N=m1m2mn 种不同的方法。3排列与排列数：从 n 个不同元素中，任取 m(mn)个元素，按照一定顺序排成一列，叫做从 n 个不同元素中取出 m 个元素的一个排列，从 n 个不同元素中取出 m 个(mn)元素的所有排列个数，叫做从 n 个不同元素中取出 m 个元素的排列数，用表示，=n(n-1)(n-m+1)=,其中 m,nN,mn,注：一般地=1，0！=1，=n!。4N 个不同元素的圆周排列数为=(n-1)!。5组合与组合数：一般地，从 n 个不同元素中，任取m(mn)个元素并成一组，叫做从 n 个不同元素中取出 m 个2 / 18元素的一个组合，即从 n 个不同元素中不计顺序地取出 m个构成原集合的一个子集。从 n 个不同元素中取出 m(mn)个元素的所有组合的个数，叫做从 n 个不同元素中取出 m个元素的组合数，用表示：6组合数的基本性质：（1） ；（2） ；（3） ；（4） ；（5） ；（6） 。7定理 1：不定方程 x1+x2+xn=r 的正整数解的个数为。证明将 r 个相同的小球装入 n 个不同的盒子的装法构成的集合为 A，不定方程 x1+x2+xn=r 的正整数解构成的集合为 B，A 的每个装法对应 B 的唯一一个解，因而构成映射，不同的装法对应的解也不同，因此为单射。反之 B 中每一个解(x1,x2,xn),将 xi 作为第 i 个盒子中球的个数，i=1,2,n，便得到 A 的一个装法，因此为满射，所以是一一映射，将 r 个小球从左到右排成一列，每种装法相当于从 r-1 个空格中选 n-1 个，将球分 n 份，共有种。故定理得证。推论 1 不定方程 x1+x2+xn=r 的非负整数解的个数为推论 2 从 n 个不同元素中任取 m 个允许元素重复出现的组合叫做 n 个不同元素的 m 可重组合，其组合数为8二项式定理：若 nN+,则(a+b)n=.其中第 r+1 项3 / 18Tr+1=叫二项式系数。9随机事件：在一定条件下可能发生也可能不发生的事件叫随机事件。在大量重复进行同一试验时，事件 A 发生的频率总是接近于某个常数，在它附近摆动，这个常数叫做事件 A 发生的概率，记作 p(A),0p(A)1.10.等可能事件的概率，如果一次试验中共有 n 种等可能出现的结果，其中事件 A 包含的结果有 m 种，那么事件 A的概率为 p(A)=11.互斥事件：不可能同时发生的两个事件，叫做互斥事件，也叫不相容事件。如果事件 A1，A2，An 彼此互斥，那么 A1，A2，An 中至少有一个发生的概率为p(A1+A2+An)=p(A1)+p(A2)+p(An).12对立事件：事件 A，B 为互斥事件，且必有一个发生，则 A，B 叫对立事件，记 A 的对立事件为。由定义知 p(A)+p()=1.13相互独立事件：事件 A（或 B）是否发生对事件B（或 A）发生的概率没有影响，这样的两个事件叫做相互独立事件。14相互独立事件同时发生的概率：两个相互独立事件同时发生的概率，等于每个事件发生的概率的积。即p(Ap(B).若事件 A1，A2，An相互独立,那么这 n 个事件同时发生的概率为4 / 18p(A1p(A2)p(An).15.独立重复试验:若 n 次重复试验中,每次试验结果的概率都不依赖于其他各次试验的结果,则称这 n 次试验是独立的.16.独立重复试验的概率:如果在一次试验中,某事件发生的概率为 p,那么在 n 次独立重复试验中,这个事件恰好发生k 次的概率为 pn(k)=pk(1-p)n-k.17离散型随机为量的分布列：如果随机试验的结果可以用一个变量来表示，那么这样的变量叫随机变量，例如一次射击命中的环数 就是一个随机变量， 可以取的值有 0,1,2,10。如果随机变量的可能取值可以一一列出，这样的随机变量叫离散型随机变量。一般地，设离散型随机变量 可能取的值为x1,x2,xi, 取每一个值 xi(i=1,2,)的概率p(=xi)=pi，则称表x1x2x3xipp1p2p3pi为随机变量 的概率分布，简称 的分布列，称E=x1p1+x2p2+xnpn+为 的数学期望或平均值、均值、简称期望，称 D=(x1-E)2p1+(x2-E)2p2+(xn-E)2pn+为 的均方差，简称方差。5 / 18叫随机变量 的标准差。18二项分布：如果在一次试验中某事件发生的概率是p，那么在 n 次独立重复试验中，这个事件恰好发生 k 次的概率为 p(=k)=, 的分布列为01xiNp此时称 服从二项分布，记作 B(n,p).若B(n,p)，则 E=np,D=npq,以上 q=1-p.19.几何分布：在独立重复试验中，某事件第一次发生时所做试验的次数 也是一个随机变量，若在一次试验中该事件发生的概率为 p，则 p(=k)=qk-1p(k=1,2,)， 的分布服从几何分布，E=，D=(q=1-p).二、方法与例题1乘法原理。例 1 有 2n 个人参加收发电报培训，每两个人结为一对互发互收，有多少种不同的结对方式？解将整个结对过程分 n 步，第一步，考虑其中任意一个人的配对者，有 2n-1 种选则；这一对结好后，再从余下6 / 18的 2n-2 人中任意确定一个。第二步考虑他的配对者，有2n-3 种选择，这样一直进行下去，经 n 步恰好结 n 对，由乘法原理，不同的结对方式有(2n-1)(2n-3)31=2加法原理。例 2 图 13-1 所示中没有电流通过电流表，其原因仅因为电阻断路的可能性共有几种？解断路共分 4 类：1）一个电阻断路，有 1 种可能，只能是 R4；2）有 2 个电阻断路，有-1=5 种可能；3）3 个电阻断路，有=4 种；4）有 4 个电阻断路，有 1 种。从而一共有 1+5+4+1=11 种可能。3插空法。例 310 个节目中有 6 个演唱 4 个舞蹈，要求每两个舞蹈之间至少安排一个演唱，有多少种不同的安排节目演出顺序的方式？解先将 6 个演唱节目任意排成一列有种排法，再从演唱节目之间和前后一共 7 个位置中选出 4 个安排舞蹈有种方法，故共有=604800 种方式。4映射法。例 4 如果从 1，2，14 中，按从小到大的顺序取出a1,a2,a3 使同时满足：a2-a13,a3-a23，那么所有符合要求的不同取法有多少种？7 / 18解设 S=1,2,14，=1，2，10；T=(a1,a2,a3)|a1,a2,a3S,a2-a13,a3-a23,=(),若，令，则(a1,a2,a3)T,这样就建立了从到 T 的映射，它显然是单射，其次若(a1,a2,a3)T,令，则，从而此映射也是满射，因此是一一映射，所以|T|=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 元子集共有个，k=1,2,10，因此，A 的子集的元素个数之和为 1029。6容斥原理。例 6 由数字 1，2，3 组成 n 位数(n3)，且在 n 位数中，1，2，3 每一个至少出现 1 次，问：这样的 n 位数有多少个？解用 I 表示由 1，2，3 组成的 n 位数集合，则|I|=3n，用 A1，A2，A3 分别表示不含 1，不含 2，不含 3的由 1，2，3 组成的 n 位数的集合，则|A1|=|A2|=|A3|=2n，|A1A2|=|A2A3|=|A1A3|=1。|A1A2A3|8 / 18=0。所以由容斥原理|A1A2A3|=32n-3.所以满足条件的 n位数有|I|-|A1A2A3|=3n-32n+3 个。7递推方法。例 7 用 1，2，3 三个数字来构造 n 位数，但不允许有两个紧挨着的 1 出现在 n 位数中，问：能构造出多少个这样的 n 位数？解设能构造 an 个符合要求的 n 位数，则 a1=3，由乘法原理知 a2=33-1=8.当 n3 时：1）如果 n 位数的第一个数字是 2 或 3，那么这样的 n 位数有 2an-1；2）如果 n 位数的第一个数字是 1，那么第二位只能是 2 或 3，这样的 n位数有 2an-2，所以 an=2(an-1+an-2)(n3).这里数列an的特征方程为 x2=2x+2，它的两根为 x1=1+,x2=1-,故an=c1(1+)n+c2(1+)n,由 a1=3,a2=8 得，所以8算两次。例 8m,n,rN+，证明：证明从 n 位太太与 m 位先生中选出 r 位的方法有种；另一方面，从这 n+m 人中选出 k 位太太与 r-k 位先生的方法有种，k=0,1,r。所以从这 n+m 人中选出 r 位的方法有种。综合两个方面，即得式。9母函数。例 9 一副三色牌共有 32 张，红、黄、蓝各 10 张，编号9 / 18为 1，2，10，另有大、小王各一张，编号均为 0。从这副牌中任取若干张牌，按如下规则计算分值：每张编号为 k 的牌计为 2k 分，若它们的分值之和为 XX，则称这些牌为一个“好牌”组，求好牌组的个数。解对于 n1,2,XX,用 an 表示分值之和为 n 的牌组的数目，则 an 等于函数 f(x)=(1+)2(1+)3(1+)3 的展开式中 xn 的系数（约定|x|1） ，由于 f(x)=(1+)(1+)(1+)3=3=3。而 0XX211，所以 an 等于的展开式中 xn 的系数，又由于=(1+x2+x3+x2k+)1+2x+3x2+(2k+1)x2k+,所以 x2k 在展开式中的系数为 a2k=1+3+5+(2k+1)=(k+1)2,k=1,2,从而，所求的“好牌”组的个数为 aXX=10032=1006009.10组合数的性质。例 10 证明：是奇数(k1).证明=令 i=pi(1ik)，pi 为奇数，则，它的分子、分母均为奇数，因是整数，所以它只能是若干奇数的积，即为奇数。例 11 对 n2,证明：证明1）当 n=2 时，2242；2）假设 n=k 时，有 2k4k,当 n=k+1 时，因为10 / 18又.所以结论对一切 n2 成立。11二项式定理的应用。例 12 若 nN,n2，求证：证明首先其次因为，所以 2+得证。例 13 证明：证明首先，对于每个确定的 k，等式左边的每一项都是两个组合数的乘积，其中是(1+x)n-k 的展开式中 xm-h 的系数。是(1+y)k 的展开式中 yk 的系数。从而就是(1+x)n-k(1+y)k 的展开式中 xm-hyh 的系数。于是，就是展开式中 xm-hyh 的系数。另一方面，=(xk-1+xk-2y+yk-1)，上式中，xm-hyh 项的系数恰为。所以12概率问题的解法。例 14 如果某批产品中有 a 件次品和 b 件正品，采用有放回的抽样方式从中抽取 n 件产品，问：恰好有 k 件是次品的概率是多少？解把 k 件产品进行编号，有放回抽 n 次，把可能的重复排列作为基本事件，总数为(a+b)n（即所有的可能结果） 。设事件 A 表示取出的 n 件产品中恰好有 k 件是次品，则事件 A 所包含的基本事件总数为akbn-k，故所求的概11 / 18率为 p(A)=例 15 将一枚硬币掷 5 次，正面朝上恰好一次的概率不为0，而且与正面朝上恰好两次的概率相同，求恰好三次正面朝上的概率。解设每次抛硬币正面朝上的概率为 p，则掷 5 次恰好有k 次正面朝上的概率为(1-p)5-k(k=0,1,2,5)，由题设，且 01，化简得，所以恰好有 3 次正面朝上的概率为例 16 甲、乙两个乒乓球运动员进行乒乓球比赛，已知每一局甲胜的概率为，乙胜的概率为，比赛时可以用三局二胜或五局三胜制，问：在哪一种比赛制度下，甲获胜的可能性大？解（1）如果采用三局两胜制，则甲在下列两种情况下获胜：A12：0（甲净胜二局） ，A22：1（前二局甲一胜一负，第三局甲胜）.p(A1)=,p(A2)=因为 A1 与 A2 互斥，所以甲胜概率为 p(A1+A2)=(2)如果采用五局三胜制，则甲在下列三种情况下获胜：B13：0（甲净胜 3 局） ，B23：1（前 3 局甲 2 胜 1 负，第四局甲胜） ，B33：2（前四局各胜 2 局，第五局甲胜） 。因为 B1，B2，B2 互斥，所以甲胜概率为 p(B1+B2+B3)=p(B1)+p(B2)+p(B3)=+=由（1） ， （2）可知在五局三胜制下，甲获胜的可能性大。12 / 18例 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） ；（2） ；（3）记 为取出的 3 张卡片的数字之积，则 的分布为0248p所以三、基础训练题1三边长均为整数且最大边长为 11 的三角形有_个。2在正 XX 边形中，当所有边均不平行的对角线的条数为_。3用 1，2，3，9 这九个数字可组成_个数13 / 18字不重复且 8 和 9 不相邻的七位数。410 个人参加乒乓球赛，分五组，每组两个人有_种分组方法。5以长方体的顶点为顶点的三棱锥的个数是_。6今天是星期二，再过 101000 天是星期_。7由展开式所得的 x 的多项式中，系数为有理数的共有_项。8如果凸 n 边形(n4)的任意三条对角线不共点，那么这些对角线在凸 n 边形内共有_个交点。9袋中有 a 个黑球与 b 个白球，随机地每次从中取出一球（不放回） ，第 k(1ka+b)次取到黑球的概率为_。10一个箱子里有 9 张卡片，分别标号为 1，2，9，从中任取 2 张，其中至少有一个为奇数的概率是_。11某人拿着 5 把钥匙去开门，有 2 把能打开。他逐个试，试三次之内打开房门的概率是_。12马路上有编号为 1，2，3，10 的十盏路灯，要将其中三盏关掉，但不能同时关掉相邻的两盏或三盏，也不能关掉两端的路灯，则满足条件的关灯方法种数是_。14 / 1813a,b,c,d,e 五个人安排在一个圆桌周围就坐，若 a,b不相邻有_种安排方式。14已知 i,m,n 是正整数，且 1imn。证明：（1） ；（2）(1+m)n(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=ax2+bx+c 的系数，能组成过原点，且顶点在第一或第三象限的抛物线有_条。3四面体的顶点和各棱的中点共 10 个点，在其中任取4 个不共面的点，有_种取法。4三个人传球，从甲开始发球，每次接球后将球传给另外两人中的任意一个，经 5 次传球后，球仍回到甲手中的传法有_种。5一条铁路原有 m 个车站（含起点，终点） ，新增加 n个车站（n1） ，客运车票相应地增加了 58 种，原有车15 / 18站有_个。6将二项式的展开式按降幂排列，若前三项系数成等差数列，则该展开式中 x 的幂指数是整数的项有_个。7从 1 到 9 这九个自然数中任取两个分别作为对数的真数和底数，共可得到_种不同的对数值。8二项式(x-2)5 的展开式中系数最大的项为第_项，系数最小的项为第_项。9有一批规格相同的均匀圆棒，每根被划分成长度相同的 5 节，每节用红、黄、蓝三色之一涂色，可以有_种颜色不同的圆棒？（颠倒后相同的算同一种）10在 1，2，XX 中随机选取 3 个数，能构成递增等差数列的概率是_。11投掷一次骰子，出现点数 1，2，3，6 的概率均为，连续掷 6 次，出现的点数之和为 35 的概率为_。12某列火车有 n 节旅客车厢，进站后站台上有 m(mn)名旅客候车，每位旅客随意选择车厢上车，则每节车厢都有旅客上车的概率是_。13某地现有耕地 10000 公顷，规划 10 年后粮食单产比现在增加 22%，人均粮食占有量比现在提高 10%，如果人口年增长率为 1%，那么耕地平均每年至多只能减少多少公顷16 / 18（精确到 1 公顷）？（粮食单产=）五、联赛一试水平训练题1若 0500，有_个有序的四元数组（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）若 ij，则 f(i)f(j)；（2）若 i+j=7，则f(i)+f(j)=7，这样的映射的个数为_。41，2，3，4，5 的排列 a1,a2,a3,a4,a5 具有性质：对于 1i4,a1,a2,ai 不构成 1，2，i 的某个排列，这种排列的个数是_。5骰子的六个面标有 1，2，6 这六个数字，相邻两个面上的数字之差的绝对值叫变差，变差的总和叫全变差V，则全变差 V 的最大值为_，最小值为_。6某次乒乓球单打比赛中，原计划每两名选手恰比赛一场，但有 3 名选手各比赛 2 场之后就退出了，这样，全部比赛只进行 50 场，上述三名选手之间比赛场数为_。7如果 a,b,c,d 都属于1,2,3,4且17 / 18ab,bc,cd,da；且 a 是 a,b,c,d 中的最小值，则不同的四位数的个数为_。8如果自然数 a 各位数字之和