排列和组合

转自：https://www.cnblogs.com/1024th/p/10623541.html

绪论：加法原理、乘法原理

分类计数原理：做一件事，有n类办法，在第1类办法中有$m_1$种不同的方法，在第2类办法中有$m_2$种不同的方法，…，在第n类办法中有$m_n$种不同的方法，那么完成这件事共有$N=m_1+m_2+…+m_n$种不同的方法。

分步计数原理：完成一件事，需要分成n个步骤，做第1步有$m_1$种不同的方法，做第2步有$m_2$种不同的方法，…，做第n步有$m_n$种不同的方法,那么完成这件事共有$N=m_1×m_2×⋯×m_n$种不同的方法。

区别：分类计数原理是加法原理，不同的类加起来就是我要得到的总数；分步计数原理是乘法原理，是同一事件分成若干步骤，每个步骤的方法数相乘才是总数。

排列问题

排列数

从n个不同元素种取出 $m(m \leqslant n) $个元素的所有不同排列的个数，叫做从n个不同元素种取出m个元素的排列数，用符号$A^m_n$表示。

排列数公式

$$ \begin{aligned} \mathrm{A}_n^m&=n(n-1)(n-2)\cdots(n-m+1)=\frac{n!}{(n-m)!},\\ &\quad n,m\in \mathbb{N}^* ,\text{并且}m \leqslant n \end{aligned} $$

（规定$0!=1$）

推导：把n个不同的元素任选m个排序，按计数原理分步进行：
取第一个：有n种取法；
取第二个：有(n−1)种取法；
取第三个：有(n−2)种取法；
……
取第m个：有(n−m+1)种取法；
根据分步乘法原理，得出上述公式。

排列数性质

公式1：$\mathrm{A}_n^m = n\mathrm{A}_{n-1}^{m-1}$可理解为“某特定位置”先安排，再安排其余位置。
公式2：$\mathrm{A}_n^m = m\mathrm{A}_{n-1}^{m-1} + \mathrm{A}_{n-1}^m$可理解为：含特定元素的排列有$m\mathrm{A}_{n-1}^{m-1}$，不含特定元素的排列为$\mathrm{A}_{n-1}^m$。

组合问题

组合数

从n个不同元素种取出$m(m \leqslant n)$个元素的所有不同组合的个数，叫做从n个不同元素种取出m个元素的组合数，用符号$C^m_n$表示。

组合数公式

$$ \begin{aligned} \mathrm{C}_n^m&=\frac{\mathrm{A}_n^m}{\mathrm{A}_m^m}=\frac{n(n-1)(n-2)\cdots (n-m+1)}{m!}=\frac{n!}{m!(n-m)!},\\ &\quad n,m\in \mathbb{N}^* ,\text{并且}m \leqslant n \end{aligned} $$

证明：利用排列和组合之间的关系以及排列的公式来推导证明。

将部分排列问题$\mathrm{A}^{m}_{n}$分解为两个步骤：

第一步，就是从n个球中抽m个出来，先不排序，此即组合数问题$ \mathrm{C}^{m}_{n}$；

第二步，则是把这m个被抽出来的球排序，即全排列$\mathrm{A}^{m}_{n}$。

根据乘法原理，$\mathrm{A}_n^m=\mathrm{C}_n^m \mathrm{A}_m^m$，那么

$$ \mathrm{C}_n^m=\frac{\mathrm{A}_n^m}{\mathrm{A}_m^m}=\frac{n(n-1)(n-2)\cdots (n-m+1)}{m!}=\frac{n!}{m!(n-m)!} $$

$$ \mathrm{C}_n^0=\mathrm{C}_n^n=1 $$

证明：利用排列和组合之间的关系以及排列的公式来推导证明。
将部分排列问题$ A^m_n$分解为两个步骤：
第一步，就是从n个球中抽m个出来，先不排序，此即组合数问题$ C^m_n$；
第二步，则是把这m个被抽出来的球排序，即全排列$ A^m_m$。
根据乘法原理，$ A^m_n$=$ C^m_n$$ A^m_m$，那么

$$ \mathrm{C}_n^m=\frac{\mathrm{A}_n^m}{\mathrm{A}_m^m}=\frac{n(n-1)(n-2)\cdots (n-m+1)}{m!}=\frac{n!}{m!(n-m)!} $$

组合数的性质

