20192020年高中数学竞赛教材讲义第十三章排列组合与概率
一、基础知识1．加法原理：做一件事有
类办法，在第1类办法中有m1种不同的方法，在第2类办法中有m2种不同的方法，……，在第
类办法中有m
种不同的方法，那么完成这件事一共有Nm1m2…m
种不同的方法。2．乘法原理：做一件事，完成它需要分
个步骤，第1步有m1种不同的方法，第2步有m2种不同的方法，……，第
步有m
种不同的方法，那么完成这件事共有Nm1×m2×…×m
种不同的方法。3．排列与排列数：从
个不同元素中，任取mm≤
个元素，按照一定顺序排成一列，叫做从
个不同元素中取出m个元素的一个排列，从
个不同元素中取出m个m≤
元素的所有排列个数，叫做从
个不同元素中取出m个元素的排列数，用表示，
1…
m1其中m
∈Nm≤
注：一般地1，0！1，
。4．N个不同元素的圆周排列数为
1。5．组合与组合数：一般地，从
个不同元素中，任取mm≤
个元素并成一组，叫做从
个不同元素中取出m个元素的一个组合，即从
个不同元素中不计顺序地取出m个构成原集合的一个子集。从
个不同元素中取出mm≤
个元素的所有组合的个数，叫做从
个不同元素中取出m个元素的组合数，用表示：
C
m



1
m1m


m
m


6
．
组
合
数
的
基
本
性
质
：（
1
）；（
2
）；（
3
）；（
4
）
C
0


C
1




C



C
k2
；（5）
k0
C
kk

C
kk1



C
kkm

Ck1km1
；（6）。
7．定理1：不定方程x1x2…x
r的正整数解的个数为。证明将r个相同的小球装入
个不同的盒子的装法构成的集合为A，不定方程x1x2…x
r的正整数解构成的集合为B，A的每个装法对应B的唯一一个解，因而构成映射，不同的装法对应的解也不同，因此为单射。反之B中每一个解x1x2…x
将xi作为第i个盒子中球的个数，i12…
，便得到A的一个装法，因此为满射，所以是一一映射，将r个小球从左到右排成一列，每种装法相当于从r1个空格中选
1个，将球分
份，共有种。故定理得证。推论1不定方程x1x2…x
r的非负整数解的个数为推论2从
个不同元素中任取m个允许元素重复出现的组合叫做
个不同元素的m可重组合，其组合数为
8．二项式定理：若

∈N则ab

C
0

a


C
1a
1bC
2a
2b2



C
r

a


r
b
r

C


b



其中第r1项Tr1叫二项式系数。9．随机事件：在一定条件下可能发生也r