知识库
二项式定理与组合恒等式
LaTeX
$$(1+x)^n=\sum_{k=0}^n\binom nkx^k.$$
代入特殊值:
- $x=1$:$\sum_k\binom nk=2^n$——$n$ 个元素的子集一共 $2^n$ 个,每个元素选或不选;
- $x=-1$:$\sum_k(-1)^k\binom nk=0$($n\ge1$)——偶数大小的子集和奇数大小的子集一样多。
每个代数恒等式都可以换成一个计数论证:两边数的是同一个集合。把 $(1+x)^n$ 看成 生成函数,系数恒等式就是多项式乘法的结果。
更多常用恒等式
| 内容 | 结论 |
|---|---|
| 二项式平方和 | $\sum_{k=0}^n\binom nk^2=\binom{2n}{n}$ |
| Vandermonde | $\sum_{k=0}^{r}\binom mk\binom n{r-k}=\binom{m+n}{r}$ |
| Hockey-stick | $\sum_{k=r}^n\binom kr=\binom{n+1}{r+1}$ |
二项式平方和是 Vandermonde 取 $m=n=r$ 再用 $\binom n{n-k}=\binom nk$。组合解释:从两组各 $n$ 个元素里一共选 $n$ 个,可以直接选,也可以先定第一组选几个。Vandermonde 本身就是 $(1+x)^m(1+x)^n=(1+x)^{m+n}$ 比较 $x^r$ 的系数——卷积。
常见的连接方式:对 $(1+x)^n$ 求导得到 $\sum k\binom nkx^{k-1}$;指数生成函数处理带阶乘的和;差分推 $\sum k^m$(见 幂和与 Bernoulli 数);部分分式裂项处理有理式求和。
核对
这一条是文字讲解,由 AI 整理,没有可以数值核对的步骤;作者读过后才公开。