【国际数学竞赛】如何理解组合恒等式？...

数学学习 - 2019-09-21 0 Views

排列组合中有很多恒等式，比如 $C_{n}^{m}+C_{n}^{m-1}=C_{n+1}^{m}$ 。刚接触时，我们往往把它们当作公式来记忆，利用 $P_{n}^{m}=\frac{n !}{(n-m) !}$ 和 $C_n^m=\frac{n !}{m ! \cdot(n-m) !}$ 来证明。但其实，它们都可以被赋予具体的场景(或问题)，通过“算两次”的技巧来验证和理解，比如上述恒等式左右两边都是指从 $n+1$ 个人中选出 $m$ 个人的方法数。本文从计数原理出发讲解排列与组合公式的由来，并在此基础上讲解如何通过具体的场景来理解各种不同的排列组合恒等式，比如 $C_{n}^{0}+C_{n}^{1}+\cdots+C_{n}^{n}=2^{n}$ ； $C_{r}^{r}+C_{r+1}^{r}+\cdots+C_{n}^{r}=C_{n+1}^{r+1}$ ； $C_{m}^{r} C_{n}^{0}+C_{m}^{r-1} C_{n}^{1}+\cdots+C_{m}^{0} C_{n}^{r}=C_{n+m}^{r}$ ； $C_{n}^{r} \times C_{n-r}^{k-r}=C_{n}^{k} \times C_{k}^{r}$ …… 希望与大家探讨和加深对排列组合恒等式的理解。主要内容：

（1）计数原理 （2）排列组合 （3）恒等式

一、计数原理

计数原理就是计数的方法，一共有两种原理：加法原理与乘法原理 接下里我们借助召唤师峡谷或者王者峡谷进行说明：如果做一件事情是“一步到位”，那么我们就用加法原理。从蓝色水晶沿着“上中下”三条路到红色水晶有多少种走法呢？

这一看就知道了一共三种走法，上一种、中一种、下一种，所以 $1+1+1=3$ 种。这就是加法原理。但如果你从蓝色水晶出发先到河道，然后再从河道出发前往红色水晶那有多少种走法呢？

首先蓝色水晶到河道有3种走法，而从河道到红色水晶又有3种走法，所以一共有 $3\times3=9$ 种走法。这就是乘法原理：如果做一件事情需要“分步进行”，那么总的方法数就等于把每一步骤的方法数乘在一起。

加法原理与乘法原理看着很简单，但复杂的排列组合就是从这两个原理开始的，我们要理解其本质：加法原理对应的是一种分类思想，而乘法原理对应的是一种分步思想，对于排列组合的难题我们一般都是采取先分类后分步的策略。

注：两种思想在数学中都很常见，之前有一篇《分类讨论》就详细讲解了运用分类讨论解题。

二、排列组合

介绍完计数原理那么我们就可以来讲讲排列组合了。首先是排列(Permutation)。请问从 $n$ 个人中挑选 $m$ 个人排成一排，有多少种方法数呢？

这里我们就可以运用乘法原理来计数，选出 $m$ 个人，也就有 $m$ 个位置，不妨一个一个位置来考虑：第一个位置有 $n$ 种选择；第二个位置有 $(n-1)$ 种选择；……第 $m$ 个位置有 $(n-m+1)$ 种选择。 所以一共有 $n\cdot (n-1)\cdot(n-2)\cdots(n-m+1)$ 种方法数，记为 $P_n^m$ 。

注：排列数有不同的表示方法，如 $A_n^m$ 等，不过表达的含义是一样的。

上面写的太复杂了，所以我们引入了阶乘(Factorial)：对于任一自然数 $n$ ， $n !=n(n-1)(n-2)(n-3) \dots \times 3 \times 2 \times 1$ ，并且规定 $0!=1$ .

注：这下4个0也可以算24点了， $(0!+0!+0!+0!)!=24$

所以计算式就可以简写为： $P_{n}^{m}=\frac{n !}{(n-m) !}$ 。特别的，当 $m=n$ 时，也就是 $n$ 个人全部排队，也叫做全排列， $P_n^n=n!$ 。接着考虑组合(Combination)。让我们再回到上面一个问题：请问从 $n$ 个人中挑选 $m$ 个人排成一排，有多少种方法数呢？前面我们是通过从整体出发一个位置一个位置的考虑得到了排列数，接下去可以换一种思路：我们先从 $n$ 个人中选出 $m$ 个人，然后再对这 $m$ 个人进行排列。因为完成的是同一件事情所以方法数肯定是相等的，且我们把从 $n$ 个人中选出 $m$ 个人记为 $C_n^m$ ,那么根据分步原理可知： $C_n^m\cdot P_m^m=P_n^m$ 于是， $C_{n}^{m}=\frac{n !}{(n-m) ! m !}$ 。

注：（1）组合数也有很多中表示方法，比如 $\left(\begin{array}{c}{n} \\ {m}\end{array}\right)$ ，但是含义是相同的；（2）排列是有顺序的，组合是没有顺序的，所以看问题时一定要考虑清楚。

