高中数学竞赛教材讲义 第十三章 排列组合与概率讲义.pdf

《高中数学竞赛教材讲义 第十三章 排列组合与概率讲义.pdf》由会员分享，可在线阅读，更多相关《高中数学竞赛教材讲义 第十三章 排列组合与概率讲义.pdf（10页珍藏版）》请在三一文库上搜索。

1、第十三章 排列组合与概率 一、基础知识 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 个元素

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

3、有组合的个数，叫做从 n 个不同元素 中取出 m 个元素的组合数，用表示： m n C . )!( ! ! ! ) 1() 1( mnm n m mnnn C m n 6 组合数的基本性质 ： （1）； （2）； （3）； （4） mn n m n CC 1 1 n n m n m n CCC k n k n CC k n 1 1 ；（5）；（6） n n k k n n nnn CCCC2 0 10 1 11 k mk k mk k k k k CCCC 。 kn mn m k k n CCC 7定理 1：不定方程 x1+x2+xn=r 的正整数解的个数为。 1 1 n r C 证明将 r

4、个相同的小球装入 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 1 n r C 理得证。 推论 1 不定方程 x1+x2+xn=r 的非负整数解的个数为. 1 r rn C 推论2 从

5、n个不同元素中任取m个允许元素重复出现的组合叫做n个不同元素的m可重组合， 其组合数为. 1 m mn C 8二项式定理：若 nN+,则(a+b)n=. nn n rrnr n n n n n n n bCbaCbaCbaCaC 222110 其中第 r+1 项 Tr+1=叫二项式系数。 r n rrnr n CbaC, 9随机事件：在一定条件下可能发生也可能不发生的事件叫随机事件。在大量重复进行同一 试验时，事件 A 发生的频率总是接近于某个常数，在它附近摆动，这个常数叫做事件 A 发 n m 生的概率，记作 p(A),0p(A)1. 10.等可能事件的概率，如果一次试验中共有 n 种等可能

6、出现的结果，其中事件 A 包含的结果 有 m 种，那么事件 A 的概率为 p(A)=. n m 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.AA 13相互独立事件：事件 A（或 B）是否发生对事件 B（或 A）发生的概率没有影响，这样的 两个事件叫做相互独立事件。 14相互独立事件同时

7、发生的概率：两个相互独立事件同时发生的概率，等于每个事件发生 的概率的积。即 p(AB)=p(A)p(B).若事件 A1，A2，An相互独立,那么这 n 个事件同时发 生的概率为 p(A1A2 An)=p(A1)p(A2) p(An). 15.独立重复试验:若 n 次重复试验中,每次试验结果的概率都不依赖于其他各次试验的结果, 则称这 n 次试验是独立的. 16.独立重复试验的概率:如果在一次试验中,某事件发生的概率为p,那么在n次独立重复试验 中,这个事件恰好发生 k 次的概率为 pn(k)=pk(1-p)n-k. k n C 17离散型随机为量的分布列：如果随机试验的结果可以用一个变量来表

8、示，那么这样的变 量叫随机变量， 例如一次射击命中的环数就是一个随机变量， 可以取的值有 0,1,2,10。 如果随机变量的可能取值可以一一列出，这样的随机变量叫离散型随机变量。 一般地，设离散型随机变量可能取的值为 x1,x2,xi,取每一个值 xi(i=1,2,)的概 率 p(=xi)=pi，则称表 x1x2x3xi pp1p2p3pi 为随机变量的概率分布，简称的分布列，称 E=x1p1+x2p2+xnpn+为的数学期望或 平均值、均值、简称期望，称 D=(x1-E)2p1+(x2-E)2p2+(xn-E)2pn+为的均方 差，简称方差。叫随机变量的标准差。D 18二项分布：如果在一次试

9、验中某事件发生的概率是 p，那么在 n 次独立重复试验中，这个 事件恰好发生 k 次的概率为 p(=k)=, 的分布列为 knkk n qpC 01xiN p n n qpC 00111n n qpC knkk n qpC nn n pC 此时称服从二项分布，记作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). p 1 2 p q 二、方法与例题

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

11、 种可能， 只能是 R4； 2） 有 2 个电阻断路， 有-1=5 2 4 C 种可能 ； 3）3 个电阻断路，有=4 种 ； 4）有 4 个电阻断路，有 1 种。从而一共有 1+5+4+1=11 3 4 C 种可能。 3插空法。 例 3 10 个节目中有 6 个演唱 4 个舞蹈，要求每两个舞蹈之间至少安排一个演唱，有多少种 不同的安排节目演出顺序的方式？ 解 先将 6 个演唱节目任意排成一列有种排法，再从演唱节目之间和前后一共 7 个位置 6 6 A 中选出 4 个安排舞蹈有种方法，故共有=604800 种方式。 4 7 A 4 7 6 6 AA 4映射法。 例 4 如果从 1， 2， 14

