排列和组合是计数原理中的基础。其概念并不复杂，但应用起来非常灵活多变，所以如何理解这类公式尤为重要。

排列和组合的定义

讲到排列和组合就需要先介绍一下阶乘的概念：

n个不同元素的全排列称为n的阶乘，记作n!

n!=n\cdot (n-1)\cdot (n-2)\cdots1

可以理解为这n个元素排成一列，将这一操作分成n步来实施：第一步，选取1个元素，有n种方法；第二步，从剩下的n-1个元素中再选取第一个，有n-1种方法。。。直到第n步：选取最后一个元素时只剩下了1个元素可选，所以只有1种选择。符合分步计数原理， n\cdot (n-1)\cdot (n-2) \cdot(n-3) \cdots 1

排列所关注的是n个不同元素中选取r个元素排成一列，一共有多少种方法；记作 P_{n}^{r} （P为Permutation的首字母）

组合描述的是n个不同元素中选取r个组成一组，一共有多少种方法；记作 C_{n}^{r} （C为Combination的首字母）

从定义中我们可以看出排列和组合很相似，其不同点在于，对于排列来说，排列的结果中元素的顺序有关；而对于组合来说，元素的顺序无关。如a,b,c与a,c,b对于排列来说是两个不同的排列，而对于组合来说就是同一种组合。

排列组合公式

排列的公式： P_{n}^{r}=\frac{n!}{(n-r)!} 可以理解为阶乘n!的一部分，即阶乘n!在计算的过程中，排列了前r个元素后即停止了。

组合的公式 C_{n}^{r}=\frac{n!}{r!(n-r)!} 和 P_{n}^{r} 的关系：可以理解为组合 C_{n}^{r} 和排列 P_{n}^{r} 选取出的元素都是相同的，只是排列 P_{n}^{r} 中的各种顺序对于组合并不重要，所以排列 P_{n}^{r}=\frac{n!}{(n-r)!} 中r个元素所形成的各种顺序在组合 C_{n}^{r} 中看成是同一种，所以需要在 \frac{n!}{(n-r)!} 的基础上除以 r!

排列组合公式有一些性质，比如：

C_{n}^{r}=C_{n}^{n-r}

这可以看作 C_{n}^{r} 这个从n个元素选出r个这一动作是将n个元素分为两组。当我们将含有r个元素的一组分出来时，剩下的n-r个元素也就自然地形成了另外一组，即 C_{n}^{n-r} 。

又如：

C_{n}^{0}+C_{n}^{1}+C_{n}^{2}+\cdots +C_{n}^{n}=2^n

首先，我们可以从二项式定理的角度验证一下这个式子。由二项式定理： (a+b)^n=C_n^0a^n+C_n^1a^{n-1}b+C_n^2a^{n-2}b^2+\cdots +C_n^nb^n ，如果 a=b=1 ，则有 2^n=C_{n}^{0}+C_{n}^{1}+C_{n}^{2}+\cdots +C_{n}^{n} ，可知等式成立。

如何理解这一方程呢？可以考虑这样一种情况：将编号为1、2、3...、n的许多小球放入两个不同的盒子中，计算有多少种不同的方法（其中一个盒子可以是空的）。那么一种思考方式是从盒子的角度思考进行分类讨论：第一个盒子中没有球，而球全在第二个盒子中；或第一个盒子中有两个球，剩下的全在第二个盒子中...直到第n种情况，球全在第一个盒子中。由于是分类计数，应使用加法原理，所以总的方法数是 C_{n}^{0}+C_{n}^{1}+C_{n}^{2}+\cdots +C_{n}^{n}

另一种方法是从每一个小球的角度来思考。1号球可以放进第一个盒子也可以放进第二个盒子。2号球可以进第一个盒子也可以进第二个盒子...此种是分步计数的结果，应使用乘法原理，总的方法数是 2\cdot 2\cdot 2\cdots 2=2^n

可见计数部分的问题可以从不同的角度来考虑，只要合理都会得到正确的结果，所以对于不同的问题应该根据其情况使用适合的方法来分析。在之后的文章中会用更多的例子来说明。