二项式系数及其反演

二项式系数&二项式定理

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

$\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卷积公式：

(\begin{matrix} x + y \\ n \end{matrix}) = \sum_{k = 0}^{n} (\begin{matrix} x \\ k \end{matrix}) (\begin{matrix} y \\ n - k \end{matrix})

以及展开形式(expand form)

{(1 + t)}^{x} = \sum_{n = 0}^{\infty} (\begin{matrix} x \\ n \end{matrix}) t^{n}, {(1 - t)}^{- x} = \sum_{n = 0}^{\infty} 〈 \begin{matrix} x \\ n \end{matrix} 〉 t^{n}

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

且有

〈 \begin{matrix} x + y \\ n \end{matrix} 〉 = \sum_{k = 0}^{n} 〈 \begin{matrix} x \\ k \end{matrix} 〉 〈 \begin{matrix} y \\ n - k \end{matrix} 〉

定义1

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

\begin{array}{l} {(P_{n} [x])}_{i j} = {\begin{matrix} (\begin{matrix} x \\ i - j \end{matrix}), & i \geq j \\ 0 & o t h e r w i s e \end{matrix} \\ {(Q_{n} [x])}_{i j} = {\begin{matrix} 〈 \begin{matrix} x \\ i - j \end{matrix} 〉, & i \geq j \\ 0 & o t h e r w i s e \end{matrix} \\ {(D_{k})}_{i j} = {\begin{matrix} 1, & i = j + k \\ 0, & o t h e r w i s e \end{matrix} \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] = \sum_{k = 0}^{n} (\begin{matrix} x \\ k \end{matrix}) D_{k} = \sum_{k = 0}^{n} \frac{{(x)}_{k}}{Γ (k + 1)} D^{k} = \sum_{k = 0}^{n} \sum_{i = k}^{n} \frac{[\begin{matrix} i \\ k \end{matrix}]}{Γ (i + 1)} D^{i} x^{k}, \\ Q_{n} [x] = \sum_{k = 0}^{n} \frac{{〈 x 〉}_{k}}{Γ (k + 1)} D^{k} = \sum_{k = 0}^{n} \sum_{i = k}^{n} {(- 1)}^{i + k} \frac{[\begin{matrix} i \\ k \end{matrix}]}{Γ (i + 1)} D^{i} x^{k} \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])}_{i j} = \sum_{k = j}^{i} (\begin{matrix} x \\ i - k \end{matrix}) (\begin{matrix} y \\ k - j \end{matrix}) = (\begin{matrix} x + y \\ i - j \end{matrix}) = {(P_{n} [x + y])}_{i j}

推论：$\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])}_{i j} = {\begin{matrix} (\begin{matrix} x \\ i - j \end{matrix}) y^{i - j} \\ 0 \end{matrix}, i \geq j; \\ {(Q_{n} [x, y])}_{i j} = {\begin{matrix} 〈 \begin{matrix} x \\ i - j \end{matrix} 〉 y^{i - j} \\ 0 \end{matrix}, i \geq j . \end{array}

定理3

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

\begin{array}{l} {\begin{matrix} 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{matrix} \\ {\begin{matrix} P_{n} {[x, y]}^{m} = P_{n} [m x, y], \\ Q_{n} {[x, y]}^{m} = Q_{n} [m x, y] . \end{matrix} \end{array}

即

{\begin{matrix} 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{matrix}

反演开始！

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

定理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) = \sum_{k = 0}^{n} (\begin{matrix} x \\ k \end{matrix}) b_{n - k} (x, y) \Leftrightarrow b_{n} (x, y) = \sum_{k = 0}^{n} (\begin{matrix} - x \\ n - k \end{matrix}) a_{n - k} (x, y)

也就是

a_{n} (x, y) = \sum_{k = 0}^{n} (\begin{matrix} x \\ n - k \end{matrix}) b_{n - k} (x, y) \Leftrightarrow b_{n} (x, y) = \sum_{k = 0}^{n} (\begin{matrix} - x \\ n - k \end{matrix}) 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} = \sum_{j = 0}^{i} (\begin{matrix} x \\ i - j \end{matrix}) b_{j} \Leftrightarrow b_{i} = \sum_{j = 0}^{i} (\begin{matrix} - x \\ i - j \end{matrix}) 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

有恒等式

\sum_{k = 0}^{n} (\begin{matrix} x \\ k \end{matrix}) y^{k} = \sum_{k = 0}^{n} (\begin{matrix} n - x \\ k \end{matrix}) {(1 + y)}^{n - k} {(- y)}^{k}

作变换：

\sum_{k = 0}^{n} (\begin{matrix} x \\ k \end{matrix}) y^{n - k} = \sum_{k = 0}^{n} {(- x)}^{k} (\begin{matrix} n - x \\ k \end{matrix}) {(1 + y)}^{n - k} \dots \dots Tip : replace y with \frac{1}{y}

令

b_{n - k} = y^{n - k}, a_{n} = \sum_{k = 0}^{n} {(- 1)}^{k} (\begin{matrix} n - x \\ k \end{matrix}) {(1 + y)}^{n - k},

则有

\sum_{k = 0}^{n} \sum_{i = 0}^{n - k} {(- 1)}^{i} (\begin{matrix} - x \\ k \end{matrix}) (\begin{matrix} n - k - x \\ i \end{matrix}) {(1 + y)}^{n - k - i} = y^{n} \dots \dots Tip : Use the Inversion Formula

神奇变换2

有恒等式

\sum_{k = 0}^{n} {(- 1)}^{k} (\begin{matrix} n + x \\ n - k \end{matrix}) \frac{1}{1 + k} = (\begin{matrix} B_{n} (x) + n \\ n \end{matrix})

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

变形为：

\sum_{k = 0}^{n} (\begin{matrix} x \\ n - k \end{matrix}) \frac{{(- 1)}^{k}}{1 + k} = (\begin{matrix} B_{n} (x - n) + n \\ n \end{matrix})

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

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

有

\sum_{k = 0}^{n} (\begin{matrix} - x \\ n - k \end{matrix}) (\begin{matrix} B_{k} (x - k) + k \\ k \end{matrix}) = \frac{{(- 1)}^{n}}{1 + n}

神奇变换3

有恒等式

\sum_{k = 0}^{n - 1} (\begin{matrix} z \\ k \end{matrix}) x^{n - k - 1} = \sum_{k = 1}^{n} (\begin{matrix} z - k \\ n - k \end{matrix}) {(x + 1)}^{k - 1}

通过反演，得出：

\sum_{k = 0}^{n} (\begin{matrix} - x \\ k \end{matrix}) \sum_{i = 0}^{n - k} (\begin{matrix} x - i - 1 \\ n - k - i \end{matrix}) (z + 1) = z^{n}

神奇变换4

有恒等式

\sum_{k = 0}^{n - 1} (\begin{matrix} z \\ k \end{matrix}) \frac{x^{n - k}}{n - k} = \sum_{k = 1}^{n} (\begin{matrix} z - k \\ n - k \end{matrix}) \frac{{(x + 1)}^{k} - 1}{k}

通过反演，得出

\sum_{k = 0}^{n} (\begin{matrix} - z \\ k \end{matrix}) \sum_{i = 0}^{n - k} (\begin{matrix} z - i - 1 \\ n - k - i \end{matrix}) \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, 二项式系数