转载自：伤神的博客——概率学系列 二：深入浅出 - 加法和乘法原理以及排列和组合的定义

加法原理

如果某件事可以由$k$类不同途径之一去完成，在第一类途径中有$m1$种完成方法，在第二类途径中有$m2$，第$k$类途径中有$mk$种完成的方法，那么完成这件事总共有 $m1+m2+…+mk$种方法。

以上便是加法原理的定义，那么该如何解读呢？注意两点，

途径

指的是完成一件事情的某一条完整途径；比如从$A$点到$Z$点由多条途径（注意，加法原理需要保证途径是单向的），但是只要是有这么一条途径完成了$A$$\rightarrow$$Z$，就称为一类途径；

k 类不同路径

这里的类可以更为直观的理解成条，既是 k 条路径；
所以加法原理便是这些所有可能的途径之和。

乘法原理

如果某件事需经过$k$个步骤才能完成，做第一步有$m1$种方法，做第二件事有$m2$种方法，…，做第 $k$ 步有 $mk$ 种方法，那么完成这件事总共有 $m1×m2×…×mk$ 种方法。

以上便是乘法原理的定义，那么又该如何解读呢？首先，与加法原理不同的是，加法原理实际上是站在结果的角度来思考问题的；而乘法原理是站在中间步骤的角度上来思考问题的；比如有多少个从 A 点到 Z 点的途径？加法原理是站在最终的结果的角度既途径来思考问题的，而乘法原理则是站在中间的步骤的可能性既方法的角度来思考问题的。其次，加法原理和乘法原理其实是相容的，比如，针对同一件事 $A$$\rightarrow$$Z$ 有多少条途径，该途径之和 $= m1×m2×…×mk$ 种方法。

由此，可以猜测，乘法原理感觉上是对加法原理的进行了一次抽象而已；针对同一件事，两种原理的计算结果相同，只是算法和研究问题的角度不同而已；那么笔者在这里所描述的这种抽象指的是什么？笔者试图通过下面的例子一步一步的进行推导；

考虑这样一种最简单的情况，假设我们有这样一个篮子，里面放置了编号分别为 $1、2、3$ 的三个小球，要完成这么一件事情，随机抽取两次，每次只取一个小球且不放回，试问，取出的两个小球的编号总共有多少种可能？(从概率学的观点，完成这件事总共的样本点是多少？)

从加法原理出发，我们知道，它研究问题的角度是事情的结果，所以笔者将所有可能的结果绘制了出来，如下图所示，

注意，笔者将该结果归为了三类，既是选中 $1$ 的途径、选中 $2$ 的途径和选中 $3$ 的途径，图中黑色表示两次选出的小球，就是一类途径既结果，标识 $A、B$ 分别表示第一次和第二次取球的动作；将这三类相关的所有途径的相加的总和 $6$，也就是通过加法原理所求得的所有可能性的总和，也就是概率学中所描述的总体样本点。上述关系同样可以简化成下面这张图，红色的线条表示选中 $1$ 号球的所有可能性，黑色线条表示选中 $2$ 号球的所有可能性，绿色线条表示选中 $3$ 号球的所有可能性；

那么，为什么笔者说乘法原理是对加法原理的抽象呢？其实乘法原理是对种种结果既途径进行了归纳和抽象，发现途径中的各个步骤与最终的结果（既所有途径之和）有着某种必然的关系，而通过数学的定义，可以归纳出这种关系；那么乘法原理是如何来从它的角度来描述这种关系的呢？注意，它研究问题的角度是从途径中的每一个步骤出发的，既是分别站在步骤 $A、B$ 的角度出发的，如上图可知，步骤 $A$ 有 $3$ 种选择，而步骤 $B$ 有 $2$ 种选择，那么每个步骤的选择是否与最终结果既所有途径之和存在某种必然的联系呢？步骤 $A$ 有 $3$ 种选择，如果选定任意一种选择以后，步骤 $B$ 都会有 2 种选择；所以这种关系可以用下面这个加法表达式来表示，$2+2+2$。

