混凝土数学学习笔记——二项式系数

前言

大战混凝土。

定义

通常的定义是 $\dbinom nk$ 表示在 $n$ 个元素里挑选 $k$ 个的方案数。

为了拓宽定义，我们先定义下降幂 $r^{\underline k}$ 为：

$$r^{\underline k}=\prod_{i=1}^{k}(r-i+1),\quad r\in\mathbf R,k\in\mathbf Z$$

比如 $5^{\underline 3}=5\times4\times3=60$，$\left(\dfrac 12\right)^{\underline2}=\dfrac12\cdot\left(-\dfrac12\right)-\dfrac14$。

现在我们有了二项式系数的新定义

$$\dbinom rk= \begin{cases} \dfrac{r^{\underline k}}{k!},&k\ge 0\\ 0,&k<0 \end{cases}\quad(r\in\mathbf R,k\in\mathbf Z)$$

这个定义将原来 $\dbinom nk$ 的定义域从 $\mathbf N\times\mathbf N$ 拓宽到了 $\mathbf R\times\mathbf Z$。这是一个非常大的突破。

如果参数是自然数 $n\ge k\ge 0$，那么这个式子还可以被写成

$$\dbinom nk=\dfrac{n!}{k!(n-k)!}$$

基本性质

在定义的基础上我们可以发现一些有用的性质。

$$\dbinom nk=\dbinom n{n-k}\tag1,\quad n\ge 0$$

原因很简单，将上公式中 $k$ 和 $n-k$ 地位对调即可。对于 $k>n$ 和 $k<0$ 的情况等式两边都为 $0$。

---

$$\dbinom rk=\dfrac rk\dbinom{r-1}{k-1}\tag2,\quad k\neq0$$

考虑将两侧展开

$$\dbinom rk=\dfrac{r^{\underline k}}{k!}=\dfrac rk\cdot\dfrac{(r-1)^{\underline{k-1}}}{(k-1)!}=\dfrac rk\dbinom{r-1}{k-1}$$

上述等式还可以被表达成一个有用的形式

$$k\dbinom rk=r\dbinom{r-1}{k-1}\tag3$$

另一个形式可以将下标保持不变：

$$(r-k)\dbinom rk=r\dbinom{r-1}k\tag4$$

其原因也是简单的：

$$\begin{aligned} (r-k)\dbinom rk&=(r-k)\dbinom r{r-k}\\ &=r\dbinom{r-1}{r-k-1}=r\dbinom{r-1}{k} \end{aligned}$$

---

下一个等式是我们熟知的组合递推式：

$$\dbinom rk=\dbinom{r-1}{k-1}+\dbinom{r-1}k\tag5$$

在 $r$ 为正整数时该式子的组合意义为：在 $n$ 个元素里选择 $k$ 个，可以先选择第 $1$ 个，然后在剩下的 $n-1$ 个元素里选择 $k-1$ 个；也可以不选择第一个，然后在剩下 $n-1$ 个元素里选择 $k$ 个。两者的值是相等的。

在 $r$ 是实数的时候，我们可以用上面的公式进行证明：

$$\begin{aligned} &\because (r-k)\dbinom rk=r\dbinom{r-1}k,k\dbinom rk=r\dbinom{r-1}{k-1}\\ &\begin{aligned} \ \therefore(r-k)\dbinom rk+k\dbinom rk&=r\dbinom{r-1}{k}+r\dbinom{r-1}{k-1}\\ r\dbinom rk&=r\left[\dbinom{r-1}{k-1}+\dbinom{r-1}k\right]\\ \dbinom rk&=\dbinom{r-1}{k-1}+\dbinom{r-1}k \end{aligned} \end{aligned}$$

上过程在所有 $r\neq 0$ 时成立，而在 $r=0$ 时可以简单特判。

当然还可以根据定义：

$$\begin{aligned} \dbinom{r-1}{k-1}+\dbinom{r-1}k&=\dfrac{(r-1)^{\underline{k-1}}}{(k-1)!}+\dfrac{(r-1)^{\underline k}}{k!}\\ &=\dfrac{k(r-1)^{\underline{k-1}}}{k!}+\dfrac{(r-1)^{\underline{k-1}}\cdot(r-k)}{k!}\\ &=\dfrac{r\cdot(r-1)^{\underline{k-1}}}{k!}=\dfrac{r^{\underline k}}{k!}=\dbinom rk \end{aligned}$$

---

展开 $(5)$ 我们可以得到一系列有用的恒等式。

