二项式系数（Binomial Coefficients）与组合恒等式（Combinatorial Identities）
前言
这曾是个一时兴起而决定的计划。
这是一篇书写于2014年2月23日的文章，修订于2018年7月5日。
这个系列主要是为了记录自己曾经学习过的，已经忘记的，亦或者是正在学习的内容。
0.符号约定
\[r^{\underline k} = r(r-1)(r-2)\cdots(r-k+1)\] \[r^{\overline k} = r(r+1)(r+2)\cdots(r+k-1)\]并不是些什么故弄玄虚的符号，但实际上在专业的数学读物上比较少见，不过Knuth使用这些符号约定，考虑面向大都是计算机相关背景的读者，因而选取他老人家的符号约定也在情理之中。
1.定义
『它有那么丰富的性质，这真是令人奇怪的事』— Blaise.Pascal
帕斯卡于1655年发表的《论算术三角》中详细的阐述了一个二项式系数的表格表示（杨辉三角，西方一般称之为帕斯卡三角）表中每个数等于其肩上两个数之和，这个性质直接给出了二项式系数的一个递归的定义:
\[\begin{align} {r \choose k} &= {r-1 \choose k-1} + {r-1 \choose k} \\ {0 \choose 0} &= 1 \\ {r \choose k} &= 0,\ when\ k\ <\ 0 \\ \end{align}\]这个定义又被称作加法公式（Addition Formula），从它可以导出许多有趣的二项式系数性质，大多数于初高中课本上已经出现过，鄙人在此也就不再赘述其证明过程。
\[k{r \choose k} = r{r-1 \choose k-1}, \ k \in \mathbb{N}\] （吸收（Absorption））
（对称（Symmetry））
（利用加法公式反复展开即可得到）
（利用加法公式反复展开具有最小下指标的二项式系数项即可得到）
此类组合数是由于二项式定理（Binomial Theorem）而被命名为二项式系数的，简单叙述如下：
令$n$是一个正整数。于是对于任意的$x, y$，有
\[(x+y)^n = x^n + {n \choose 1}x^{n-1}y + {n \choose 2}x^{n-2}y^2 + \cdots +{n \choose n-1}xy^{n-1} + y^n\]回忆起组合数的定义，实际上这个定理的证明非常容易—$x^{k}y^{n-k}$的系数实际上就是$k$个因子$x$与$n-k$个因子$y$的项的个数，这恰好是从$n$个$(x+y)$的因子中选取k个的方法数–他们都提供一个x。
1.5 定义(续)
然而到目前为止，我们似乎一直在幻想乡中阐述这些定理和公式—上下标总是整数并且总是非负的。这显然不可能满足我们的需要，我们期望能够拥有一个类似于泰勒展式（Taylor Extension）这类一般的式子。幸运的是牛顿（Newton）于1665年阐述了如何将上述定理推广到一般的情况。
如果我们定义
\[{r \choose k} = {r^{\underline k}\over {k!}}, \text{if } k \in \mathbb{N}_{\ge 0}, \text{otherwise} \ 0\]那么二项式定理即可推广到更加一般的情形（及上述二项式定理对n不再有任何限制）推广的合理性证明不在本次的内容之中，其能够在大多数微积分教材中找到
让我们来看看我们究竟得到了什么，令$z=x/y$ (或y/x)，则二项式定理可以等价归约为
\[(1+z)^r = \sum_{k=0}^\infty {r \choose k}z^k,\ |z|<1\]考虑$r$为负整数$-n$的情况
\[\begin{align} {r \choose k} &= {-n \choose k} = {-n(-n-1)\cdots(-n-k+1)\over k!} \\ &= (-1)^k{n(n+1)\cdots(n+k-1)\over k!} \\ &= (-1)^k{n+k-1 \choose k} \end{align}\]| 因此，对于$ | z | <1$，我们得到 |
因而有
\[(1-z)^{-r}={1 \over (1-z)^r}=\sum_{k=0}^\infty {r+k-1 \choose k}z^k\]当$r=1$时，我们就得到了收敛的几何级数和
\[{1 \over 1-z} = \sum_{k=0}^\infty z^k,\ |z|<1\]这个结果某种程度上阐明了定理的合理性，至少我们没有走什么弯路，这的确令人欣慰。
2.基本性质
在推广了二项式定理之后，我们仍然希望其能够具有整数情况下的那些美妙的性质，否则这种推广就没什么意义的—他甚至不能够向下兼容。幸运的是，情况正如我们希望的那样。推广证明的方法一般称之为多项式推理法（Polynomial Argument），这个方法通过考察等式两边多项式的零点来证明他们相等。譬如之前所提到的吸收律，推广证明大致如下：
考虑到等式两边其实都是关于$r$的$k+1$次多项式，而由代数基本定理我们能知道:一个非零的$d$次多项式或者更低次数的多项式在复数域上至多只能有$d$个的零点，也就是说，两个这样的多项式之差不可能在多于$d$个点处为零（因为他们的差是一个不高于$d$次的多项式）除非这两个多项式相等。而在整数情况下我们已经证明，只要$r$是一个非负整数，那么吸收律就是成立的，因而两个多项式在无穷多处取相同的值，则他们必然是完全相同的。 借助这一强大的工具，我们能够推广其他所有在整数情况下已经证明的组合恒等式。
处理完这些遗留下的问题之后，一个很自然的问题便出现在了我们的眼前—我们是否能够通过上指标$r$是正数或正整数的值推导出上指标为$-r$的值或是建立某种联系呢。这个工作是有必要的—根据以往的经验，非负总是更加容易处理，我们对它也更加的熟悉。而实际在定义（续）这一节之中我们已经给出了这个关系
\[{r \choose k}=(-1)^k{k-r-1 \choose k}\]通常我们称这个变换为反转上指标（Negating the Upperindex）。
通过微分
\[(1+z)^r = \sum_{k=0}^\infty {r \choose k}z^k\]我们能得到对于任意正整数p成立的这样一个恒等式
\[\sum_{k=1}^r k^p {r \choose k}\]3.和式
我们会在很多地方遇到组合式和式，例如排序查找算法分析，又或是深入一些的数理统计与概率论—它们并不是什么无用的，纯理论的东西，尽管他们时常看起来异常鬼畜。
以下几道简单的示例/习题主要来自以下参考书：
1).Introductory Combinatorics (5th Edition)
2).Concrete Mathematics (2nd Edition)
3).The Art Of Computer Programming - Fundamental Algorithms (3rd Edition)
ex.1 一个简单的和式
\[\sum_{k=1}^n{n \choose k}{n \choose k-1} = {2n+1 \choose n+1}-{2n \choose n}\]初见这个和式我们似乎感到无从下手，没有之前任何一个现有结论可以应用至此的样子，果真如此吗，让我们仔细看看这个和式。我们并没有看到$(-1)^k$这样的项，所以暂时不考虑反转上指标，相乘的两项是如此的相似，或许我们应该从对称性下手?
\[\sum_{k=1}^n{n \choose k}{n \choose k-1} = \sum_{k=1}^n{n \choose n-k}{n \choose k-1}\]看起来似乎没什么进展，但是基础稍好一些的读者或许能发现，这个形式似乎是某种卷积的样子(下指标和为定值)，让我们将这个等式抽象成更加简易一般的形式
\[\sum_{k=0}^n{s \choose n-k}{t \choose k}\]注意到这个式子的组合学解释，它的每一项都代表了从$s$项物体中选取$n-k$项，并从$t$项物体中选取$k$项的方法数，这实际上也就是从$s+t$项中选取$n$项的方法数（考虑将$n$项分别分配在$s$和$t$中 并求和），即有
\[\sum_{k=0}^n{s \choose n-k}{t \choose k} = {s+t \choose n}\]这个精妙的结论称为组合式的范德蒙德卷积（Vandermonde Convolution），而论证这个结论的方法叫做组合学论证法（Combinatorial Argument）。尽管我个人并不太喜欢这种论证的方法，但是不得不说，很多时候它还是挺有用的。由范德蒙德卷积（以下简称卷积）我们可以推导出一些有趣的结论，譬如当$s=t=n$的时候，则有:
\[\sum_{k=0}^n{n \choose n-k}{n \choose k} =\sum_{k=0}^n{n \choose k}^2 = {2n \choose n}\]即杨辉三角一行上各数的平方和。牢牢记住这个卷积式，它是我们求组合式和式的基础。回到之前的和式，有了卷积之后，这个题目变得异常容易起来，
\[\begin{align} &\sum_{k=1}^n{n \choose k}{n \choose k-1} \\ &= \sum_{k=1}^n{n \choose n-k}{n \choose k-1} \\ &= {2n \choose n-1} = {2n+1 \choose n+1}-{2n \choose n} \\ \end{align}\]问题解决了。不过实际上还有一种更简单的方法甚至不需要卷积式。我们考虑使用二项式定理来证明它。
\[\sum_{k=0}^n{n \choose k}x^k = (1+x)^n\] \[\sum_{k=1}^{n+1}{n \choose k-1}x^k = x(1+x)^n\]则有:
\[(\sum_{k=0}^n{n \choose k}x^k) * (\sum_{k=1}^{n+1}{n \choose k-1}x^k) = x(1+x)^{2n}\]比较$x^n$的系数即可得到
\[\sum_{k=1}^n{n \choose k}{n \choose k-1} = {2n \choose n-1}\]我们永不要忘记组合数与二项式定理的关系，二项式定理往往能给我们提供绝佳的解决方案。
ex.2 更进一步的挑战
有时候或许会出现一些类似于交错级数的组合式和式，譬如
\[\sum_{k=0}^r {r-k \choose m} {s \choose k-t} (-1)^{k-t} = {r-t-s \choose r-t-m}, t, r, m \in \mathbb{N}_{\ge 0}\]看起来这个式子似乎和卷积式完全不搭边，对称性似乎也不那么好用，不过我们发现$(-1)$的指数和${s \choose k-t}$是一样的，这让我们回忆起了反转上指标，让我们来试试。
\[\begin{align} &\sum_{k=0}^r {r-k \choose m} {s \choose k-t} (-1)^{k-t} \\ &=\sum_{k=0}^r {r-k \choose m} {k-t-s-1 \choose k-t} \\ &=\sum_{k=0}^r {r-k \choose m} {k-t-s-1 \choose -s-1} \\ \end{align}\]他看起来像是将卷积反了过来，但是我们并不知道如何处理这让的式子，因而我们无法继续进行下去了，我们没法应用我们已经拥有的任何手段。这让我们陷入了困境。我们只好重新来过。既然如此，我们尝试反转${r-k \choose m}$试试。
\[\sum_{k=0}^r {r-k \choose m} {s \choose k-t} (-1)^{k-t}=\sum_{k=0}^r {m-r+k-1 \choose m} {s \choose k-t} (-1)^{k-t+m}\]依然没有任何头绪，我们需要处理这个$-r+k$，要让他不再出现在上指标之中，即，我们需要在反转之前于下指标中创造一个$r-k$。对，就是这样，我们通过对称来做到这一点。
\[\begin{align} &\sum_{k=0}^r {r-k \choose m} {s \choose k-t} (-1)^{k-t}\\ &= \sum_{k=0}^r {r-k \choose r-k-m} {s \choose k-t} (-1)^{k-t} \\ &=\sum_{k=0}^r {-m-1 \choose r-k-m} {s \choose k-t} (-1)^{r-t-m}\\ \end{align}\]简直是完美，我们创造出了一个卷积式（注意两个组合式的上标和下标）。
\[\sum_{k=0}^r {-m-1 \choose r-k-m} {s \choose k-t} (-1)^{r-t-m}={s-m-1 \choose r-t-m}(-1)^{r-t-m}={r-t-s \choose r-t-m}\]证毕，让我们再回到之前走进的死胡同，我们同样证明了一个新的恒等式，他大概是这个样子，将卷积倒转了过来。
\[\sum_{k=0}^r{r-k \choose m}{s+k \choose n} = {r+s+1 \choose m+n+1}, n, s, m, r \in \mathbb{N}_{\ge 0}\]真是漂亮，我们轻而易举的就得到了如此优美的两个式子。
ex.3 仍不满足
在此之前，我想要引入一个新的，复杂而鬼畜的和式，在此不会给出其具体的证明（或许在该篇的续中会给出，因为其一般情形下的证明相当复杂，这里的空白似乎有点不太够了），其形式如下
\[\sum_{k \ge 0}{r-tk \choose k}{s-t(n-k) \choose n-k}{r \over r-tk}={r+s+tn \choose n}, n \in \mathbb{N}\]我们试试看能不能利用这个鬼畜的东西得到一个关于下列和式的可行解。
\[\sum_{k \ge 0}{n+k \choose m+2k}{2k \choose k}{(-1)^k \over k+1}, m, n \in \mathbb{N}_{\ge 0}\]这个和式来源于<具体数学>，其一种可行的解法是，用一个由像${l+k \choose 2k}$的项组成的和式替代${n+k \choose m+2k}$，这样我们需要求一个有两个求和号的式子，并且需要密切注意上下指标的取值范围，这是繁琐而令人厌倦的。观察我们引入的那个和式，我们发现首要目标就是将待求和式变形为上指标和为常数，下指标和也为常数的形式，联想到ex.2中曾经使用过的方法，我们首先使用对称律。
\[\sum_{k \ge 0}{n+k \choose m+2k}{2k \choose k}{(-1)^k \over k+1}=\sum_{k \ge 0}{n+k \choose n-m-k}{2k \choose k}{(-1)^k \over k+1}\]接着反转上指标，注意到我们不反转${2k \choose k}$的原因是，采用对称律之后，其下指标k的符号不会改变，仍然和另外一个组合式的下指标相同，这样我们仍需要反转另一个组合式。
\[=\sum_{k \ge 0}{-m-2k-1 \choose n-m-k}{2k \choose k}{(-1)^{n-m} \over k+1}\]非常好，我们得到了我们想要的，我们还需要使得分式的分母与某个组合式的上指标相等，看样子我们需要将$k+1$某种形式的替换掉，之前使用过的方法似乎都没法做到这一点，不过我们还有一个规则没有使用，那便是吸收律，让我们试试它。
\[\frac{\binom{2k}{k}}{k+1} = \frac{\binom{2k+1}{k}}{2k+1}\]完美，我们用尽所有手段之后，得到了我们想要的东西。在最后一步应用上那个鬼畜的恒等式，最终过程看起来大概是这个样子。
\[\begin{align} &\sum_{k \ge 0}{n+k \choose m+2k}{2k \choose k}{(-1)^k \over k+1}\\ &=\sum_{k \ge 0}{n+k \choose n-m-k}{2k \choose k}{(-1)^k \over k+1}\\ &=\sum_{k \ge 0}{-m-2k-1 \choose n-m-k}{2k \choose k}{(-1)^{n-m} \over k+1}\\ &=\sum_{k \ge 0}{-m-2k-1 \choose n-m-k}{2k+1 \choose k}{(-1)^{n-m} \over 2k+1} \end{align}\]使用$(1，m-2n-1，-2，n-m)$替换掉鬼畜式中的$(r，s，t，n)$，得到
\[(-1)^{n-m}{-m \choose n-m} = {n-1 \choose n-m}\]4.后记
无论何时，遇到怎么样复杂的问题，在尝试完最后一种已知手段之前都不要放弃，并且要善于使用之前使用过的思路和方法，或是将新的问题归约为已知问题，就像我们在ex.3中所做的那样，这种思维方式叫最归化，正如G.Polya所言”如果你无法解出一个问题，那么一定是有一个更简单的问题你未能解决”。善于观察问题与现有手段的联系才能够帮助你快速解决问题。