计数原理
加法原理
各手段只能用一个。
乘法原理
各手段互相独立。
排列与组合
排列 A^m_n
- 从
n 个元素中有顺序地取m 个的方案数 -
A^m_n=(n)\cdot(n-1)\cdots(n-m+1)
组合 C^m_n
-
从
n 个元素中不考虑顺序地取m 个的方案数 -
C^m_n=\frac{A^m_n}{A^m_m} -
组合数递推
-
C^0_n=1 -
C^m_n=C^m_{n-1}+C^{m-1}_{n-1} -
注意到有
C^m_n=C^{n-m}_n -
杨辉三角
| nm | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 1 | |||||
| 1 | 1 | ||||
| 1 | 2 | 1 | |||
| 1 | 3 | 3 | 1 | ||
| 1 | 4 | 6 | 4 | 1 |
常用技巧（不要乱用）
捆绑法
- 例：排列A~G，要求AB相邻
- 将所需元素合并为一个元素
-
ans=A^6_6A^2_2
隔板法
- 例：排列A~G，要求AB不相邻
- 先排列另外5个元素，形成6个“空位”
- 然后选两个空位插入即可
-
ans=A^5_5C^2_7A^2_2=A^5_5A^2_7
选题
由0,1,2,3,4,5组成的没有重复数字的五位奇数个数？
10个球分到7个盒子，每个盒子至少分到1个，问方案数？
即在10个球的9个空位中放6个隔板