$\binom{j}{i} \cdot \binom{i}{n} = \binom{j}{n} \cdot \binom{j-n}{j-i}$
方法二:组合意义证明(抽球模型)
这种方法更直观,通过构建一个实际的“选人”或“抽球”场景来解释为什么两边相等。
场景设定: 假设你有一个袋子,里面有 $j$ 个互不相同的球(编号 1 到 $j$)。你要从中选出 $n$ 个球作为“大奖”,但是规则比较特殊。
左边 $\binom{j}{i} \cdot \binom{i}{n}$ 的含义:
- 先选池子:你先从 $j$ 个球里随便挑出 $i$ 个球出来,放到一个“候选池”里(剩下的 $j-i$ 个球直接淘汰)。这一步的方法数是 $\binom{j}{i}$。
- 再选大奖:然后,你从这个包含 $i$ 个球的“候选池”里,再挑出 $n$ 个球作为最终的“大奖”。这一步的方法数是 $\binom{i}{n}$。
- 结果:最终,你手里的 $n$ 个大奖球,必然全部来自那 $i$ 个候选球。
右边 $\binom{j}{n} \cdot \binom{j-n}{j-i}$ 的含义:
- 先定大奖:你先直接从 $j$ 个球里挑出那 $n$ 个最终的“大奖”球。这一步的方法数是 $\binom{j}{n}$。
- 反向选淘汰者:现在你需要确定那 $i$ 个“候选球”是谁。因为大奖必须在候选池里,所以这 $n$ 个大奖绝对不能被淘汰。
- 剩下的 $j-n$ 个非大奖球中,你需要选出 $j-i$ 个球去“淘汰”(因为总共要淘汰 $j-i$ 个球,且这 $j-i$ 个球必须从非大奖球里选,否则大奖就被误杀了)。
- 从 $j-n$ 个非大奖球里选 $j-i$ 个去淘汰,方法数是 $\binom{j-n}{j-i}$。
- 结果:剩下的 $i$ 个球($j - (j-i) = i$)自然就构成了候选池,且包含了所有大奖。
结论
无论是“先选池子再选奖”(左边),还是“先选奖再选淘汰者”(右边),最终达成的结果状态是一样的:你确定了哪 $n$ 个是大奖,以及哪 $i$ 个是候选(包含大奖)。因此两边计数相等。
—— 本文来自火龙信奥(义乌睿码科技):义乌青少年信息学奥赛与编程教育平台,专注 CSP-J/S、NOIP、GESP 竞赛培训,线上线下融合教学,助力编程升学。网址:hlcoding.com