排列组合
加法原理
完成某件事情有 \(n\) 类方法，其中第 \(i\) 类方法有 \(a_i\) 种方案。
则总共有 \(\sum_{i=1}^na_i\) 种方案。
乘法原理
完成某件事有 \(n\) 个步骤，第 \(i\) 个步骤有 \(a_i\) 种方案。
则共有 \(\prod_{i=1}^n a_i\) 种。
排列问题
定义：在一个集合中，有序地不重复地选取若干元素。
- 排列数
给定一个 \(n\) 个元素的集合，从中有序地选出 \(m\) 个元素，方案为 \(n(n-1)(n-2)\cdots (n-m+1)=\frac{n!}{(n-m)!}\)。
定义对于 \(n\ge m\)，\(P(n,m)\) 表示从 \(n\) 个元素中，有序选出 \(m\) 个的方案数。
所以 \(P(n,m)=\frac{n!}{(n-m)!}\)。
- 组合数
对于一个有 \(n\) 个元素的集合，从中无序地选出 \(m\) 个，方案为 \(\frac{n!}{m!(n-m)!}\)，用 \(C_n^m\) 表示。
显然有 \(C^n_m=C^{n-1}_m+C^{n-1}_{m-1}\)，意思是最后一个数字（第 \(m\) 个）选和不选。
插板法
题目：将 \(n\) 个相同的物品，放入 \(m\) 个不同的盒子里，问方案数。
考虑将 \(n\) 个物品排成一排，\(m\) 个盒子就是用 \(m-1\) 个板子，将 \(n\) 个物品隔成 \(m\) 段，每段都当作放进一个盒子中。
方案数为 \(C_{n-1}^{m-1}\)。
还可以转化成类似于 \(\sum_{i=1}^m x_i=n\) 的正整数解个数。
改版：将 \(n\) 个相同的物品，放入 \(m\) 个不同的盒子里，但是不要求每个盒子都要放，求方案数。
可以考虑让每个盒子里附带上一个借来的物品，这样既可以满足不需要新放入，又可以用公式做。
方案数：\(C_{n+m-1}^{m-1}\)。
那么又可以转化成了满足 \(\sum_{i=1}^m x_i=n\) 的非负整数解个数。
还相当于满足 \(\sum_{i=1}^m y_i=n+m\) 的正整数解个数。