二项式系数及其反演

二项式系数&二项式定理

了解标题之前，我们先要花一些时间复习一下普通的二项式系数：

$\left( \begin{array}{c}n\\k\end{array} \right) = \dfrac{\Gamma (n + 1)}{\Gamma (k + 1)\Gamma (n - k + 1)}$

我们对它研究得非常多，例如经典的二项式定理：

${(x + y)^n} = \left( \begin{array}{c}n\\0\end{array} \right){x^n}{y^0} + \left( \begin{array}{c}n\\1\end{array} \right){x^{n - 1}}{y^1} + \left( \begin{array}{c}n\\2\end{array} \right){x^{n - 2}}{y^2} + \cdots + \left( \begin{array}{c}n\\n - 1\end{array} \right){x^1}{y^{n - 1}} + \left( \begin{array}{c}n\\n\end{array} \right){x^0}{y^n}$

写成和式的形式，也就是

${(x + y)^n} = \sum\limits_{k = 0}^n {\left( \begin{array}{c}n\\k\end{array} \right)} {x^{n - k}}{y^k} = \sum\limits_{k = 0}^n {\left( \begin{array}{c}n\\k\end{array} \right)} {x^k}{y^{n - k}}$

证明挺简单的，想必大家都会，这里不会的可以来谈人生了QwQ

广义二项式定理

这玩意怎么推广？

${(x + y)^\alpha } = \mathop \sum \limits_{k = 0}^\infty \left( \begin{array}{c}\alpha \\k\end{array} \right){x^{\alpha - k}}{y^k}$

第一种证明

证明也非常简单

它可以看成$(1+x)^\alpha$的幂级数展开

显然函数当$\alpha>0$的时候是analytic的，所以可以通过多次求导得到幂级数中的项：

$f(x)=\sum_\limits{n\geq 0}\dfrac{f^{(n)}(0)}{n!}x^n$

令$f(x)=(1+x)^\alpha$，多次求导可得

${f^{(n)}}(x) = \alpha (\alpha - 1) \cdots \cdots (\alpha - n + 1){(1 + x)^{a - n}}$

当然这个只对$\alpha>0$有效，对于其它情况，可以用幂级数倒数的性质来证明。

这个证明可能用的定理太高级，其实还是组合式的比较好，但是可能就比较长就是了……

第二种证明

还是原来的函数$f(x)$，假定它能展开成幂级数$f(x) = \sum\limits_{n \ge 0} {a_n} {x^n}$

然后我们无比震惊地发现它满足如下的微分方程：

$(1 + x)f’(x) = \alpha f(x),f(0) = 1$

这个微分方程又可以写成系数之间的递推式：

${a_0} = 1,\sum\limits_{n \ge 0} {((n + 1){a_{n + 1}} + n{a_n})x = \sum\limits_{n \ge 0} {\alpha {a_n}{x^n}} }$

然后就有

${a_0} = 1,\forall n,n{a_n} = (\alpha - n - 1){a_{n + 1}}$

然后解递推方程咯…..

如果你还是看不懂，可以去维基百科看详细过程解答。

组合证明

百度百科-二项式定理上面有写，如果你这个都看不懂说明你废了。。

二项式定理的一些小应用

• 当然是帮助证明东西

证明组合恒等式：

比如证明

$$\sum\limits_{k = 0}^n {\left( {\begin{array}{*{20}{c}}n\\k\end{array}} \right)}^2 = \left( {\begin{array}{*{20}{c}}{2n}\\n\end{array}} \right)$$

可以考虑恒等式

$${(1 + x)^n}{(1 + x)^n} = {(1 + x)^{2n}}$$

然后证明就很显然了

证明自然数幂求和公式:

我没有看懂（留坑），但是有一篇博客系统地讲述了自然数幂和的各种求法：解决自然数幂和的方法

二项式反演！

前置定义&定理

设$x$为任意复数，$n$是非负整数

对于广义二项式系数$\left( {\begin{array}{*{20}{c}}x\\n\end{array}} \right)$，有Vandermonde卷积公式：

$$\left(\begin{array}{c}x+y\\ n\end{array}\right)={\displaystyle \sum _{k=0}^n\left(\begin{array}{c}x\\ k\end{array}\right)}\left(\begin{array}{c}y\\ n-k\end{array}\right)$$

