为您整理了该恒等式（在组合数学中常被称为牛顿恒等式或三项式修正恒等式）的两种经典证明方法：代数展开法与组合计数（双重计数）法。

为了与您之前的变量习惯相对应，这里我们证明以下形式： $$C_M^N \cdot C_N^K = C_M^K \cdot C_{M-K}^{N-K} \quad (M \ge N \ge K \ge 0)$$

方法一：代数展开法（利用阶乘定义）

这是最直接、最严谨的代数证明方法，通过将组合数展开为阶乘形式进行化简。

证明步骤：

根据组合数的阶乘定义 $C_n^m = \frac{n!}{m!(n-m)!}$，我们将等式左边（LHS）展开：

$$\text{LHS} = C_M^N \cdot C_N^K = \frac{M!}{N!(M-N)!} \cdot \frac{N!}{K!(N-K)!}$$

观察分子和分母，可以发现 $N!$ 可以直接约去：

$$\text{LHS} = \frac{M! \cdot \color{red}{N!}}{\color{red}{N!}(M-N)! \cdot K!(N-K)!} = \frac{M!}{(M-N)! \cdot K!(N-K)!}$$

为了凑出等式右边的结构，我们在分子和分母中同时乘以 $(M-K)!$：

$$\text{LHS} = \frac{M!}{K!(M-K)!} \cdot \frac{(M-K)!}{(M-N)!(N-K)!}$$

由于 $(M-K) - (N-K) = M-N$，我们可以将上式分母中的 $(M-N)!$ 改写为 $((M-K)-(N-K))!$：

$$\text{LHS} = \underbrace{\frac{M!}{K!(M-K)!}}_{C_M^K} \cdot \underbrace{\frac{(M-K)!}{(N-K)! \cdot ((M-K)-(N-K))!}}_{C_{M-K}^{N-K}}$$

根据组合数的定义，这两部分正好对应右边的两个组合数：

$$\text{LHS} = C_M^K \cdot C_{M-K}^{N-K} = \text{RHS}$$

证毕。

方法二：组合计数法（双重计数法）

这种方法通过“用两种不同的视角去数同一件东西”来证明等式。相比代数计算，它能更直观地揭示公式背后的物理/逻辑意义。

证明步骤：

假设我们要解决这样一个实际的选人问题：

从 $M$ 个候选人中，选出一个由 $N$ 人组成的“委员会”，并且在这个委员会中，还要进一步选出 $K$ 人作为“常务委员”（其中 $M \ge N \ge K$）。

我们从两个不同的视角来计算选择的总方案数：

• 视角 A（先选委员会，再选常委）：
• 第一步：先从 $M$ 个候选人中挑选出 $N$ 个委员会成员，共有 $C_M^N$ 种选法；
• 第二步：从这选好的 $N$ 个委员会成员中，挑选出 $K$ 人作为常委，共有 $C_N^K$ 种选法。

根据乘法原理，总的挑选方案数为： $$\text{方案数} = C_M^N \cdot C_N^K$$

• 视角 B（先选常委，再选剩余的委员）：
• 第一步：直接先从 $M$ 个候选人中挑出那 $K$ 个核心的常委，共有 $C_M^K$ 种选法；
• 第二步：常委确定后，此时还剩下 $M-K$ 个候选人，而我们还需要 $N-K$ 个普通委员来凑齐 $N$ 人的委员会。因此从剩下的候选人中选普通委员，共有 $C_{M-K}^{N-K}$ 种选法。

根据乘法原理，总的挑选方案数为： $$\text{方案数} = C_M^K \cdot C_{M-K}^{N-K}$$

因为视角 A 和 视角 B 计算的是同一个选人事件的所有可能结果，所以两种算法得到的方案数必然相等，即： $$C_M^N \cdot C_N^K = C_M^K \cdot C_{M-K}^{N-K}$$

证毕。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com