二项式定理

二项式定理

内容

二项式定理阐明了一个展开式的系数：

\[(x+y)^n=\sum_{i=0}^n\left(^n_i\right)x^iy^{n-i} \]

证明：

\[(x+y)^n=(x+y)(x+y)\cdots(x+y) \]

暴力拆开看一下，应该是每个 \((x+y)\)，都取出一个 \(x\) 或者 \(y\)，去跟后面所有的 \((x+y)\) 中再取一个数字，乘起来，相加。

所以展开后的每一项都是 \(n\) 次项。

而注意到先选 \(i\) 个 \(x\)，后选 \(n-i\) 个 \(y\) 与先选 \(n-i\) 个 \(y\)，后选 \(i\) 个 \(x\) 乘起来其实是一样的，即我们关心的只是 \(x^iy^{n-i}\) 中的 \(i\) 以及有多少个 \(x^iy^{n-i}\)。

从组合数学的方向考虑，假设我们选择了 \(i\) 个 \(x\)，那么就需要选择 \((n-i)\) 个 \(y\)。

而方案数就是 \(\left(^n_i\right)=\left(^n_{n-i}\right)\)。

即从 \(n\) 个 \((x+y)\) 中，选 \(i\) 个 \(x\) 或选 \(n-i\) 个 \(y\) 的方案数，但本质上是等价的。

所以对于一共选了 \(i\) 个 \(x\)，\(n-i\) 个 \(y\)，贡献就是 \(\left(^n_i\right)x^iy^{n-i}\)。

对于完全展开后的式子，就是把所有上述式子相加，即 \(\sum_{i=0}^n\left(^n_i\right)x^iy^{n-i}\)。

一些推论

感觉只要会了普通版本，这些东西十分简单，就是特殊情况。

• \((x+1)^n=\sum_{i=0}^n\left(^n_i\right)x^i\)

令 \(y=1\) 即可，不解释。

• \(\sum_{i=0}^n\left(^n_i\right)=2^n\)

这个可以当作是在 \(n\) 个数中选子集，每个数都有选和不选两种状态，所以一共是 \(2^n\) 种。

• \(\sum_{i=0}^n(-1)^i\left(^n_i\right)=0\)

令 \(x=-1,y=1\) 即可。

多项式定理

直接上式子：

\[(x_1+x_2+\cdots x_k)^n=\sum_{\left(\sum_{l=1}^kn_l\right)=n}\prod_{i=1}^k\left(^{n-\sum_{j=1}^{i-1}n_j}_{n_i}\right)x_i^{n_i} \]

即考虑 \(x_i\) 选择 \(n_i\) 个的方案数。

与二项式定理同理，所有项的系数必须是 \(n\)。

\[\left(^{n-\sum_{j=1}^{i-1}n_j}_{n_i}\right) \]

这一坨的意思是，当前考虑到第 \(i\) 个，\(n\) 个中已经被选了 \(\sum_{j=1}^{i-1}n_j\) 个，需要选 \(n_i\) 个 \(x_i\) 的方案数。

给点例题

NOIP2011提高组 计算系数

题意：给定多项式 \((ax+by)^k\)，求展开后 \(x^ny^m\) 的系数。

本来是很复杂的，但是学完二项式定理就很简单了，推式子：

\[(ax+by)^k\\ =\sum_{i=0}^k\left(^k_i\right)(ax)^i(by)^{n-i} \]

其中要我们求的就是 \(\left(^k_n\right)(ax)^i(by)^{n-i}\)。

移出系数就是：\(\left(^k_n\right)a^ib^{n-i}\)。

用快速幂搞搞即可。

注意排列数记得用递推式：\(C_{i,j}=C_{i-1,j}+C_{i-1,j-1}\)。其中 \(C_{i,j}\) 表示从 \(i\) 个物品中，无序地选取 \(j\) 个的方案数。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ljl;
#define FUP(i,x,y) for(int i=(x);i<=(y);++i)
#define FDW(i,x,y) for(int i=(x);i>=(y);--i)
inline void Rd(auto &num);
const int K=1e3+5,N=K,M=K;
const ljl Mod=10007;
ljl a,b,k,n,m,fct[N],C[N][N];
ljl qpow(ljl a,ljl k)//a^k
{ljl ans=1ll;while(k){if(k&1)ans=ans%Mod*a%Mod;a=a%Mod*a%Mod;k>>=1;}return ans;
}
void getc()
{//c[a][b]:choose b in aFUP(i,1,k)C[i][0]=C[0][i]=1;FUP(i,1,k)FUP(j,1,i)C[i][j]=(C[i-1][j-1]+C[i-1][j])%Mod;
//	FUP(i,1,k)
//	{
//		FUP(j,1,k)
//		{
//			printf("%lld ",C[i][j]);
//		}
//		printf("\n");
//	}return ;
}
int main(){Rd(a);Rd(b);Rd(k);Rd(n);Rd(m);fct[1]=1;FUP(i,2,k)fct[i]=fct[i-1]*i%Mod;getc();printf("%lld\n",C[k][n]%Mod*qpow(a,n)%Mod*qpow(b,m)%Mod);return 0;
}
inline void Rd(auto &num)
{num=0;char ch=getchar();bool f=0;while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}while(ch>='0'&&ch<='9'){num=(num<<1)+(num<<3)+(ch-'0');ch=getchar();}if(f)num=-num;return;
}