「学习笔记」二项式定理及其的扩展

· · 个人记录

五一假期过来写学习笔记，乐。

话不多说，直接步入主题吧。

二项式系数

就是像 \dbinom{n}{m} 这样的东西。

对于非负整数 n,k，规定 \dbinom{n}{0}=1 及 \dbinom{n}{n}=1，k>n 则 \dbinom{n}{k}=0，1 \le k \le n 且 n 为正整数，则 \dbinom{n}{k}=\dfrac{n!}{k!(n-k)!}。

我们知道 \dbinom{n}{m}=\dfrac{n!}{m!(n-m)!}，那么显然可以得出 \dbinom{n}{m}=\dfrac{n(n-1)...(n-m+1)}{m!}，还有 \dbinom{n}{m}=\dbinom{n}{n-m}。

二项式定理

对于一个非负整数 n，(x+y)^n=x^n+\binom{n}{1}x^{n-1}y+\binom{n}{2}x^{n-2}y^2+...+\binom{n}{n-1}xy^{n-1}+y^n，用求和符号表示就是 (x+y)^n=\sum\limits_{k=0}^n\binom{n}{k}x^{n-k}y^k。

在初一我们一定学过 (x+y)^2=x^2+2xy+y^2，这其实就是二项式定理的一个特殊形式。

假设 y=1，则可得 (x+1)^n=\sum\limits_{k=0}^n\binom{n}{k}x^k。

这个东西在证明卢卡斯定理时会用到。

杨辉三角（帕斯卡三角形）

杨辉三角就是像下面这样的东西：

   0  1  2  3  4  5  6 
  ---------------------
0 |1
1 |1  1
2 |1  2  1
3 |1  3  3  1
4 |1  4  6  4  1
5 |1  5 10 10  5  1
6 |1  6 15 20 15  6  1
......

（边框上的是坐标）

我们规定只有一个 1 的是第 0 行，1 1 是第 1 行，1 2 1 是第 2 行，以此类推。（但是我看百度百科上说 1 是第 1 行，在这里就当第 0 行算QWQ）

杨辉三角每行端点与结尾的数为1，其余的数等于它上方两数之和。

为啥扯二项式却扯到杨辉三角了？

有一道提高组真题 P2822 [NOIP2016 提高组] 组合数问题，它需要用前缀和求解，由于我的代码是远古时期写的，我就直接粘上代码。

#include<bits/stdc++.h>
#define XD 114514

using namespace std;
int t,k,a[2010][2010],b[2010][2010];
int c[10010][10],num;
int main(){
    cin>>t>>k;
    for(int i=1;i<=t;i++){
        scanf("%d%d",&c[i][1],&c[i][2]);
        num=max(num,c[i][1]);
    }
    for(int i=1;i<=num+2;i++){
        for(int j=1;j<=i;j++){
            if(j==1 or j==i) a[i][j]=1;
            else{
                a[i][j]=a[i-1][j]+a[i-1][j-1];
                if(a[i][j]>=k) a[i][j]-=k;
            } 
        }
    }
    for(int i=3;i<=num+2;i++){
        for(int j=2;j<i;j++){
            if(a[i][j]==0 and j!=i+1) b[i-2][j-1]++;
            b[i-2][j-1]+=b[i-3][j-1]+b[i-2][j-2]-b[i-3][j-2];
        }
        b[i-2][i-1]=b[i-2][i-2];
    }
    for(int i=1;i<=t;i++){
        printf("%d\n",b[c[i][1]-1][min(c[i][1]-1,c[i][2])]);
    }
    return 0;
}

其实当时通过打表发现二项式系数构成的数字三角形和杨辉三角形完全一样，于是就愉快的求一遍前缀和就 AC 了。

那么根据杨辉三角的性质可得到\dbinom{n}{k}=\dbinom{n-1}{k}+\dbinom{n-1}{k-1}，这就是帕斯卡公式。

其实就是设杨辉三角形中第 i 行第 j 列第数为 Y_{ij}，那么 \dbinom{i}{j}=Y_{ij}。（补于 2023.5.18）

这里我会写一些二项式系数其他的式子。

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

证明:

\begin{aligned}k\dbinom{n}{k}&=k\times\dfrac{n(n-1)...(n-k+1)}{k!}\\&=\dfrac{n(n-1)...(n-k+1)}{(k-1)!}\\&=n\times\dfrac{(n-1)(n-2)...(n-k+1)}{(k-1)!}\\&=n\dbinom{n-1}{k-1}\end{aligned}

2.\sum\limits_{k=0}^n\dbinom{n}{k}=2^n

