排列组合

排列

从 $n$ 个不同元素中取出 $m(m \leqslant n)$ 个元素，按照一定顺序排成一列，叫作从 $n$ 个不同元素中任意取出 $m$ 个元素的一个排列(arrangement). 我们把有关求排列的个数的总是叫作排列问题.

我们把从 $n$ 个不同元素中取出 $m(m \leqslant n)$ 个元素的所有排列的个数，叫作从 $n$ 个不同元素中任意取出 $m$ 个元素的排列数，记作 {$A^m_n$ }

排列数公式：

${A^m_n}$

$=n(n-1)(n-2)\cdots(n-m+1)$

$=\dfrac{n!}{(n-m)!}$

特别地，当 $m=n$ 时，$A^n_n=n!$ .

另外，规定：0!=1

组合

从 $n$ 个不同元素中取出 $m(m \leqslant n)$ 个元素合成一组，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个组合(combination).

我们把从 $n$ 个不同元素中取出 $m(m \leqslant n)$ 个元素的所有组合的个数，叫作从 $n$ 个不同元素中任意取出 $m$ 个元素的组合数，记作 { $C^m_n$ } ，组合数公式：

${C^m_n}$

$=\dfrac{A^m_n}{A^m_m}$

$=\dfrac{n(n-1)(n-2)\cdots(n-m+1)}{m!}.$

$=\dfrac{n!}{m!(n-m)!}$

特别地，当 $m=n$ 时，$C^n_n=1$ .

另外，规定：$C^0_n=1$

组合有一个性质：

$C^m_n=C^{n-m}_n$ （从 $n$ 个元素中取 $m$ 个元素的方法，就是从 $n$ 个元素中留出 $n-m$ 个元素的方法.）

排列，与抽出元素的顺序有关；组合，与抽出元素的顺序无关.

一个问题

从组合的概念知道，组合数必然是整数，那么，怎么证明呢？