$$\begin{aligned} \sum_{k=0}^n\dbinom{r+k}k&=\dbinom{r}{-1}+\dbinom{r}{0}+\sum_{k=1}^n\dbinom{r+k}k\\ &=\dbinom{r+1}{0}+\dbinom{r+1}1+\sum_{k=2}^n\dbinom{r+k}k\\ &=\cdots\\ &=\dbinom{r+n}{n-1}+\dbinom{r+n}n=\dbinom{r+n+1}n \end{aligned}\tag 6$$

比如 $\dbinom10+\dbinom21+\dbinom32+\dbinom43=4=\dbinom{1+3+1}{3}=\dbinom53$。

---

另一个有用的式子有相似的形式：

$$\begin{aligned} \sum_{k=0}^n\dbinom km&=\dbinom 0{m+1}+\dbinom0m+\sum_{k=1}^n\dbinom km\\ &=\dbinom 1{m+1}+\dbinom1m+\sum_{k=2}^n\dbinom km\\ &=\cdots\\ &=\dbinom{n}{m+1}+\dbinom nm=\dbinom{n+1}{m+1} \end{aligned}\tag7$$

相当于是对杨辉三角的列求部分和。

二项式定理

最基础的二项式定理是这样的：

$$(x+y)^n=\sum_{k=0}^n\dbinom nkx^ky^{n-k}\tag8,\quad n\in\mathbf N$$

两个特殊情况是：

1. 当 $x=y=1$ 时原式变为

$$\sum_{k=0}^n\dbinom nk=2^n\tag9$$

1. 当 $x=-1,y=1$ 时原式为（$n\neq0$）

$$\sum_{k=0}^n(-1)^k\dbinom nk=0\tag{10}$$

上标取反

$$\dbinom rk=(-1)^k\dbinom{k-r-1}{k} \tag{11}$$

证明起来很简单，因为

$$\begin{aligned} r^{\underline k}&=r(r-1)\cdots(r-k+1)\\ &=(-1)^k(-r)(-r+1)\cdots(-r+k-1)\\ &=(-1)^k(k-r+1)^{\underline k} \end{aligned}$$

根据这个性质可以得到

$$\begin{aligned} \sum_{k=0}^m(-1)^k\dbinom rk&=\sum_{k=0}^m\dbinom{k-r-1}{k}\\ &=\dbinom{m-r}{m}\\ &=(-1)^m\dbinom{r-1}{m} \end{aligned}\tag{12}$$

散装公式

$$\dbinom nk\dbinom km=\dbinom nm\dbinom{n-m}{k-m}\tag{13}$$

证明可以直接看定义：

$$\begin{aligned} \dbinom nk\dbinom km&=\dfrac{n!}{k!(n-k)!}\cdot\dfrac{k!}{m!(k-m)!}\\ &=\dfrac{n!}{(n-k)!m!(k-m)!}\\ &=\dfrac{n!}{m!(n-m)!}\cdot\dfrac{(n-m)!}{(n-k)!(k-m)!}\\ &=\dbinom nm\dbinom{n-m}{k-m} \end{aligned}$$

---

$$\sum_{k}\dbinom r{m+k}\dbinom s{n-k}=\dbinom{r+s}{m+n}\tag{14}$$

证明需要一定技巧，我们令 $k^\prime=k+m$，令 $n^\prime=n+m$，这样我们消掉了 $m$，原式变成

$$\sum_{k^\prime}\dbinom r{k^\prime}\dbinom{s}{n^\prime-k^\prime}$$

如果 $r,s$ 都是正整数，那么这个式子有很清晰的组合意义：在由 $r$ 个红球和 $s$ 个蓝球组成的 $r+s$ 个球中选择 $n^\prime$ 个，可以枚举所有选择的红球数量 $k^\prime$，那么此时选择蓝球的数量是 $n^\prime-k^\prime$，那么此时方案数为 $\dbinom r{k^\prime}\dbinom{s}{n^\prime-k^\prime}$，而总方案数显然是 $\dbinom{r+s}{n^\prime}$。

---

$$\sum_{k}\dbinom l{m+k}\dbinom s{n+k}=\dbinom{l+s}{l-m+n}\tag{15},\quad l\in\mathbf N$$

利用公式 $(1)$ 将项 $\dbinom l{m+k}$ 变为 $\dbinom l{l-m-k}$，可以直接套 $(14)$。

练习题

1

求下式的封闭形式：

$$\sum_{k=0}^m\dbinom mk\bigg/\dbinom nk,\quad n\ge m\ge 0$$

---

首先我们知道

$$\dbinom nm\dbinom mk=\dbinom nk\dbinom{n-k}{m-k}$$

