排列组合：公式及推导

引入

定义：

排列：从指定个数的元素中取出指定个数的元素进行排序；(考虑元素的顺序)
组合：从给定个数的元素中仅仅取出指定个数的元素；(不考虑元素的顺序)

加法&乘法原理

加法原理：

完成一个工程可以有 $n$ 类办法， $a_i(i\in[1,n])$ 代表第$i$ 类方法的数目。则完成这件事共有 $S=a_1+a_2+a_3+···+a_n$ 种不同的方法。

乘法原理：

完成一个工程需要 $n$ 个步骤，$a_i(i\in[1,n])$ 代表第 $i$ 个步骤的不同方法的数目。那么完成这个工程共有 $S=a_1 \times a_2 \times a_3 \times ··· \times a_n$ 种不同的方法。

排列与组合基础

排列数：

从 $n$ 个不同的元素中，任取 $m(m \leqslant n,m与n均为自然数，下同)$ 个元素按照一定的顺序排成一列，叫做从 $n$ 个不同元素中 $m$ 个元素的一个排列；从 $n$ 个不同元素中取出 $m(m \le n)$ 个元素的所有排列个数，叫做从 $n$ 个元素中取出 $m$ 个元素的排列数，用符号 $A^m_n$ (或者是 $P^m_n$ )表示。
排列的计算公式如下：

$A^m_n =n(n-1)(n-2)..(n-m+1)=\frac{n!}{(n-m)!}$

$n!$ 代表 $n$ 的阶乘，即 $6!=1 \times 2 \times 3 \times 4 \times 5 \times 6$ 。

公式可以这样理解： $n$ 个人选 $m$ 个来排队，队长为 $n$ ( $m \leqslant n$ )，第一个位置可以选的人为 $n$ 个,第二个位置可以选的人为 $n-1$ 个，以此类推，第 $m$ 个(最后一个)可以选 $n-m+1$ 个，得：

\[A^n_m =n(n-1)(n-2)...(n-m+1)= \frac{n!}{(n-m)!} \]

全排列： $n$ 个人来排队，队长为 $n$ 。第一个位置可以选 $n$ 个，第二个位置可以选 $n-1$ 个，依此类推得：

\[A^n_n=n(n-1)(n-2)...3 \times 2 \times 1=n! \]

全排列是排列数的一个特殊情况。

组合数：

从 $n$ 个不同元素中，任取 $m(m \leqslant n)$ 个元素组成一个集合，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个组合；从 $n$ 个不同元素中q取出 $m(m \leqslant n)$ 个元素组成的所有组合的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的组合数，用符号 $(^n_m)$ 来表示，读作 $\left\lceil n选m \right\rfloor $ 。
组合数计算公式：

\[( ^n_m )=\frac{A^m_n}{m!}=\frac{n!}{m!(n-m)!} \]

如何理解上述公式？考虑 $n$ 个人选 $m$ 个出来 $(m \leqslant n)$ ,不排队，不在乎顺序。如果关心顺序，则为 $A^m_n$ ,若不关心那么就要除掉重复，那么重复了多少？同样 $m$ 个人，还要 $\left\lceil 全排列 \right\rfloor $ 得 $m!$ ，所以得：

\[( ^n_m )\times m!=A^m_n \]

\[(^n_m )=\frac{A^m_n}{m!}=\frac{n!}{m!(n-m)!} \]

组合数也常用 $\complement^m_n$ 表示，即 $\complement^m_n=(^n_m)$ 。

组合数也被称为 $\left\lceil 二项式系数 \right\rfloor $ ，下文会阐述其联系。

特别的，当 $m>n$ 时，$A^m_n=(^n_m)=0$ 。