三、恒等式

至此，我们已经把排列数与组合数计算公式都讲清楚了，接下去就是要讲排列组合中各种恒等式了。在前言中我们也讲了，本文主要是通过赋予恒等式具体含义来深入理解其成立原因，而不是通过带入排列数或组合数计算公式进行证明。所以关键的点不在于代数计算而是理解含义。 （1） $C_n^m=C_n^{n-m}$

左边表达的是从 $n$ 个人中选择 $m$ 个人参加活动；右边表示的是从 $n$ 个人中选择 $(n-m)$ 个人不参加活动。左右两式表示的都是同一件事情的方法数，所以相等。

这就是“算两次”的技巧，从不同角度去思考问题，因为是同一件事情所以得到的式子都是相等的。 （2） $P_{n}^{m}+m P_{n}^{m-1}=P_{n+1}^{m}$

右边表示的是从 $(n+1)$ 个人中选择 $m$ 个人进行排队；针对上述这件事，我们考虑 $(n+1)$ 中特定的一个人“小黑”的情况： 1）如果小黑不在这 $m$ 个人的队列中，那么有 $P_n^m$ 种方法； 2）如果小黑在这 $m$ 个人的队列中。那么先把小黑安置好，可以从 $m$ 个位置中任意选一个位置，然后再从剩下的 $n$ 个人中选择 $(m-1)$ 个人排到队伍中。因此总的方法数为 $m P_{n}^{m-1}$ 。根据加法原理，所以这件事总的方法数为 $P_{n}^{m}+m P_{n}^{m-1}$ ，得证。

这里我们通过对特定的人“小黑”进行分类讨论得到了同一件事情的总方法数的不同表达式，而接下去讲的恒等式都是用这种方法说明的。这有助于我们深入理解这些恒等式。 （3） $C_{n}^{m}+C_{n}^{m-1}=C_{n+1}^{m}$

右式表示的是从 $(n+1)$ 个人中选出 $m$ 个人；左式我们可以按照恒等式(2)进行类似的分类讨论，指定一个人“小黑”： 1）如果小黑在这 $m$ 个人中，那么再从 $n$ 个人中选 $(m-1)$ 个人； 2）如果小黑不在这 $m$ 个人中，那么就是从 $n$ 个人中选 $m$ 个人;根据加法原理，这件事总的方法数为： $C_{n}^{m}+C_{n}^{m-1}$ ，得证。

特别的，可以用恒等式(3)来证明： （3*） $C_{r}^{r}+C_{r+1}^{r}+\cdots+C_{n}^{r}=C_{n+1}^{r+1}$

因为 $1=C_r^r=C_{r+1}^{r+1}$ , 所以 $C_{r}^{r}+C_{r+1}^{r}=C_{r+1}^{r+1}+C_{r+1}^{r}=C_{r+2}^{r+1}$ （利用恒等式(3)）。接着 $C_{r+2}^{r+1}+C_{r+2}^r=C_{r+3}^{r+1}$ …… 依次下去，最后可得 $C_{n}^{r+1}+C_n^{r}=C_{n+1}^{r+1}$ ,得证。

（4） $C_{n}^{m+1}+C_{n}^{m-1}+2 C_{n}^{m}=C_{n+2}^{m+1}$

右式表示的是从 $(n+2)$ 个人中选出 $(m+1)$ 个人；与上面讨论类似，左边需要根据“小黑”、“小白”两个人的情况进行分类讨论： 1）小黑、小白都没有被挑选出来， $C_n^{m+1}$ ; 2）小黑、小白都被挑选出来了， $C_n^{m-1}$ ; 3）小黑、小白其中有一人被挑选出来了， $2 C_{n}^{m}$ 。所以，根据加法原理 $C_{n}^{m+1}+C_{n}^{m-1}+2 C_{n}^{m}$ ，得证。注：这里麻烦了一点，需要讨论两个人的情况，不过思想还是和前面一样的。按照这种想法我们能够造出很多很多的组合恒等式。

下面再来看一些稍微复杂的。 （5） $C_{n}^{r} \times C_{n-r}^{k-r}=C_{n}^{k} \times C_{k}^{r}$

下面考虑这样一件事的方案数： 在 $n$ 个人中有 $k$ 个人中奖，并且中奖的 $k$ 个人中有 $r$ 个人为特等奖； 右式是这样考虑的：先从 $n$ 个人中选择 $k$ 个人中奖，然后再从 $k$ 个人中选择 $r$ 个人为特等奖，根据乘法原理 $C_{n}^{k} \times C_{k}^{r}$ ；左式是这样考虑的：从 $n$ 个人先把特等奖的 $r$ 个人选出来，然后再选 $(k-r)$ 个中奖者，根据乘法原理 $C_{n}^{r} \times C_{n-r}^{k-r}$ 。因此左式等于右式。

（6） $C_{m}^{r} C_{n}^{0}+C_{m}^{r-1} C_{n}^{1}+\cdots+C_{m}^{0} C_{n}^{r}=C_{n+m}^{r}$

