具体数学笔记（第五章二项式系数）

有意思的来了，狂喜基本恒等式(nk)=(nn−k),n≥0,k为整数\binom{n}{k}=\binom{n}{n-k},n\ge0,k为整数(kn)=(n−kn),n≥0,k为整数限制一定要记得，n为负数的时候是不成立的(nk)=nk(n−1k−1) 同样可以得到k(nk)=n(n−1k−1)\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-

lahlah_

1196人浏览 · 2021-08-16 13:52:28

lahlah_ · 2021-08-16 13:52:28 发布

~~有意思的来了，狂喜~~

基本恒等式

$(nk)=(nn−k),n≥0,k为整数\binom{n}{k}=\binom{n}{n-k},n\ge0,k为整数$
限制一定要记得，n为负数的时候是不成立的
$同样可以得到k(nk)=n(n−1k−1)\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1} \\ ~~ \\ 同样可以得到k\binom{n}{k}=n\binom{n-1}{k-1}$
平行求和法：
$∑k=0m(n+kk)=(n+m+1m)\sum_{k=0}^m\binom{n+k}{k}=\binom{n+m+1}{m}$
上指标求和：
$∑k=0n(km)=(n+1m+1)\sum_{k=0}^n\binom{k}{m}=\binom{n+1}{m+1}$
上指标反转：
$(nk)=(−1)k(k−n−1k)\binom{n}{k}=(-1)^k\binom{k-n-1}{k}$
利用上指标反转，可以推出
$∑k=0m(nk)(−1)k=(−1)m(n−1m)\sum_{k=0}^m\binom{n}{k}(-1)^k=(-1)^m\binom{n-1}{m}$
还有其他有趣的恒等式（证明略，都可以用归纳法/大力拆/手撕组合意义）
$∑k=0m(nk)(n2−k)=m+12(nm+1)\sum_{k=0}^m \binom{n}{k}(\frac{n}{2}-k)=\frac{m+1}{2}\binom{n}{m+1}$

$(nm)(mk)=(nk)(n−km−k)\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k}$
二项式系数可以推广到三项式甚至多项式系数
$(x+y+z)n=∑(a+b+c)!a!b!c!xaybzc=∑(a+b+cb+c)(b+cc)xaybzc(x+y+z)^n=\sum\frac{(a+b+c)!}{a!b!c!}x^ay^bz^c=\sum\binom{a+b+c}{b+c}\binom{b+c}{c}x^ay^bz^c$
$=(a1+a2+a3+...+ama1)(a2+a3+...+ama2)...(am−1+amam−1)\frac{(a_1+a_2+a_3+...+a_m)!}{a_1!a_2!a_3!....a_m!} \\ ~~ \\= \binom{a_1+a_2+a_3+...+a_m}{a_2+a_3+...+a_m}\binom{a_2+a_3+...+a_m}{a_3+a_4+...+a_m}...\binom{a_{m-1}+a_m}{a_m}\\ ~~\\=\binom{a_1+a_2+a_3+...+a_m}{a_1}\binom{a_2+a_3+...+a_m}{a_2}...\binom{a_{m-1}+a_m}{a_{m-1}}$
范德蒙德卷积：
$∑k(rk)(sn−k)=(r+sn)\sum_k\binom{r}{k}\binom{s}{n-k}=\binom{r+s}{n}$
可以通过手撕组合意义证明
最恐怖的二项式恒等式：
$∑kij(−1)∑i<jkij(∏1≤i<j<n(ai+ajaj+kij))(∏1≤j<n((aj+anan+∑i<jkij−∑i>jkij)))\sum_{k_{ij}}(-1)^{\sum_{i<j}k_{ij}}\left(\prod_{1 \le i < j<n}\binom{a_i+a_j}{a_j+k_{ij}}\right)\left(\prod_{1\le j<n}\left(\binom{a_j+a_n}{a_n+\sum_{i<j}k_{ij}-\sum_{i>j}k_{ij}}\right)\right)$
~~RNM,退钱!!~~
其实带入特殊值后发现还挺好记的，如把 $n = 4$ 带入得
$∑i,j,k(−1)i+j+k(a+bb+i)(a+cc+j)(b+cc+k)(a+dd−i−j)(b+dd+i−k)(c+bd+j+k)=(a+b+c+d)!a!b!c!d!\sum_{i,j,k}(-1)^{i+j+k}\binom{a+b}{b+i}\binom{a+c}{c+j}\binom{b+c}{c+k}\binom{a+d}{d-i-j}\binom{b+d}{d+i-k}\binom{c+b}{d+j+k}\\=\frac{(a+b+c+d)!}{a!b!c!d!}$
~~好记个p~~
重要的二项式系数恒等式：
就是上面几个看起来比较短的就是

5.3 处理的技巧

高阶差分：
可以发现， $(nk)(−1)k\binom{n}{k}(-1)^k$ 可以计算部分和而 $(nk)\binom{n}{k}$ 不行
其中的一个原因是与差分算子 $Δ\Delta$ 有关
容易发现高阶差分与二项式系数有关
$Δnf(x)=∑k(nk)(−1)n−kf(x+k)\Delta^nf(x)=\sum_k\binom{n}{k}(-1)^{n-k}f(x+k)$

通常幂可以转换成下降幂，进而可以得到所有的多项式都可以表示成二项式系数倍数之和，这样的一个展开式称为牛顿级数
有时候对一个多项式如果无从下手可以考虑利用n阶差分

牛顿级数是有限微积分对无限微积分中的泰勒级数的回应
反演：
$f(n)=∑k(nk)(−1)kg(k)g(n)=\sum_k\binom{n}{k}(-1)^kf(k) \iff f(n)=\sum_k\binom{n}{k}(-1)^kg(k)$

可用于解决错排问题，这里直接给出封闭形式
$Dn=⌊n!e+12⌋+[n=0]D_n=\lfloor \frac{n!}{e}+\frac{1}{2}\rfloor+[n=0]$

5.4 生成函数

~~终于来了，狂喜~~

我们考虑二项式系数的生成函数
$(1+x)r=∑k=0r(rk)xk(1+x)^r=\sum_{k=0}^r\binom{r}{k}x^k$
类似地
$(1+x)s=∑k=0s(sk)xk(1+x)^s=\sum_{k=0}^s\binom{s}{k}x^k$
把这两个东西乘在一起
$1+x)^{r+s}$
把两边都的第 $n$ 次项系数提出
$∑k=0n(rk)(sn−k)=(r+sn)\sum_{k=0}^n\binom{r}{k}\binom{s}{n-k}=\binom{r+s}{n}$
这样我们就得到了范德蒙德卷积
ohhhhhhhhhhh

两个重要的恒等式：
$1(1−x)n+1=∑k=0(n+kn)xk\frac{1}{(1-x)^{n+1}}=\sum_{k=0}\binom{n+k}{n}x^k$
$xn(1−x)n+1=∑k=0(kn)xk\frac{x^n}{(1-x)^{n+1}}=\sum_{k=0}\binom{k}{n}x^k$
证明也不难
第一个用二项式定理展开 $1-x)^{-n-1}$ 可以得到第 $k$ 项第系数为 $(−n−1k)(−1)k\binom{-n-1}{k}(-1)^k$ 然后我们将它的上指标反转，就可以得到 $(k+nk)\binom{k+n}{k}$ 或 $(k+nn)\binom{k+n}{n}$ 了