二项式定理与基本恒等式

cqbzlzm · 2023-08-07 23:17:11 · 算法·理论

二项式系数与帕斯卡三角

二项式系数：符号\dbinom{n}{k}叫做二项式系数，可以表示从n个元素的集合中选k个元素作为自己的方案数，相当于组合数。

帕斯卡三角：即杨辉三角，帕斯卡三角形的第n行第k列表示\dbinom{n}{k}

如图：许多将使用到帕斯卡三角作为辅助

基本恒等式

0）

{\dbinom{n}{k} }=\frac{ n! }{ k!(n-k)! }

最基本的定义计算式

1) 对称恒等式

{ \dbinom{n}{k} }={ \dbinom{n}{n-k} }

从n个数中选k个，相当于选出剩下的n-k个

2）吸收恒等式

当一个变量在二项式系数外成为累赘时，常常用这两个公式将外面的变量"吸收"到二项式系数里面，故称吸收恒等式

式1：

{ \dbinom{n}{k} }=\frac{n}{k}\dbinom{n-1}{k-1}

代入公式计算

式2：

{ \dbinom{n}{k} }=\frac{n}{n-k}\dbinom{n-1}{k}

一样代入公式计算即可

3）加法(Pascal)公式

{ \dbinom{n}{k} }=\dbinom{n-1}{k}+\dbinom{n-1}{k-1}

代入公式计算。

组合意义：从n个球中取k个，考虑最后一个球选不选，选就是\dbinom{n-1}{k-1}，不选就是\dbinom{n-1}{k}

4) 变下指标求和

简单和： （帕斯卡三角形第n行求和）

\sum_{k=0}^n\dbinom{n}{k}=2^n

从n个球中任意选取1个，2个......n个，即任意选，所以每一位可以选或不选，即为2^n

交错和：

\sum_{k=0}^n{(-1)^k { \dbinom{n}{k} } }=0

证明：

\sum_{ k=0 }^n { (-1)^k { \dbinom{n}{k} } }=\sum{k=0}^n{ (-1)^k { 1 }^{n-k}{ \dbinom{n}{k} } } =(1-1)^n=0

5）变上指标求和

（帕斯卡三角形列求和）

\sum_{i=0}^n{ { \dbinom{i}{k} } }={ \dbinom{n+1}{k+1} }

从n+1选k+1个，枚举最后一个数的位置，从前面位置选k个，即为左式

或：

用加法（Pascal）公式不断拆分，最终拆分为黑框中的元素的和。形式化解释如图

6）上下指标保持同差值求和

（帕斯卡三角形对角线求和）

\sum_{k=0}^n{ \dbinom{k+r}{k} }={ \dbinom{r+n+1}{n} }

证明：

\sum_{k=0}^n{ \dbinom{k+r}{k} }=\sum_{k=0}^n{ \dbinom{k+r}{r} }={ \dbinom{r+n+1}{n} }

先变成下指标不变的式子，再用公式求和、

或：

形式化解释如图

7）上指标反转

{ \dbinom{n}{k} }=(-1)^k{ \dbinom{k-n-1}{k} }

{\dbinom{n}{k} }=\frac{n!}{k!(n-k)!}=\frac{ n\times (n-1)\times ...\times(n-k+1)}{ k! }

(-1)^k{ \dbinom{k-n-1}{k} }=(-1)^k\frac{ (k-n-1)\times(k-n-2)\times...\times (k-n-k) }{k!}=\frac{(n-k+1)\times(n-k+2)\times...\times(n-k+k)}{k!}

上面两个式子化简出来是一样的，所以得证。

特别注意到这个式子里面有一个(-1)^k，所以有很多套路。

例子：

求\sum_{k\leq m}{\dbinom{n}{k}(-1)^k}。

解法：

如果式子里面没有(-1)^k，那么式子就是一个帕斯卡三角形的行求和，这是没有固定公式的。

但是出现了(-1)^k，那么我们就可以用上指标反转，

\sum_{k\leq m}{\dbinom{n}{k}(-1)^k}=\sum_{k\leq m}{\dbinom{k-n-1}{k}}

发现这个式子上下都有k，所以上下保持一个相同的差值在变化，即帕斯卡三角形的对角线求和

所以

\sum_{k\leq m}{\dbinom{n}{k}(-1)^k}=\sum_{k\leq m}{\dbinom{k-n-1}{k}}=\dbinom{m-n}{m}