证明：这个用排列组合证明自认为更简单。设 S 为一个有 n 个互不相同元素的集合，在集合中选出若干个元素放入集合 T 中，则 T 集合有 2^n 种不同的情况，因为每个元素有放入 T 集合和不放入 T 集合两种选择，所以有 2^n 种。也可以说是把 S 的元素放入 T 中，计算没有元素的情况数、只有 1 个元素的情况数、 T 中有 2 个元素的情况数...T 种有 n 个元素的情况数求和，也就是 \sum\limits_{k=0}^n\dbinom{n}{k}，于是就证出来了。QWQ

3.\dbinom{n}{0}-\dbinom{n}{1}+\dbinom{n}{2}-\dbinom{n}{3}+...+(-1)^n\dbinom{n}{n}=0 (n\ge 1)

证明：把这个柿子转换一下就变成了 \binom{n}{0}+\binom{n}{2}+...=\binom{n}{1}+\binom{n}{3}+...=2^{n-1}，由上面的第 2 的柿子可得，\sum\limits_{k=0}^{n-1}\binom{n-1}{k}=2^{n-1}，我们来看杨辉三角的图，根据帕斯卡公式，\binom{n}{0}+\binom{n}{2}+...=\binom{n}{1}+\binom{n}{3}+...=2^{n-1} 就变成了 \binom{n-1}{0}+\binom{n-1}{1}+\binom{n-1}{3}+...=\binom{n-1}{0}+\binom{n-1}{1}+\binom{n-1}{3}+...=2^{n-1}，然后就没有然后了。QWQ

  1. 1\dbinom{n}{1}+2\dbinom{n}{2}+..+n\dbinom{n}{n}=n2^{n-1}

证明：

\begin{aligned}1\binom{n}{1}+2\binom{n}{2}+..+n\binom{n}{n}&=n\binom{n-1}{0}+n\binom{n-1}{1}+...+n\binom{n-1}{n-1}\\&=n(\binom{n-1}{0}+\binom{n-1}{1}+...+\binom{n-1}{n-1})\\&=n2^{n-1}\end{aligned}
  1. \sum\limits_{k=0}^n\dbinom{n}{k}^2=\dbinom{2n}{n}(n \ge 0)

证明：设 S 是一个有 2n 个互不相同元素的集合，在集合 S 中选出 n 个元素，则有 \binom{2n}{n} 种方案，也可以把 S 分为 A 和 B 两个子集，每个子集中都有 n 个元素，假设在 A 中选 k 该数，则在 B 中选 (n-k) 个数，则有 \sum\limits_{k=0}^n\binom{n}{k}\binom{n}{n-k}=\sum\limits_{k=0}^n\binom{n}{k}^2 种方案数，于是，\sum\limits_{k=0}^n\binom{n}{k}^2=\binom{2n}{n}(n \ge 0)。

上面的第 5 个其实是范德蒙卷积公式中的一种特殊情况。

范德蒙卷积公式：对所有的正整数 m_1,m_2,n，有 \sum\limits_{k=0}^n\binom{m_1}{k}\binom{m_2}{n-k}=\binom{m_1+m_2}{n}。

多项式系数

没想到吧，有了二项式系数还有多项式系数。

\dbinom{n}{n_1\ n_2...n_t}=\dfrac{n!}{n_1!n_2!...n_t!}

多项式定理

(x_1+x_2+...+x_t)^n=\sum\dbinom{n}{n_1\ n_2...n_t}x_1^{n_1}x_2^{n_2}...x_t^{n_t}

其中求和的条件是满足 n_1+n_2+...+n_t=n 的非负整数解。

牛顿二项式定理

这个只把柿子写上，听说要用到微积分的知识。

设 \alpha 是实数。对于所有满足 0 \le |x| < |y| 的 x 和 y，有 (x+y)^{\alpha}=\sum\limits_{k=0}^{\infty}\binom{\alpha}{k}x^ky^{\alpha-k}，其中 \binom{\alpha}{k}=\frac{\alpha(\alpha-1)...(\alpha-k+1)}{k!}。

参考的网络文献

杨辉三角百度百科

二项式定理百度百科

acm数学（番外1） 范德蒙德卷积公式

【组合数学】多项式定理 ( 多项式定理 | 多项式定理证明 | 多项式定理推论 1 项数是非负整数解个数 | 多项式定理推论 2 每项系数之和 )

还有一本书。

这时有人可能就要问了：“你巴拉巴拉写了这么多，那这些到底有啥用呢？”

我可以负责地对你说，这对 OI 没有任何卵用。（滑稽