二项式系数 | Codeboy's Blog

形式陈述

对整数 $n\ge0$ $n \geq 0$ 与 $0\le k\le n$ $0 \leq k \leq n$ ，定义

$$ \binom nk=\left|\left\{C\subseteq\{1,\ldots,n\}:|C|=k\right\}\right|. $$

(\binom{n}{k}) = | {C \subseteq {1, \dots, n} : | C | = k} | .

按先排列所选元素、再消除其内部次序可得

$$ \binom nk=\frac{n!}{k!(n-k)!}. $$

(\binom{n}{k}) = \frac{n!}{k! (n - k)!} .

通常约定 $k<0$ $k < 0$ 或 $k>n$ $k > n$ 时 $\binom nk=0$ $(\binom{n}{k}) = 0$ 。

直觉

二项式系数测量“从 $n$ $n$ 个互异对象中无序选出 $k$ $k$ 个”的结果数；分母中的 $k!$ $k!$ 正好消除同一子集的不同列举顺序。

例子与边界

从五人中选两人共有 $\binom52=10$ $(\binom{5}{2}) = 10$ 种。$\binom nk=\binom n{n-k}$ $(\binom{n}{k}) = (\binom{n}{n - k})$ ，因为选中 $k$ $k$ 人与排除其余 $n-k$ $n - k$ 人一一对应。公式针对互异对象且不重复选择；含重复对象的排列或可重复抽取需要不同计数。

推论与应用

按某个固定元素是否被选中可得 Pascal 恒等式

$$ \binom nk=\binom{n-1}{k}+\binom{n-1}{k-1}. $$

(\binom{n}{k}) = (\binom{n - 1}{k}) + (\binom{n - 1}{k - 1}) .

二项式系数还出现在二项式定理、Bernoulli 试验、子集枚举和组合概率中。

参考资料

Eric Lehman, F. Thomson Leighton, and Albert R. Meyer, Mathematics for Computer Science, rev. 2018, §§15.5–15.6.
Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th ed., McGraw-Hill, 2019, §6.4.

形式陈述 ​

直觉 ​

例子与边界 ​

推论与应用 ​

形式陈述

直觉

例子与边界

推论与应用