前置芝士

加法原理

完成一项工作有 \(n\) 类方法，每类方法有 \(a_i\) 种，则总共有 \(\sum\limits_{i=1}\limits^{n} a_i\) 种方法完成这项工作。

乘法原理

完成一项工作有 \(n\) 个步骤，每个步骤有 \(a_i\) 种方法，则 \(\prod\limits_{i=1}\limits^{n} a_i\) 种方法完成这项工作。

排列

在 \(n\) 个数中选出 \(m\) 个数组成一个序列，共有 \(\dfrac{n!}{(n-m)!}\) 种方法，记作 \(A_n^m\)。

组合

在 \(n\) 个数中选出 \(m\) 个数组成一个集合，共有 \(\dfrac{n!}{m!(n-m)!}\) 种方法，记作 \(C_n^m\)。

插板法

例 1

有 \(n\) 个相同的小球，将它们分为 \(k\) 组，要求每组不能为空，问共有多少种方案？

考虑将问题转化一下，变为有 \(k-1\) 个隔板隔开这些小球，要从 \(n-1\) 个空中选 \(k-1\) 个，答案为 \(C_{n-1}^{k-1}\)。

例 2

有 \(n\) 个相同的小球，将它们分为 \(k\) 组，每组可以为空，问共有多少种方案？

我们在原来 \(n\) 个球的基础上再拿 \(k\) 个球过来，转化为每组不能为空的形式（只有新拿来的 \(k\) 个球的一组就对应原情况的空组），从 \(n+k-1\) 个空中选 \(k-1\) 个，答案为 \(C_{n+k-1}^{k-1}\)。

上面这个例子的本质就是求 \(\sum\limits_{i=1}\limits^{n} x_i = n(x_i \ge 0)\) 的解的组数。

在下面这个例子将会用到它。

例 3

有 \(n\) 个相同的小球，将它们分为 \(k\) 组，要求每组至少有 \(a_i\) 个，问共有多少种方案？

考虑还是再拿 \(\sum a_i\) 个球过来。我们令 \(x_i\) 为第 \(i\) 组分到的球数，那么我们令 \(y_i=x_i-a_i\)，则有 \(\sum y_i+\sum a_i =n\)。

整理得 \(\sum y_i=n-\sum a_i(y_i\ge 0)\)。

这就转化为了例 2，插板得到答案为 \(C_{n-\sum a_i+k-1}^{n-\sum a_i}\)。