基本概念

• **排列数（Permutational number）：**从$n$个不同元素中，任选$m(m \leq n)$个元素排成一列的方案数，记作$A_n^m$或$P_n^m$，有$A_n^m = n (n-1)\cdots(n - m + 1) = \frac{n!}{(n - m)!}$。
• **组合数（Combinatorial number）：**从$n$个不同元素中，任选$m(m \leq n)$个元素的方案数，记作$C_n^m$，有$C_n^m = \frac{A_n^m}{m!} = \frac{n!}{m!(n-m)!}$。由于组合数出现在二项式定理中，又称作二项式系数，记作$\binom{n}{m}$，这种表示形式更为常见。
• **加法原理：**如果完成一件事情有$n$类方法，第$i$类方法有$a_i$种，那么完成这一件事情共有$S = \sum_{i=1}^n a_i$种不同的方法。
• **乘法原理：**如果完成一件事情有$n$个步骤，第$i$个步骤有$a_i$种方法，那么完成这一件事情共有$S = \prod_{i=1}^n a_i$种不同的方法。

组合数（二项式系数）

$$ C_n^m = \binom{n}{m} = \frac{n!}{m!(n-m)!} $$

组合数有如下性质：

$$ \begin{align} \binom{n}{m} &= \binom{n-1}{m} + \binom{n-1}{m-1} \\ \binom{n}{m} &= \frac{n}{m} \cdot \binom{n-1}{m-1} = \frac{n - m + 1}{m} \binom{n}{m - 1} \\ \binom{n}{h} \cdot \binom{n - h}{k} &= \binom{n}{k} \cdot \binom{n - k}{h} = \binom{n}{h + k} \cdot \binom{h + k}{h} \\ \binom{n+m}{m} &= \sum_{i=0}^m \binom{n}{i} \binom{m}{m-i} \\ \sum_{r=0}^k \binom{n+r-1}{r} &= \binom{n+k}{k} \end{align} $$

式$(1),(2),(3),(4)$可以由组合数的公式计算得到，下面证明式$(5)$：

$$ \begin{aligned} \sum_{r=0}^k \binom{n+r-1}{r} &= \binom{n-1}{0} + \sum_{r=1}^k \binom{n+r-1}{r} \\ &= \binom{n}{0} + \binom{n}{1} + \sum_{r=2}^k \binom{n+r-1}{r} \\ &= \binom{n+1}{1} + \binom{n+1}{2} + \sum_{r=3}^k \binom{n+r-1}{r} \\ &\dots \\ &= \binom{n+k-1}{k-1} + \binom{n+k-1}{k} \\ &= \binom{n+k}{k} \end{aligned} $$

抽屉原理

定理：$将n个物品分成k组，那么至少有一组的物品数\geq \lceil \frac{n}{k} \rceil$。

**Proof：**使用反证法证明，假设定理不成立，即每组物品数$a_i < \lceil \frac{n}{k} \rceil$，则$S = \sum_{i=1}^k a_i \leq k \times (\lceil \frac{n}{k} \rceil - 1) = k \times \lceil \frac{n}{k} \rceil - k < k \times (\frac{n}{k} + 1) - k = n$与$S = n$矛盾，故定理成立。$\square$

错排公式

错排问题是排列组合中的经典问题之一，$\{ 1, 2, \dots, n \}$的排列共$n!$种，若对排列$a_i$有$\forall i \in \{ 1, 2, \dots, n \}, a_i \neq i$，则称这种排列叫做错排，$n$个元素的错排数记作$D_n$，有错排公式：

$$ D_n = (n-1)(D_{n-1} + D_{n-2}) $$