第一个 $2$ 表示选中 $1$ 号球以后的所有可能性，第二个 $2$ 表示选中 $2$ 号球以后的所有可能性，第三个 $2$ 表示选中 $3$ 号球以后的所有可能性；因此，我们得到了所有途径之和等于 $3$ 个 $2$ 相加这样的一个结果；实际上，这正是加法原理的解题思路，从某一个起点开始，计算所有可能的途径，然后将所有起点对应的途径的可能相加记得到最终的结果；然而，当我们将研究问题的角度转向过程中的每一个步骤以后，就会得到这样一个非常关键的结论，既所有途径之和 $= 3 个 2$ 相加；而这个结论就是将加法原理转向乘法原理的关键之所在了，数学家们顺势而为，将这种关系定义为乘法原理，该原理既是将这种关系进行了抽象化，进行了数学上的定义，其定义的形式既是大家所熟知的$3×2$。

当然，它实际所表达的数学意义其实就是 $3 个 2$ 相加，也就是所有途径之和；然后，乘法原理换了个角度来描述这个问题，从各个步骤的选择方式来进行描述，第一次取出既步骤 $A$ 的可能选择是 $3$，第二次取出既步骤 $B$ 的可能选择是 $2$，那么总体选择 $= 3×2 = 所有途径之和$；笔者通过下面这张概念图来描述了这种关系，步骤 $A 有 3$ 中可能，而步骤 $B 有 2$ 中可能，两者的乘积便是所有途径之和，既是样本空间的大小；

显然，这种规则可以推广到任意多个球，任意多个步骤的情形，笔者这里不再论述；由此可知，加法原理和乘法原理是相容的，只是研究问题的角度不同而已，研究问题的方式其实最终都是加法原理；

总结

笔者对上述的原理进一步进行总结，并给出了自己的定义，实际上加法原理的解题思路笔者将其命名为横向思维，考察的就是就是从起点一直到终点的所有途径的可能；而乘法原理的解题思路笔者将其命名为纵向思维，将计算所有从起点到终点途径的可能性的问题转化到了各个步骤上，只需要考察各个步骤的可能性，最终根据乘法原理只需要将各个步骤的可能性相乘便得到所有途径的可能性；因此，乘法原理通过纵向思维将解题办法和思路简化了，而这种简化正是建立在乘法原理对加法原理的抽象上的。

排列和组合
从原理上理解了加法原理和乘法原理以后，再来理解排列和组合就容易多了，

排列
从$n$个不同元素中任意取 $r(r≤n)$ 个元素排成一列（考虑元素先后出现的次序），称此为一个排列，此种排列的总数记为 P^r_n。按照乘法原理，取出的第一个元素有 $n$ 种取法，取出的第二个元素有 $n−1$ 种取法，……，取出第 $r$ 个元素有 $n−r+1$ 种取法，所以有 $$P^r_n=n×(n−1)×…×(n−r+1)=\frac{n!}{(n−r)!}$$

若 $r=n$，则称为全排列，记为 $P_n$。显然 $P_n=n!$。

上面便是排列所给出的定义，其实所描述的内容就是乘法原理；

重复排列

从 $n$ 个不同元素中每次取出一个，放回后再取下一个，如此连续取 $r$ 次所得的排列称为重复排列，此种重复排列数共有 $nr$ 个。注意：这里的 $r$ 允许大于 $n$；

很好理解，如果要放回，那么每一个步骤既每一次选择都有 $n$ 种可能性，所以，这种情况下，总共的样本点为 $n1×n2×⋯×nr=nr$；还是以乘法原理中的例子为例，好玩的是，一种最为极端的例子，那么有可能三次都取到 1 号球；

组合

