2022-09-19 13:48:31
浏览数 (3)
二项式系数 Binomial Coefficients
1.1 基本恒等式 Basic Identities
1.1.1 定义 Definition
binom nk 表示二项式系数，其中 n 称作上指标 (upper index)，而称 k 为下指标 (lower index)。
1.1.2 对称恒等式 Symmetric Identity
证明：
binom nk=frac{n!}{k!(n-k)!}=frac{n!}{(n-(n-k))!(n-k)!}=binom n{n-k}1.1.3 吸收恒等式 Absorption Identity
binom rk=frac rkbinom {r-1}{k-1}证明：
- k> 0
- k<0
binom rk = 0 = binom {r-1}{k-1}1.1.3 相伴恒等式 Companion Identity
(r-k)binom rk=rbinom {r-1}k证明：
begin{aligned}(r-k)binom rk & =(r-k)binom r {r-k}\& = rbinom {r-1}{r-k-1}\& = rbinom {r-1}kend{aligned}1.1.4 加法公式 Addition Formula
binom rk = binom {r-1}k binom {r-1}{k-1}证明：
rbinom rk=(r-k)binom rk kbinom rk=rbinom {r-1}k rbinom {r-1}{k-1}1.1.5 上指标求和 Summation of Upper Indicators
证明：
利用数学归纳法。
n=0 时，左边 =binom 0m=[m=0]=binom 1{m 1}= 右边
时，
begin{aligned}sum_{0leq kleq n 1}binom km & =sum_{0leq kleq n}binom km binom {n 1}m\& = binom {n 1}{m 1} binom {n 1}m\& = binom {n 2}{m 1}end{aligned}所以对一切
，(1) 成立。
1.1.6 平行求和法 Parallel Summation
证明：
begin{aligned}sum_{kleq n}binom {m k}k & =sum_{-mleq kleq n}binom {m k}k\& = sum_{-mleq kleq n}binom {m k}m\& = sum_{0leq kleq m n}binom km\& = binom {m n 1}{m 1}end{aligned}注意到以上证明当且仅当 m kge 0 才可以这么做（第二行运用到对称法则），因此我们在第一步去掉了 k<-m
1.1.7 上指标反转 Upper Negation
证明：
- kge 0
$binom rk=frac{r^{underline k}}{k!}=frac{(-1)^k (-r)(1-r)cdots (k-1-r)}{k!}=frac {(-1)^k(k-r-1)^{underline k}}{k!}=(-1)^kbinom {k-r-1}k- k<0
binom rk = 0 = (-1)^kbinom {k-r-1}k1.1.8 三项式版恒等式 Trinomial Version of Identity
证明：
，
begin{aligned}binom rmbinom mk & = frac{r!}{m!(r-m)!}frac{m!}{k!(m-k)!} \& = frac{r!}{k!(m-k)!(r-m)!}\& = frac{r!}{k!(r-k)!}frac{(r-k)!}{(m-k)!(r-m)!}\& = binom rk binom {r-k}{m-k}end{aligned}若 m<kk<00。
1.1.9 范德蒙德卷积 Vandermonde Convolution
证明：
这里可以暂时通过组合意义来简单证明：
先从 r 个球中取 m k 个，再从 s 个球中取 n-k 个，就相当于在 r s 个球中取 m n 个。
具体严谨证明见下文——生成函数。
1.1.10 二项式定理 Binomial Theorem
(x y)^n=sum_{k=0}^nbinom nky^kx^{n-k}quad nin Z_ 特别地，
(1 x)^n=sum_{k=0}^nbinom nkx^kquad nin Z_ 1.1.11 其他基本组合恒等式 Other Basic Combination Identities
sum_{k=0}^n binom nk=2^n tag 1sum_{k=0}^n (-1)^kbinom nk=0 tag 21.2 生成函数 Generating Function
1.2.1 卷积 Convolution
c_n=sum_{k=0}^na_kb_{n-k} tag1由 (1) 所定义的序列 langle c_nrangle 称为序列 langle a_nrangle 和 langle b_n rangle 的卷积。
1.2.2 二项式定理与生成函数 Binomial Theorem and Generating Function
(1 z)^r=sum_{kge 0}binom rkz^k tag1类似地，
(1 z)^s=sum_{kge 0}binom skz^k tag2将 (1)(2) 相乘，我们可以得到另外一个生成函数：
(1 z)^r(1 z)^s=(1 z)^{r s}让这个等式两边 z^n 的系数相等就给出：
sum_{k=0}^nbinom rkbinom s{n-k}=binom {r s}n我们就发现了范德蒙德卷积。
此外我们还有一系列重要的恒等式：
(1-z)^r=sum_{kge 0}(-1)^kbinom rktag 3
当 n=0 时，我们就得到了 (4) 的特例，即几何级数：
frac 1{1-z}=1 z z^2 z^3 cdots =sum_{kge 0}z^k这就是序列 langle 1,1,1,cdots rangle 的生成函数。
1.3 基本练习 Basic Practice
1.3.1 利用基本组合恒等式 Use Basic Combinatorial Identities
- 证明：sum_{k=1}^n (-1)^{k-1}kbinom nk=0 (nge2)
begin{aligned}LHS & = sum_{k=1}^n(-1)^{k-1}nbinom {n-1}{k-1} \& = nsum_{k}(-1)^kbinom nk\& = nbinom 0n\& = n[n=0]\& = 0 = RHSend{aligned}- 证明：sum_{k=p}^nbinom nkbinom kp=binom np2^{n-p}
begin{aligned}LHS & = sum_{k=p}^nbinom npbinom {n-k}{k-p}\& = binom npsum_{k=0}^{n-p}binom {n-p-k}k\& = binom np 2^{n-p} = RHSend{aligned}1.3.2 利用生成函数 Use Generating Functions
- 证明：
- sum_{k=0}^n{binom nk}^2=binom n{2n}
- sum_{k=1}^{2n-1}binom {2n}k[2 (k-1)]=frac 12{binom {4n}{2n} (-1)^{n-1}binom {2n}n}
[collapse title=”解答”] 1. 首先有：
begin{aligned} [z^n](1 z)^{2n} & =sum_{k=0}^{2n}binom {2n}kz^k\ & =binom {2n}n end{aligned} begin{aligned} [z^n](1 z)^{2n} & =[z^n]((1 z)^n)^2\ & = [z^n](sum_{i=0}^nbinom niz^i)cdot (sum_{j=0}nbinom njz^j)\ & =sum_{k=0}^nbinom nkbinom n{n-k}\ & =sum_{k=0}^n{binom nk}^2 end{aligned} sum_{k=0}^n{binom nk}^2=binom {2n}n 2. 由小题 得：
sum_{k=0}^{2n}binom {2n}k^2=binom {4n}{2n}tag1 其次：
begin{aligned} [z^{2n}](1-z^2)^{2n} & =[z^{2n}]sum_{k=0}^{2n}(-1)^kbinom {2n}kz^{2k}\ & =(-1)^nbinom {2n}n end{aligned} begin{aligned} [z^{2n}](1-z^2)^{2n} & =(1-z)^{2n}(1 z)^{2n}\ & = [z^{2n}](sum_{k=0}^{2n}(-1)^kbinom {2n}kz^k)(sum_{j=0}^{2n}binom {2n}jz^j)\ & = sum_{k=0}^{2n}(-1)^kbinom {2n}kbinom {2n}{2n-k}\ & = sum_{k=0}^{2n}(-1)^kbinom {2n}k^2 end{aligned} (-1)^nbinom {2n}n=sum_{k=0}^{2n}(-1)^kbinom {2n}k^2 tag 2 由 得：
sum_{k=1}^nbinom {2n}{2k-1}^2=frac 12{binom {4n}{2n} (-1)^{n-1}binom {2n}n} [/collapse]
