2013届高中数学竞赛教案讲义（13）排列组合与概率

第十三章 排列组合与概率一、基础知识1．加法原理：做一件事有 n 类办法，在第 1 类办法中有 m1种不同的方法，在第 2 类办法中有 m2种不同的方法，……，在第 n 类办法中有 mn种不同的方法，那么完成这件事一共有 N=m1+m2+…+mn种不同的方法2 乘法原理：做一件事，完成它需要分 n 个步骤，第 1 步有 m1种不同的方法，第 2 步有 m2种不同的方法，……，第 n 步有 mn种不同的方法，那么完成这件事共有 N=m1×m2×…×mn种不同的方法。3．排列与排列数：从 n 个不同元素中，任取 m(m≤n)个元素，按照一定顺序排成一列，叫做从 n个不同元素中取出 m 个元素的一个排列，从 n 个不同元素中取出 m 个(m≤n)元素的所有排列个数，叫做从 n 个不同元素中取出 m 个元素的排列数，用表示，=n(n-1)…(n-m+1)=,其中 m,n∈N,m≤n,注：一般地=1，0！=1，=n!。4．N 个不同元素的圆周排列数为=(n-1)!。5．组合与组合数：一般地，从 n 个不同元素中，任取 m(m≤n)个元素并成一组，叫做从 n 个不同元素中取出 m 个元素的一个组合，即从 n 个不同元素中不计顺序地取出 m 个构成原集合的一个子集。从 n 个不同元素中取出 m(m≤n)个元素的所有组合的个数，叫做从 n 个不同元素中取出 m个元素的组合数，用表示：6．组合数的基本性质：（1）；（2）；（3）；（4）；（5）；（6）。17．定理 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．二项式定理：若 n∈N+,则(a+b)n=.其中第 r+1 项 Tr+1=叫二项式系数。9．随机事件：在一定条件下可能发生也可能不发生的事件叫随机事件。在大量重复进行同一试验时，事件 A 发生的频率总是接近于某个常数，在...