以及展开形式(expand form)

$${(1+t)}^x={\displaystyle \sum _{n=0}^{\infty }\left(\begin{array}{c}x\\ n\end{array}\right)}{t}^n,{(1-t)}^{-x}={\displaystyle \sum _{n=0}^{\infty }\langle \begin{array}{c}x\\ n\end{array}\rangle }{t}^n$$

其中$\left\langle {\begin{array}{*{20}{c}}x\\n\end{array}} \right\rangle = \dfrac{x(x + 1) \cdots (x + n - 1)}{n!}$

且有

$$\langle \begin{array}{c}x+y\\ n\end{array}\rangle ={\displaystyle \sum _{k=0}^n\langle \begin{array}{c}x\\ k\end{array}\rangle }\langle \begin{array}{c}y\\ n-k\end{array}\rangle$$

• 定义1

$x$为任意数，$n+1$阶矩阵$P_n[x],Q_n[x],D_k(k \in N^*)$分别定义

$$\begin{array}{l}{(P_n[x])}_{ij}=\{\begin{array}{cc}\left(\begin{array}{c}x\\ i-j\end{array}\right),& i\ge j\\ 0& otherwise\end{array}\hfill \\ {(Q_n[x])}_{ij}=\{\begin{array}{cc}\langle \begin{array}{c}x\\ i-j\end{array}\rangle ,& i\ge j\\ 0& otherwise\end{array}\hfill \\ {(D_k)}_{ij}=\{\begin{array}{cc}1,& i=j+k\\ 0,& otherwise\end{array}\hfill \end{array}$$

显然，$P_n[0]=Q_n[0]=D_0=I_{n+1}$($I_{n+1}$阶单位矩阵)。设$D_1=D$，那么$D_k=D^k,k \in N^*$。设$(x)_k=\dfrac{\Gamma(x+1)}{\Gamma(k+1)}$，${\langle x \rangle}_k=\dfrac{\Gamma(x+k)}{\Gamma(x)}$，由矩阵乘法和Stirling数的性质，我们得到了一个定理：

• 定理1

$x$为任意数，则有

$$\begin{array}{l}{P}_n[x]={\displaystyle \sum _{k=0}^n\left(\begin{array}{c}x\\ k\end{array}\right)}{D}_k={\displaystyle \sum _{k=0}^n\frac{{(x)}_k}{\Gamma (k+1)}}{D}^k={\displaystyle \sum _{k=0}^n{\displaystyle \sum _{i=k}^n\frac{\left[\begin{array}{c}i\\ k\end{array}\right]}{\Gamma (i+1)}}}{D}^i{x}^k,\hfill \\ Q_n[x]={\displaystyle \sum _{k=0}^n\frac{{\langle x\rangle }_k}{\Gamma (k+1)}}{D}^k={\displaystyle \sum _{k=0}^n{\displaystyle \sum _{i=k}^n{(-1)}^{i+k}}}\frac{\left[\begin{array}{c}i\\ k\end{array}\right]}{\Gamma (i+1)}{D}^i{x}^k\hfill \end{array}$$

其中$\left[ {\begin{array}{*{20}{c}}n\\k\end{array}} \right]$是第一类无符号Stirling数。

• 定理2

$\forall x,y \in \mathbb{R}$，则有$\begin{array}{l}P_n[x + y] = P_n[x]P_n[y],\\{Q_n}[x + y] = {Q_n}[x]{Q_n}[y].\end{array}$

证明：当$i \geq j$时，

$${(P_n[x]P_n[y])}_{ij}={\displaystyle \sum _{k=j}^i\left(\begin{array}{c}x\\ i-k\end{array}\right)}\left(\begin{array}{c}y\\ k-j\end{array}\right)=\left(\begin{array}{c}x+y\\ i-j\end{array}\right)={(P_n[x+y])}_{ij}$$

推论：$\forall x,y \in \mathbb{R},m \in \mathbb{Z}$，有$\begin{array}{l}P_n{[x]^{ - 1}} = P_n[ - x],\\P_n{[x]^m} = P_n[mx],\\P_n[x] = P_n{[\frac{x}{m}]^m}.\end{array}$

• 定义2

$\forall x,y \in \mathbb{R}$,$n+1$阶矩阵$P_n[x,y],Q_n[x,y]$分别定义为

$$\begin{array}{l}{(P_n[x,y])}_{ij}=\{\begin{array}{c}\left(\begin{array}{c}x\\ i-j\end{array}\right)y^{i-j}\\ 0\end{array},i\ge j;\hfill \\ {(Q_n[x,y])}_{ij}=\{\begin{array}{c}\langle \begin{array}{c}x\\ i-j\end{array}\rangle y^{i-j}\\ 0\end{array},i\ge j.\hfill \end{array}$$

• 定理3

$\forall x,y,z \in \mathbb{R}, m \in \mathbb{Z}$，有

$$\begin{array}{l}\{\begin{array}{c}{P}_n[x,z]P_n[y,z]=P_n[x+y,z],\\ Q_n[x,z]Q_n[y,z]=Q_n[x+y,z].\end{array}\hfill \\ \{\begin{array}{c}{P}_n{[x,y]}^m=P_n[mx,y],\\ Q_n{[x,y]}^m=Q_n[mx,y].\end{array}\hfill \end{array}$$

即

$$\{\begin{array}{c}{P}_n{[x,y]}^{-1}=P_n[-x,y],P_n[x,1]=P_n[x],P_n[0,1]=I_{n+1};\\ Q_n{[x,y]}^{-1}=Q_n[-x,y],Q_n[x,1]=Q_n[x],Q_n[0,1]=I_{n+1}.\end{array}$$

反演开始！

还记得上面的推论吗？我们由它可以得到如下定理：

• 定理4

$\forall x,y \in \mathbb{R}​$，设$\{a_n\}_{n\geq 0}=\{a_n(x,y)\}_{n\geq 0}​$和$\{b_n\}_{n\geq 0}=\{b_n(x,y)\}_{n\geq 0}​$为两个函数序列

那么我们有

$$a_n(x,y)={\displaystyle \sum _{k=0}^n\left(\begin{array}{c}x\\ k\end{array}\right)}{b}_{n-k}(x,y)\iff b_n(x,y)={\displaystyle \sum _{k=0}^n\left(\begin{array}{c}-x\\ n-k\end{array}\right)}{a}_{n-k}(x,y)$$

也就是

$$a_n(x,y)={\displaystyle \sum _{k=0}^n\left(\begin{array}{c}x\\ n-k\end{array}\right)}{b}_{n-k}(x,y)\iff b_n(x,y)={\displaystyle \sum _{k=0}^n\left(\begin{array}{c}-x\\ n-k\end{array}\right)}{a}_{n-k}(x,y)$$

证明：

设$a = {({a_0},{a_1}, \cdots ,{a_n})^T},b = {({b_0},{b_1}, \cdots ,{b_n})^T}$，注意到$a = P_n[x] \Leftrightarrow b = P_n[ - x]$

即

$$a_i={\displaystyle \sum _{j=0}^i\left(\begin{array}{c}x\\ i-j\end{array}\right)}{b}_j\iff b_i={\displaystyle \sum _{j=0}^i\left(\begin{array}{c}-x\\ i-j\end{array}\right)}{a}_j$$

我们的二项式反演公式也就很明白了：

令${\{ {a_n}\} _{n \ge 0}}$和${\{ {b_n}\} _{n \ge 0}}$是两个数列，$s$为非负整数，$\forall n \geq s$，有

$${a_n} = \mathop \sum \limits_{k = s}^n \left( {\begin{array}{*{20}{c}}n\\k\end{array}} \right){b_k}$$

则有

$${b_n} = \mathop \sum \limits_{k = s}^n {( - 1)^{n - k}}\left( {\begin{array}{*{20}{c}}n\\k\end{array}} \right){a_k}$$

好啦~ 反演到此为止，下面是娱乐环节！

一些神奇的恒等式变换

• 如果你连基本恒等式都看不懂，说明你需要补习数学。

神奇变换1

有恒等式

$${\displaystyle \sum _{k=0}^n\left(\begin{array}{c}x\\ k\end{array}\right)}{y}^k={\displaystyle \sum _{k=0}^n\left(\begin{array}{c}n-x\\ k\end{array}\right)}{(1+y)}^{n-k}{(-y)}^k$$

作变换：

$${\displaystyle \sum _{k=0}^n\left(\begin{array}{c}x\\ k\end{array}\right)}{y}^{n-k}={\displaystyle \sum _{k=0}^n{(-x)}^k}\left(\begin{array}{c}n-x\\ k\end{array}\right){(1+y)}^{n-k}\cdots \cdots \text{Tip}:\text{replace }y\text{with}\frac{1}{y}$$

令

$$b_{n-k}=y^{n-k},a_n={\displaystyle \sum _{k=0}^n{(-1)}^k}\left(\begin{array}{c}n-x\\ k\end{array}\right){(1+y)}^{n-k},$$

则有

$${\displaystyle \sum _{k=0}^n{\displaystyle \sum _{i=0}^{n-k}{(-1)}^i}}\left(\begin{array}{c}-x\\ k\end{array}\right)\left(\begin{array}{c}n-k-x\\ i\end{array}\right){(1+y)}^{n-k-i}=y^n\cdots \cdots \text{Tip}:\text{Use}\text{the Inversion Formula}$$

神奇变换2

有恒等式

$${\displaystyle \sum _{k=0}^n{(-1)}^k}\left(\begin{array}{c}n+x\\ n-k\end{array}\right)\frac{1}{1+k}=\left(\begin{array}{c}{B}_n(x)+n\\ n\end{array}\right)$$

，其中$B_n(x)$是Bernouli多项式

变形为：

$${\displaystyle \sum _{k=0}^n\left(\begin{array}{c}x\\ n-k\end{array}\right)}\frac{{(-1)}^k}{1+k}=\left(\begin{array}{c}{B}_n(x-n)+n\\ n\end{array}\right)$$

令${b_k} = \dfrac{( - 1)^k}{1 + k},{a_n} = \left( {\begin{array}{*{20}{c}}{B_n(x - n) + n}\\n\end{array}} \right)$

我们在反演公式2中进行变换

有

$${\displaystyle \sum _{k=0}^n\left(\begin{array}{c}-x\\ n-k\end{array}\right)}\left(\begin{array}{c}{B}_k(x-k)+k\\ k\end{array}\right)=\frac{{(-1)}^n}{1+n}$$

神奇变换3

有恒等式

$${\displaystyle \sum _{k=0}^{n-1}\left(\begin{array}{c}z\\ k\end{array}\right)}{x}^{n-k-1}={\displaystyle \sum _{k=1}^n\left(\begin{array}{c}z-k\\ n-k\end{array}\right)}{(x+1)}^{k-1}$$

通过反演，得出：

$${\displaystyle \sum _{k=0}^n\left(\begin{array}{c}-x\\ k\end{array}\right)}{\displaystyle \sum _{i=0}^{n-k}\left(\begin{array}{c}x-i-1\\ n-k-i\end{array}\right)}(z+1)=z^n$$

神奇变换4

有恒等式

$${\displaystyle \sum _{k=0}^{n-1}\left(\begin{array}{c}z\\ k\end{array}\right)}\frac{x^{n-k}}{n-k}={\displaystyle \sum _{k=1}^n\left(\begin{array}{c}z-k\\ n-k\end{array}\right)}\frac{{(x+1)}^k-1}{k}$$

通过反演，得出

$${\displaystyle \sum _{k=0}^n\left(\begin{array}{c}-z\\ k\end{array}\right)}{\displaystyle \sum _{i=0}^{n-k}\left(\begin{array}{c}z-i-1\\ n-k-i\end{array}\right)}\frac{{(x+1)}^{i+1}-1}{i+1}=\frac{x^{n+1}}{n+1}$$

总结

我们全文讨论了许多关于二项式系数的问题。二项式系数的恒等式可能远不止这些，还需要我们去发掘。

我们可以看到在恒等式变换部分，许多式子最终的形式都是非常美妙简洁的。在OI中，可以帮助加速运算。

参考资料

[1], Wikipedia, 二项式定理

[2], Wikipedia, Binomial theorem

[3], Miskcoo’s Space , 反演魔术：反演原理及二项式反演

[4], creatorx ,二项式反演公式

[5], Wolframmathworld, Binomial theorem

[6], Peoplesju, The Generalized Binomial Theorem

[7], Concrete Mathematics, 二项式系数