因此我们移项得到

$$\dbinom mk\bigg/\dbinom nk=\dbinom{n-k}{m-k}\bigg/\dbinom nm$$

因此原式化简为

$$\sum_{k=0}^m\dbinom{n-k}{m-k}\bigg/\dbinom nm$$

现在看 $\sum\limits_{k=0}^m\binom{n-k}{m-k}$ 的值，我们考虑将 $k$ 的符号变为正的之后套用 $(6)$，因此得到

$$\begin{aligned} \sum_{k=0}^m\dbinom{n-k}{m-k}&=\sum_{k=0}^m\dbinom{n-(m-k)}{m-(m-k)}\\ &=\sum_{k=0}^m\dbinom{n-m+k}{k}=\dbinom{n+1}{m} \end{aligned}$$

所以原式就是

$$\dbinom{n+1}m\bigg/\dbinom nm=\dfrac{n+1}{n-m+1}$$

2

求下式的封闭形式：

$$T=\sum_{k=0}^nk\dbinom{m-k-1}{m-n-1}$$

---

我们发现我们可以转化为

$$S=\sum_{k=0}^n(m-k)\dbinom{m-k-1}{m-n-1}=m\sum_{k=0}^n\dbinom{m-k-1}{m-n-1}-T$$

而

$$(m-k)\dbinom{m-k-1}{m-n-1}=(m-n)\dbinom{m-k}{m-n}$$

因此

$$\begin{aligned} S&=(m-n)\sum_{k=0}^n\dbinom{m-k}{m-n}\\ &=(m-n)\sum_{k=m-n}^m\dbinom{k}{m-n}\\ &=(m-n)\left[\dbinom{m+1}{m-n+1}-\dbinom{m-n}{m-n+1}\right]\\ &=(m-n)\dbinom{m+1}{m-n+1} \end{aligned}$$

接下来我们要求 $\sum\limits_{k=0}^n\binom{m-k-1}{m-n-1}$，而这等于 $\dbinom{m}{m-n}$，因此

$$\begin{aligned} T&=m\dbinom m{m-n}-(m-n)\dbinom{m+1}{m-n+1}\\ &=m\dbinom m{m-n}-(m-n)\dfrac{m+1}{m-n+1}\dbinom m{m-n}\\ &=\dfrac{n}{m-n+1}\dbinom{m}{n} \end{aligned}$$

3

求下式的封闭形式：

$$\sum_kk\dbinom nk\dbinom rk,\quad n\in\mathbf N$$

---

首先那个单独的 $k$ 不好处理，考虑将其与一个二项式系数合并起来。

如果和 $\dbinom rk$ 合并，因为

$$k\dbinom rk=r\dbinom{r-1}{k-1}$$

所以原式就是

$$r\sum_k\dbinom nk\dbinom{r-1}{k-1}=r\dbinom{n+r-1}{n-1}$$

套上 $(15)$。如果将 $k$ 和 $\dbinom nk$ 合并我们发现式子变成

$$n\sum_{k}\dbinom rk\dbinom{n-1}{k-1}$$

而 $n-1$ 可能小于 $0$，因此 $(15)$ 不能用。

4

求下式的封闭形式：

$$\sum_{k\ge 0}\dbinom{n+k}{2k}\dbinom{2k}k\dfrac{(-1)^k}{k+1},\quad n\in\mathbf N$$

---

根据 $(13)$ 我们知道

$$\sum_{k\ge 0}\dbinom{n+k}{2k}\dbinom{2k}k\dfrac{(-1)^k}{k+1}=\sum_{k\ge 0}\dbinom{n+k}k\dbinom{n}{k}\dfrac{(-1)^k}{k+1}$$

接下来我们考虑把 $\dfrac{1}{k+1}$ 消去，因为 $(3)$ 可得

$$\dbinom{n+1}{k+1}(k+1)=\dbinom nk(n+1)$$

所以原式就是

$$\dfrac1{n+1}\sum_{k\ge0}\dbinom{n+k}k\dbinom{n+1}{k+1}(-1)^k$$

通过 $(11)$ 我们试着反转 $\dbinom{n+k}k$ 的上标，可以得到

$$\begin{aligned} \dfrac1{n+1}\sum_{k\ge0}\dbinom{n+k}k\dbinom{n+1}{k+1}(-1)^k&=\dfrac1{n+1}\sum_{k\ge 0}\dbinom{-n-1}{k}\dbinom{n+1}{k+1}\\ &=\dfrac1{n+1}\dbinom0n=[n=0] \end{aligned}$$

最后一步的转化可以通过 $(15)$ 推得。