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

高中数学竞赛教材讲义 第十三章 排列组合与概率讲义
第十三章 排列组合与概率
一、基础知识
1．加法原理：做一件事有n 类办法，在第1类办法中有m 1种不同的方法，在第2类办法中有m 2种不同的方法，……，

高中数学竞赛教材讲义 第十三章 排列组合与概率讲义
第十三章 排列组合与概率
一、基础知识
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 个元素的排列数，用表示，=n(n-1)…(n-m+1)=m n A m
n A ,其中m,n ∈N,m ≤n,)!
(!m n n -注：一般地=1，0！=1，=n!。
0n A n


n A 4．N 个不同元素的圆周排列数为=(n-1)!。n A n n 5．组合与组合数：一般地，从n 个不同元素中，任取m(m ≤n)个元素并成一组，叫做从n 个不同元素中取出m 个元素的一个组合，即从n 个不同元素中不计顺序地取出m 个构成原集合的一个子集。从n 个不同元素中取出m(m ≤n)个元素的所有组合的个数，叫做从n 个不同元素中取出m 个元素的组合数，用表示：m n C .)!
(!!!)1()1(m n m n m m n n n C m n -=+--= 6．组合数的基本性质：（1）；（2）；（3）；（4）m n n
m n C C -=11--+=n n m n m n C C C k n k n C C k n =--11；（5）；（6）
n n k k n n n n n C C C C 20
10
==+++∑= 111++++-=+++k m k k m k k k k k C C C C 。
k n m n m k k n C C C --=7．定理1：不定方程x 1+x 2+…+x n =r 的正整数解的个数为。
1
1--n r C [证明]将r 个相同的小球装入n 个不同的盒子的装法构成的集合为A ，不定方程x 1+x 2+…+x n =r 的正整数解构成的集合为B ，A 的每个装法对应B 的唯一一个解