$\mathrm{C}_n^m = \mathrm{C}_n^{n-m}$可以理解为：将原本的每个组合都反转，把原来没选的选上，原来选了的去掉，这样就变成从n个元素种取出n−m个元素，显然方案数是相等的。

递推公式$\mathrm{C}_n^m=\mathrm{C}_{n-1}^m+\mathrm{C}_{n-1}^{m-1}$ 可理解为：含特定元素的组合有$\mathrm{C}_{n-1}^{m-1}$，不含特定元素的排列为$\mathrm{C}_{n-1}^m$。还不懂？看下面。

Example
从1，2，3，4，5（n=5）中取出2（m=2）个元素的组合（$\mathrm{C}_n^m$）：
12 13 14 15 23 24 25 34 35 45
显然，这些组合中要么含有元素“1”，要么不含。
其中含有“1”的是：12 13 14 15
把里面的“1”都挖掉：2 3 4 5
而上面这个等价于从2，3，4，5（n−1）中取出1（m−1）个元素的组合。
其中不含“1”的是：23 24 25 34 35 45
上面等价于从2，3，4，5（n−1）中取出2（m）个元素的组合。
而总方案数等于上面两种情况方案数之和，即$\mathrm{C}_n^m=\mathrm{C}_{n-1}^m+\mathrm{C}_{n-1}^{m-1}$。

组合数求和公式

$$ \mathrm{C}_n^0+\mathrm{C}_n^1+\mathrm{C}_n^2+\cdots+\mathrm{C}_n^n=2^n $$

我们感性认知一下，上面这个式子的左边表示什么呢？
把从n个球中抽出0个球的组合数（值为1）、抽出1个球的组合数、抽出2个球的组合数、……、抽出n个球的组合数相加。
换句话说，就是从n个球中随便抽出一些不定个数球，问一共有多少种组合。
对于第1个球，可以选，也可以不选，有2种情况。
对于第2个球，可以选，也可以不选，有2种情况。
对于任意一个球，可以选，也可以不选，有2种情况。
根据乘法原理，一共$\underbrace{2\times 2\times \cdots \times 2}_{n\text{个2相乘}} = 2^n$种组合。
想要严谨的证明？数学归纳法：
当n=1时，$\mathrm{C}_1^0+\mathrm{C}_1^1=2=2^1$成立。
假设$n=k(k\in \mathbb{N}^*)$时等式成立，即

$$ \sum_{i=0}^{k} \mathrm{C}_k^i=2^n $$

成立，当$n=k+1$时，

$$ \begin{aligned} & \mathrm{C}_{k+1}^0 + \mathrm{C}_{k+1}^1 + \mathrm{C}_{k+1}^2 + \cdots + \mathrm{C}_{k+1}^{k} + \mathrm{C}_{k+1}^{k+1}\\ = & \mathrm{C}_{k+1}^0+ \left(\mathrm{C}_k^0+\mathrm{C}_k^1\right) + \left(\mathrm{C}_k^1+\mathrm{C}_k^2\right) + \cdots + \left(\mathrm{C}_k^{k-1}+\mathrm{C}_k^k\right) + \mathrm{C}_{k+1}^{k+1}\\ = & \left(\mathrm{C}_k^0 + \mathrm{C}_k^1 + \mathrm{C}_k^2 + \cdots + \mathrm{C}_k^k\right) + \left(\mathrm{C}_k^0 + \mathrm{C}_k^1 + \mathrm{C}_k^2 + \cdots + \mathrm{C}_k^k\right)\\ = & 2 \times 2^k\\ = & 2^{k+1} \end{aligned} $$

等式也成立。
由1、2得，等式对$n\in \mathbb{N}^*$都成立。
也可偷懒地用二项式定理证明：

$$ (a+b)^n=\sum_{k=0}^{n}\mathrm{C}_n^k a^{n-k}b^k $$

令a=b=1，就得到了

$$ \sum_{i=0}^{n} \mathrm{C}_n^i=2^n $$

类似的公式（由$\mathrm{C}_n^m = \mathrm{C}_n^{n-m}$推导）：

$$ \mathrm{C}_n^0 + \mathrm{C}_n^2 + \mathrm{C}_n^4 + \cdots = \mathrm{C}_n^1 + \mathrm{C}_n^3 + \mathrm{C}_n^5 + \cdots =2^{n-1} $$