二项式定理

1 展开式

对非负整数 nn,有:

(x+y)n=∑k=0n(nk)xn−kyk. \boxed{(x+y)^n=\sum_{k=0}^{n}\binom nk x^{n-k}y^k}.

这就是二项式定理。其中 (nk)\binom nk 表示从 nn 个不同位置中选出 kk 个,组合数的含义见 排列与组合。

例如:

(x+y)3=x3+3x2y+3xy2+y3. (x+y)^3=x^3+3x^2y+3xy^2+y^3.

各项的总次数都是 nn。当 n=0n=0 时,展开式只有常数项 11,对应 (00)=1\binom00=1。

2 系数的来源

把 (x+y)n(x+y)^n 写成 nn 个因子的乘积。分配律展开时,每个因子恰好选一个 xx 或 yy,再把选出的项相乘。

要产生 xn−kykx^{n-k}y^k,必须恰好在 kk 个因子中选择 yy,其余因子选择 xx。因此,需要选择的是哪些因子取 yy,共有 (nk)\binom nk 种,合并同类项后的系数就是 (nk)\binom nk。

例如 n=3,k=1n=3,k=1,三种选择都产生 x2yx^2y:

三个因子中分别选择一处 y,其余选择 x,三种选择合并为 3x 的平方乘 y

因子在乘积中有不同的位置,所以选择方案不同;乘法交换律又让它们产生相同的单项式。因此要把这些贡献相加,而不是只保留一项。

3 计算系数

将两个加数换成 axax、byby,得到:

(ax+by)k=∑j=0k(kj)ak−jbjxk−jyj. (ax+by)^k=\sum_{j=0}^{k}\binom kj a^{k-j}b^j x^{k-j}y^j.

要求 xnymx^ny^m 的系数,先检查 n+m=kn+m=k,再取 j=mj=m:

系数=(km)anbm=(kn)anbm. \boxed{\text{系数}=\binom km a^nb^m=\binom kn a^nb^m}.

若 n,mn,m 是非负整数且 n+m≠kn+m\ne k,该单项式不会出现,系数为 00。注意幂次要跟随相应变量,不能把 ana^n 与 bmb^m 交换。

例如 (2x−y)5(2x-y)^5 中,x3y2x^3y^2 的系数为:

(52)⋅23⋅(−1)2=80. \binom52\cdot2^3\cdot(-1)^2=80.

负号属于 yy 的系数,必须一起乘方;若要求 x4yx^4y 的系数,则为 (51)⋅24⋅(−1)=−80\binom51\cdot2^4\cdot(-1)=-80。

3.1 例题

题目:luogu P1313: [NOIP 2011 提高组] 计算系数。

输入 a,b,k,n,ma,b,k,n,m,求上述系数对 1000710007 取模的结果。题目保证 0≤k≤10000\le k\le1000、0≤n,m≤k0\le n,m\le k、n+m=kn+m=k,且 0≤a,b≤1060\le a,b\le10^6。

在这个范围内,用杨辉三角递推组合数:

(ij)=(i−1j−1)+(i−1j),(i0)=(ii)=1. \binom ij=\binom{i-1}{j-1}+\binom{i-1}j, \qquad \binom i0=\binom ii=1.

两个分支分别表示是否选中第 ii 个位置。整个递推只需要加法,可以直接对模数取模;幂次部分使用 快速幂。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 1000 + 5;
const int mod = 10007;
int c[maxn][maxn];

ll qpow(ll a, int b) {
    a = (a % mod + mod) % mod;
    ll answer = 1;  // 指数为 0 时返回 1,包括底数也为 0 的情形
    while (b) {
        if (b & 1) answer = answer * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return answer;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll a, b;
    int k, n, m;
    cin >> a >> b >> k >> n >> m;
    if (n + m != k) {  // 展开式中每一项的总次数都为 k
        cout << 0 << '\n';
        return 0;
    }

    c[0][0] = 1;
    for (int i = 1; i <= k; ++i) {
        c[i][0] = c[i][i] = 1;
        for (int j = 1; j < i; ++j) {
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
        }
    }
    ll answer = 1LL * c[k][n] * qpow(a, n) % mod;
    answer = answer * qpow(b, m) % mod;
    cout << answer << '\n';
    return 0;
}

时间为 O(k2+log⁡(n+1)+log⁡(m+1))O(k^2+\log(n+1)+\log(m+1)),空间为 O(k2)O(k^2)。边界 k=0k=0、n=0n=0 或 m=0m=0 都需要保留:指数为零表示该因子未被选用,对乘积贡献 11。

不要先用普通整数计算阶乘再相除,结果可能早已溢出;也不能把整数除法直接照搬到模运算中。这里使用的杨辉三角递推不需要除法。

完整题解:pcs2:计算系数。

4 常用恒等式

4.1 系数和

取 x=y=1x=y=1,得到:

∑k=0n(nk)=2n. \sum_{k=0}^{n}\binom nk=2^n.

组合意义是:按选取元素个数分类,所有子集共有 2n2^n 个。这一式对 n=0n=0 也成立。

4.2 奇偶选择

当 n≥1n\ge1 时,取 x=1,y=−1x=1,y=-1,得到:

∑k=0n(−1)k(nk)=0. \sum_{k=0}^{n}(-1)^k\binom nk=0.

把偶数项与奇数项分别移到等式两侧,再结合系数和,可知:

∑0≤k≤nk 为偶数(nk)=∑0≤k≤nk 为奇数(nk)=2n−1. \sum_{\substack{0\le k\le n\\k\text{ 为偶数}}}\binom nk =\sum_{\substack{0\le k\le n\\k\text{ 为奇数}}}\binom nk =2^{n-1}.

因此,当原集合至少含一个元素时,偶数大小子集与奇数大小子集数量相同,空集也计入偶数大小子集。n=0n=0 时只有一个空集,交错和为 11,不能套用上式。

4.3 范德蒙德恒等式

对非负整数 r,s,kr,s,k,有:

∑i=0k(ri)(sk−i)=(r+sk), \sum_{i=0}^{k}\binom ri\binom{s}{k-i}=\binom{r+s}k,

约定选取数量超出范围时组合数为 00。

从两个互不相交、大小分别为 r,sr,s 的集合中,一共选 kk 个元素。左侧按从第一个集合选了 ii 个分类,右侧直接从并集中选择,两者统计同一件事。

也可以比较 (1+x)r(1+x)s=(1+x)r+s(1+x)^r(1+x)^s=(1+x)^{r+s} 两侧 xkx^k 的系数。展开式中的系数既能表示选择数,也能用来组织分组计数。

5 相关题解

暂无相关题解