排列组合与概率原理及解题技巧70603.doc

自用解题方法技巧集 1 排列组合与概率原理及解题技巧一、基础知识 1. 加法原理: 做一件事有 n 类办法, 在第 1 类办法中有 m 1 种不同的方法, 在第 2 类办法中有 m 2种不同的方法, ……,在第 n 类办法中有 m n 种不同的方法,那么完成这件事一共有 N=m 1 +m 2+…+m n 种不同的方法。 2. 乘法原理: 做一件事, 完成它需要分 n 个步骤,第1 步有 m 1 种不同的方法,第2 步有 m 2 种不同的方法,……,第 n步有 m n 种不同的方法,那么完成这件事共有 N=m 1×m 2 ×…× m n 种不同的方法。 3 .排列与排列数:从 n 个不同元素中,任取 m(m ≤ n) 个元素,按照一定顺序排成一列,叫做从 n 个不同元素中取出 m 个元素的一个排列,从 n 个不同元素中取出 m个(m≤ n) 元素的所有排列个数,叫做从 n 个不同元素中取出 m 个元素的排列数,用 mnA 表示, mnA =n(n-1) …(n-m+1)= )!( !mn n?, 其中 m,n ∈ N,m ≤ n, 注:一般地 0nA =1,0! =1, nnA =n! 。 个不同元素的圆周排列数为 n A nn =(n-1)! 。 5 .组合与组合数:一般地,从 n 个不同元素中,任取 m(m ≤n) 个元素并成一组,叫做从 n 个不同元素中取出 m 个元素的一个组合,即从 n 个不同元素中不计顺序地取出 m 个构成原集合的一个子集。从n 个不同元素中取出 m(m ≤ n) 个元素的所有组合的个数,叫做从 n 个不同元素中取出 m 个元素的组合数,用 mnC 表示: . )!(! !! )1()1(mnm nm mnnnC mn??????? 6 .组合数的基本性质:(1) mnn ??;(2) 11 ???? nn mn ;(3) kn k n??? 11;(4) n nk kn 2 0 10????????;(5) 111 ????????? kmk kmk kk ?;(6) knmn mk ???。 7 .定理 1 :不定方程 x 1 +x 2+…+x n =r 的正整数解的个数为 11 ?? nrC 。[ 证明]将r 个相同的小球装入 n 个不同的盒子的装法构成的集合为 A, 不定方程 x 1+x 2+…+x n =r 的正整数解构成的集合为 B,A 的每个装法对应 B 的唯一一个解, 因而构成映射, 不同的装法对应的解也不同,因此为单射。反之 B 中每一个解(x 1 ,x 2,…,x n ),将x i 作为第 i 个盒子中球的个数, i=1,2, …,n,便得到 A 的一个装法,因此为满射,所以是一一映射,将 r 个小球从左到右排成一列,每种装法相当于从 r-1 个空格中选 n-1 个,将球分 n 份,共有 11 ?? nrC 种。故定理得证。推论 1 不定方程 x 1 +x 2+…+x n =r 的非负整数解的个数为. 1 rrnC ??自用解题方法技巧集 2 推论 2从n 个不同元素中任取 m 个允许元素重复出现的组合叫做 n 个不同元素的 m 可重组合,其组合数为. 1 mmnC ??8. 二项式定理:若n∈N +,则(a+b) n= nnn rrnrn nn nn nnbCbaCbaCbaCaC????