二项式系数 Binomial Coefficients

2022-09-19 13:48:31 浏览数 (16)

二项式系数 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}

证明：

  1. k> 0
  2. 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

证明：

  1. 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
  1. k<0
binom rk = 0 = (-1)^kbinom {k-r-1}k

1.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 1
sum_{k=0}^n (-1)^kbinom nk=0 tag 2

1.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

  1. 证明：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}
  1. 证明：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

  1. 证明：
  2. sum_{k=0}^n{binom nk}^2=binom n{2n}
  3. 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]

function identity sum

1 人点赞