组合数学

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

简介 #

  • 排列:从 $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}$$