组合数学

注意：若无特殊说明，本章涉及的变量皆为正整数.

• 排列：从 $n$ 个元素中取出 $m$ 个，按一定顺序排列.

• 组合：从 $n$ 个元素中取出 $m$ 个，不计排列顺序.

一算法有 $n$ 种方式，第 $i$ 种方式有 $a_i$ 种方法，该算法共有 $\sum_{i=1}^na_i$ 种实现方法.

例

从 $A$ 地到 $B$ 地有爬行、骑车、飞行三种方式，可以任选一个. 而爬行、骑车、飞行分别有 $a_1,a_2,a_3$ 种方法，那么 $A→B$ 共有 $a_1+a_2+a_3$ 种方法.

一算法有 $n$ 个步骤，第 $i$ 个步骤有 $a_i$ 种方法，该算法共有 $\prod_{i=1}^na_i$ 种实现方法.

例

从 $A$ 地到 $B$ 地必须先爬行到车站，再骑车到机场，最后飞行到北京，而爬行、骑车、飞行分别有 $a_1,a_2,a_3$ 种方法，那么 $A→B$ 共有 $a_1\cdot a_2\cdot a_3$ 种方法.

从 $n$ 个元素中取出 $m$ 个，按一定顺序排列的方案数，用符号 $A_n^m$ 表示.

$$A_n^m=n(n-1)(n-2)\cdots(n-m+1)=\frac{n!}{(n-m)!}$$

$n=m$ 时的排列称为全排列，$A_n^n=n!$.

从 $n$ 个元素中取出 $m$ 个，不计排列顺序的方案数，用符号 $C_n^m$ 或 ${n\choose m}$ 表示.

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

特别地，当 $m>n$ 时，$A_n^m=C_n^m=0$

$$\binom{n}{m}=\binom{n}{n-m}$$

证

$$\binom{n}{n-m}=\frac{n!}{(n-m)![n-(n-m)]!}=\frac{n!}{(n-m)!m!}=\binom{n}{m}$$

$$\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}$$

证

$$\begin{aligned} &\binom{n-1}{m}=\frac{(n-1)!}{m!(n-m-1)!}=\frac{1}{m}\cdot\frac{(n-1)!}{(m-1)!(n-m-1)!}\\ &\binom{n-1}{m-1}=\frac{(n-1)!}{(m-1)!(n-m)!}=\frac{1}{n-m}\cdot\frac{(n-1)!}{(m-1)!(n-m-1)!}\\ \end{aligned} \\ \begin{aligned} \\ \binom{n-1}{m}+\binom{n-1}{m-1}&=(\frac{1}{m}+\frac{1}{n-m})\cdot\frac{(n-1)!}{(m-1)!(n-m-1)!}\\ &=\frac{n}{m(n-m)}\cdot\frac{(n-1)!}{(m-1)!(n-m-1)!}\\ &=\frac{n!}{m!(n-m)!}\\ &=\binom{n}{m} \end{aligned}$$