12、 中， 按从小到大的顺序取出 a1,a2,a3使同时满足 ： a2-a13,a3-a23， 那么所有符合要求的不同取法有多少种？ 解 设 S=1,2,14，=1，2，10； T=(a1,a2,a3)| a1,a2,a3S,a2-a13,a3-a2 S 3,=(),若，令T 3 2 1 ,aaa 3 2 1 3 2 1 , ,| aaaSaaaS),( 3 2 1 Taaa ，则(a1,a2,a3)T,这样就建立了从到 T 的映射，它显然4, 2, 33 22 11 aaaaaaT 是单射，其次若(a1,a2,a3)T,令，则，从4, 2, 33 22 11 aaaaaa),( 3 2 1 Ta

13、aa 而此映射也是满射，因此是一一映射，所以|T|=120，所以不同取法有 120 种。 3 10 | |CT 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 的子集的元素个数之和为 k C10 1029。)(10102 9 9 1 9 0 9 10 10 2 10 1 10 CCCCCC 6容斥原理。 例 6 由数字 1，2，3

14、组成 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|=|A1 A3|=1。|A1A2A3|=0。 所以由容斥原理|A1A2A3|=32n-3.所以满足| 321 3 1 AAAAAA ji ji i i 条件的 n 位数有|I|-|A1A2A3|=3n-32n+3 个。 7递推方法。 例 7

15、 用 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,由3333 a

16、1=3,a2=8 得，所以 32 23 , 32 32 21 cc.)31 ()31( 34 1 22 nn n a 8算两次。 例 8 m,n,rN N+，证明： . 022110 m r n r mn r mn r mn r CCCCCCCCC mn 证明 从 n 位太太与 m 位先生中选出 r 位的方法有种 ； 另一方面， 从这 n+m 人中选出 k r mn C 位太太与 r-k 位先生的方法有种，k=0,1,r。所以从这 n+m 人中选出 r 位的方法有 kr m k nC C 种。综合两个方面，即得式。 0110 m r n r mn r mn CCCCCC 9母函数。 例 9 一

17、副三色牌共有 32 张，红、黄、蓝各 10 张，编号为 1，2，10，另有大、小王各 一张， 编号均为 0。 从这副牌中任取若干张牌， 按如下规则计算分值 ： 每张编号为 k 的牌计为 2k 分，若它们的分值之和为 2004，则称这些牌为一个“好牌”组，求好牌组的个数。 解 对于n1,2,2004,用an表示分值之和为n的牌组的数目， 则an等于函数f(x)=(1+ )2(1+)3(1+)3的展开式中 xn的系数（约定|x|(1+n)m. i n ii m i AmAn 15.一项“过关游戏”规定：在第 n 关要抛掷一颗骰子 n 次，如果这 n 次抛掷所得到的点数之 和大于 2n，则算过关。问

18、：（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 次传球后， 球仍回到甲手中的传法有

19、_种。 5一条铁路原有 m 个车站（含起点，终点） ，新增加 n 个车站（n1） ，客运车票相应地增加 了 58 种，原有车站有_个。 6 将二项式的展开式按降幂排列， 若前三项系数成等差数列， 则该展开式中 x n x x 4 2 1 的幂指数是整数的项有_个。 7从 1 到 9 这九个自然数中任取两个分别作为对数的真数和底数，共可得到_种不 同的对数值。 8 二项式(x-2)5的展开式中系数最大的项为第_项， 系数最小的项为第_项。 9有一批规格相同的均匀圆棒，每根被划分成长度相同的 5 节，每节用红、黄、蓝三色之一 涂色，可以有_种颜色不同的圆棒？（颠倒后相同的算同一种） 10在 1，2

20、，2006 中随机选取 3 个数，能构成递增等差数列的概率是_。 11投掷一次骰子，出现点数 1，2，3，6 的概率均为，连续掷 6 次，出现的点数之和 6 1 为 35 的概率为_。 12某列火车有 n 节旅客车厢，进站后站台上有 m(mn)名旅客候车，每位旅客随意选择车厢 上车，则每节车厢都有旅客上车的概率是_。 13某地现有耕地 10000 公顷，规划 10 年后粮食单产比现在增加 22%，人均粮食占有量比现 在提高 10%，如果人口年增长率为 1%，那么耕地平均每年至多只能减少多少公顷（精确到 1 公顷）？（粮食单产=） 耕地面积 总产量 五、联赛一试水平训练题 1若 01 为固定的正整数 ； （3） 存在 h0,1h0 k-1，使得m+1. 00 1hh jj 4.设,其中 S1，S2，Sm都是正整数且 S1S2Sm，求证组合数 m SSS n222 21 中奇数的个数等于 2m。 n nnn CCC, 11 5个不同的数随机排成图 13-2 所示的三角形阵，设 Mk是从上往下第 k 行中的最大 2 ) 1( nn 数，求 M1M2Mn的概率。 6证明：. 1 1 1 1 1 r n rn k r kn CkC