从 $n$ 个不同元素中任意取 $r(r≤n)$ 个元素并成一组（不考虑元素间的先后次序），称此为一个组合，此中组合的总数记为 $\big(^n_r\big)$ 或 $C^r_n$。按照乘法原理此中组合的总数为
$$\Big(^n_r\Big)=\frac{P^r_n}{r!}=\frac{n(n−1)…(n−r+1)}{r!}=\frac{n!}{r!(n−r)!}$$
组合也源自于乘法原理，但是它的样本集只是通过乘法原理所得到的所有途径总和的一个子集，因为它不考虑取出结果的顺序，所以它要对结果样本集进行去重；以乘法原理中的例子为例，按照乘法原理，我们得到的结果的全集是 ${ [1, 2]、[1, 3]、[2, 1]、[2, 3]、[3, 1]、[3, 2] }$；如果不考虑取出元素的先后顺序，那么结果集中的 $[1, 2] 和 [2, 1]，[1, 3] 和 [3, 1] 以及 [2, 3] 和 [3, 2]$ 都将视为是同一个结果，所以需要进行去重；去重以后，所得到的结果就是组合的结果，既是 ${ [1, 2]、[1, 3]、[2, 3] }$ 这样包含 3 个结果的样本集；因此可以看到，组合得到的样本集其实是$\frac{乘法原理}{排列}$所得到的样本集的一个子集，这也是组合有别于排列的关键因素；

通过笔者上述的描述，相信大家知道了该如何去重了，但是定义中为什么要将排列的结果除以 $r!$ 呢？不难发现，这样做的目的就是为了去重，但是，背后的规律是什么呢？数学意义或者依据在哪呢？很遗憾，定义中并没有给出，而是直接告诉你除以 $r!$ 就好，笔者不想止步于似懂非懂的层面，那么笔者就试图探究一下这样做背后的数据意义是什么，由此笔者做了如下的推导，假设总共有 $n$ 个元素，

如果取 $2$ 次，假设，去重以后的样本点有 $m$ 个，其中任意一个样本点用 $Ex$ 表示，该样本点可表述为 ${ Ex1,Ex2 }$ 其中 $Ex1,Ex2$ 为该样本点所包含的元素，如果考虑样本点中元素先后取出的顺序，那么要计算出由该样本点所衍生出来的所有样本点（这里指的是交换元素的位置），根据乘法原理，就相当于对该样本点 ${ Ex1,Ex2 }$ 中的元素进行一次全排列既 $P_2$，所以我们得到，由样本点 ${ Ex1,Ex2 }$ 所衍生的所有样本点(包括自己) $= 1×P_2 = 2$ 个，由此我们推广至去重后的所有样本空间既 $m$ 个样本点，均满足该特性，又有，
➭ 首先，去重以后的样本空间即组合的样本空间 $=m=\big(^n_r\big)$；
➭ 那么，根据上述的规律是否可以求得排列的样本空间呢？显然，排列的样本空间 $P^2_n=P_2×\big(^n_2\big)=2×\big(^n_2\big)$；
➥ 由此，我们好像得到了一个非常重要的关系既排列的样本空间 $= Pr×$ 组合的样本空间( r 表示取的次数 )；
➥ 但是，这个猜想是否适用于取任意 r 次呢？看下面的例证，

如果取 r 次，同样假设，去重以后的样本点总共有 m 个，其中任意一个样本点用 Ex 表示，该样本点可表述为 {Ex1,Ex2,…,Exr}，那么要求得该样本点所衍生的（通过修改元素先后取出的顺序）所有样本点就相当于对 {Ex1,Ex2,…,Exr} 中的所有元素进行全排列既 Prn，同样，
➭ 首先，去重以后的样本空间既组合的样本空间 $=m=\big(^n_r\big)$；
➭ 那么，显然，排列的样本空间 $P^r_n=P_r×\big(^n_r\big)=r!×\big(^n_r\big)$；
➥ 由此，该关系既排列的样本空间 $= P_r × 组合的样本空间$( $r$ 表示取的次数 ) 成立；

所以，不难发现其背后的一个核心的逻辑，就是$P^r_n=r!×\big(nr\big)$

其背后的数学意义就是，排列的样本空间就是组合中的每一个样本点通过全排列所得到的样本空间的集合；

补充，在遇到实际问题的时候，判断该问题是否是排列还是组合问题，有一个快速的判别方法，问自己，一个样本点中的各个元素的顺序是否可以交换？如果可以交换，则是排列问题，如果不可以交换则是组合问题；因为如果其中的某一个样本点中的元素允许交换位置，那么所有样本点中的元素都可以交换位置，则必然是排列问题。