下面考虑这样一件事的方案数： 有黄、绿两支队伍，分别有 $n,m$ 个人，现在选拔 $r$ 个人组成新的一支蓝队。 右式是这样考虑的，先把两支队伍合在一起，一共 $(n+m)$ 个人，然后从中选出 $r$ 个人，所以方案数为 $C_{n+m}^{r}$ ；左式，既然有两支队伍，那么就根据两支队伍入选的人数进行分类讨论： 1）黄队入选 $0$ 个，绿队入选 $r$ 个， $C_{m}^{r} C_{n}^{0}$ ； 2）黄队入选 $1$ 个，绿队入选 $(r-1)$ 个， $C_{m}^{r-1} C_{n}^{1}$ ； …… 根据加法原理，一共有 $C_{m}^{r} C_{n}^{0}+C_{m}^{r-1} C_{n}^{1}+\cdots+C_{m}^{0} C_{n}^{r}$ 种方案数。因此左式等于右式。

特别的，当 $m=n$ 时有 $C_{n}^{r} C_{n}^{0}+C_{n}^{r-1} C_{n}^{1}+\cdots+C_{n}^{0} C_{n}^{r}=C_{n+n}^{r}=C_{2n}^r$ 又根据恒等式(1) $C_n^i=C_n^{n-i}$ ,所以下式成立： （6*） $\left(C_{n}^{0}\right)^{2}+\left(C_{n}^{1}\right)^{2}+\cdots+\left(C_{n}^{r}\right)^{2}=C_{2 n}^{r}$ （7） $C_{n}^{0}+C_{n}^{1}+\cdots+C_{n}^{n}=2^{n}$

下面考虑这样一个问题： 请问含 $n$ 个元素的集合 $\{x_1,x_2,\ldots,x_n\}$ 的子集有多少个？ 左边：我们可以按照子集中元素的个数进行分类讨论， 1）有0个元素的子集有 $C_n^0$ 个； 2）有1个元素的子集有 $C_n^1$ 个； …… 根据加法原理，子集一共有 $C_{n}^{0}+C_{n}^{1}+\cdots+C_{n}^{n}$ 个。右边：我们也可以按照每个元素进行讨论，对于每一个元素而言它都有两种选择：属于这个子集与不属于这个子集，所以根据乘法原理， $2\times2\times\cdots\times2=2^n$ 。因此，左式等于右式。

总结

组合恒等式还有很多，比如 $C_{n}^{1}+2 C_{n}^{2}+\cdots+n C_{n}^{n}=n 2^{n-1}$ ，但是这个暂时还没有想到如何用一个具体问题来理解它。

注：上述恒等式的代数证明会用到： $m C_{n}^{m}=n C_{n-1}^{m-1}$ 。于是， $C_{n}^{1}+2 C_{n}^{2}+\cdots+n C_{n}^{n}=nC_{n-1}^0+nC_{n-1}^1+\cdots+nC_{n-1}^{n-1}=n2^{n-1}$ (根据恒等式(7))

如果我们拿到恒等式后能够想想它的“含义”还挺有趣的，就像在第三部分给出的那样，不仅能够加深我们对排列组合的理解还能够锻炼思维、拓展思路。比较直接的影响就是：做题的时候如果认识这个恒等式，那会方便不少。比如：

根据 $C_{n}^{1}+2 C_{n}^{2}+\cdots+n C_{n}^{n}=n 2^{n-1}$ ，所以 $\sum_{k=1}^{2008} k\left(\begin{array}{c}{2008} \\ {k}\end{array}\right)=2008 \cdot 2^{2007}$ 。那么问题就变成问 $2008 \cdot 2^{2007}$ 的最后两位是多少，就是一个很纯粹的数论取余的问题了： $2008 \cdot 2^{2007}\equiv ？(mod~100)$ 因为 $\begin{aligned} 2^{20} & \equiv 1(\bmod 25) \\ 2^{2007} \equiv & 2^{7} \equiv 3(\bmod 25) \\ 2^{2007} & \equiv 0(\bmod 4) \\ 2^{2007} & \equiv 28(\bmod 100) \end{aligned}$ 所以， $2008 \times 28 \equiv\boxed{24}(\bmod 100)$ 注：数论的内容我们之后再分享。

有兴趣的可以思考下面这个恒等式，怎么样给它一个合理的解释呢？ $C_{n}^{1}+2 C_{n}^{2}+\cdots+n C_{n}^{n}=n 2^{n-1}$ 感谢的评论：

可以把上面式子两边都除以 $2^n$ $\frac{C_{n}^{1}+2 C_{n}^{2}+\cdots+n C_{n}^{n}}{2^n}=\frac{n 2^{n-1}}{2^n}=\frac{n}{2}$ 那么左式为 $n$ 元集合子集元素个数的平均数；而右边对于单个元素而言“在子集中”与“不在子集中”的概率都为 $\frac{1}{2}$ ,所以子集中元素个数平均数为 $\frac{n}{2}$ .

感觉挺有道理的，不知道大家觉得如何？