火龙信奥
  • 首页
  • 课程
  • 题库
  • 打卡
    • 代码对战
    • 快速对战
  • 题单
  • 团队
  • 荣誉墙
  • 商城
  • 登录 / 注册

组合数学恒等式,反演推导

作者: 作者的头像   huolong , 时间:2026-06-19 10:15:20 , 所有人可见, 阅读  20

$\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}$ 的含义:

  1. 先选池子:你先从 $j$ 个球里随便挑出 $i$ 个球出来,放到一个“候选池”里(剩下的 $j-i$ 个球直接淘汰)。这一步的方法数是 $\binom{j}{i}$。
  2. 再选大奖:然后,你从这个包含 $i$ 个球的“候选池”里,再挑出 $n$ 个球作为最终的“大奖”。这一步的方法数是 $\binom{i}{n}$。
  3. 结果:最终,你手里的 $n$ 个大奖球,必然全部来自那 $i$ 个候选球。

右边 $\binom{j}{n} \cdot \binom{j-n}{j-i}$ 的含义:

  1. 先定大奖:你先直接从 $j$ 个球里挑出那 $n$ 个最终的“大奖”球。这一步的方法数是 $\binom{j}{n}$。
  2. 反向选淘汰者:现在你需要确定那 $i$ 个“候选球”是谁。因为大奖必须在候选池里,所以这 $n$ 个大奖绝对不能被淘汰。
  3. 剩下的 $j-n$ 个非大奖球中,你需要选出 $j-i$ 个球去“淘汰”(因为总共要淘汰 $j-i$ 个球,且这 $j-i$ 个球必须从非大奖球里选,否则大奖就被误杀了)。
  4. 从 $j-n$ 个非大奖球里选 $j-i$ 个去淘汰,方法数是 $\binom{j-n}{j-i}$。
  5. 结果:剩下的 $i$ 个球($j - (j-i) = i$)自然就构成了候选池,且包含了所有大奖。

结论

无论是“先选池子再选奖”(左边),还是“先选奖再选淘汰者”(右边),最终达成的结果状态是一样的:你确定了哪 $n$ 个是大奖,以及哪 $i$ 个是候选(包含大奖)。因此两边计数相等。

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

©2026加盟我们 | 关于我们 | ACM课程 | 常见问题 | 成果墙 | 评测记录 | 浙ICP备2021013995号
在线画图 | OI WIki | 打字练习
火龙信奥
请输入登录信息


请完成安全验证
验证码底图 滑块
向右拖动滑块完成验证
请输入用户名 / 绑定的手机号码



请输入注册信息(手机号验证码注册)





验证码5分钟有效,60秒内不可重复获取,每日最多3次

微信登录

微信登录二维码

正在生成二维码...

账号已过期,请续期。
去续期

绑定手机号

📱

为了更好地保护您的账号安全,享受完整的平台服务

请您尽快绑定手机号码