组合恒等式-基于六个基本组合恒等式

  |  

摘要: 六个基本组合恒等式

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


组合的定义:

二项式定理:

基于组合的定义以及二项式定理,我们可以得到六个基本组合恒等式:

  • (1) $\binom{n}{k} = \binom{n}{n-k}$
  • (2) $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$ (Pascal 恒等式)
  • (3) $\binom{n}{k} = \frac{n}{k}\binom{n-1}{k-1}$
  • (4) $\binom{n}{k}\binom{k}{m} = \binom{n}{m}\binom{n-m}{k-m} = \binom{n}{k-m}\binom{n-k+m}{m}$
  • (5) $\sum\limits_{i=0}\limits^{n}\binom{n}{i} = 2^{n}$
  • (6) $\sum\limits_{i=0}\limits^{n}(-1)^{i}\binom{n}{i} = 0$

这些组合恒等式中,(1)(2)(4) 可以直接从组合的定义式推导出;在 (4) 中令 $m = 1$ 即得到 (3);在二项式定理中取 $x=1$ 和 $x=-1$ 可以得到 (5)(6)。

一些复杂的组合恒等式往往可以通过几个基本的组合恒等式,经过归纳、递推、指标变换等方法得到。

其中指标变换需要注意同事更换求和的上下限,例如:

下面我们看一些基于六个基本组合恒等式来推导别的组合恒等式的例子。


直接使用基本恒等式

$S_{n, m} = \sum\limits_{k=0}\limits^{m}(-1)^{k}\binom{n}{k}, m \leq n$

由基本恒等式 (6) 我们知道 $m = n$ 时,$S(n, m) = 0$;

下面考虑 $m < n$ 的情况。利用基本恒等式 (2)


$p_{n} = \sum\limits_{k=0}\limits^{n}\frac{1}{k+1}\binom{n}{k}$, $q_{n} = \sum\limits_{k=0}\limits^{n}(-1)^{k}\frac{1}{k+1}\binom{n}{k}$

基本恒等式 (3)

代入 $p_{n}$、$q_{n}$ 并应用基本恒等式 (5)(6) 即得:


基本恒等式 + 指标变换

$\sum\limits_{k=0}\limits^{n}\binom{2n}{k} = 2^{2n-1} + \frac{1}{2}\binom{2n}{n}$

记 $a_{n} = \sum\limits_{k=0}\limits^{n}\binom{2n}{k}$,$b_{n} = \sum\limits_{k=n+1}\limits^{2n}\binom{2n}{k}$,由基本恒等式 (5)

对 $b_{n}$ 作指标变换:$k = 2n - l$

代入即得:


$\sum\limits_{k=1}\limits^{n}k^{2}\binom{n}{k}$

基本恒等式 (3)

对右边作指标变换 k - 1 = l,得:

因此:


$S_{mn} = \sum\limits_{k=m}\limits^{n}(-1)^{k}\binom{n}{k}\binom{k}{m} = (-1)^{m}\delta_{mn}$

克罗内克(Kronecker)函数如下:

$m = n$ 时,$S_{mn} = (-1)^{m}\binom{m}{m}\binom{m}{m} = (-1)^{m}$

$m \neq n$ 时,利用基本恒等式 (4)


基本恒等式 + 递推

$\sum\limits_{k=0}\limits^{n}(-1)^{k}\binom{n}{k}\frac{m}{m + k} = (\binom{m+n}{n})^{-1}$

令 $b_{n} = \sum\limits_{k=0}\limits^{n}(-1)^{k}\binom{n}{k}\frac{m}{m + k}$,利用基本恒等式 (2)(3)(6):

得到递推公式

由递推公式可以得到 $b_{n} = (\binom{m + n}{n})^{-1}$


$\sum\limits_{k=1}\limits^{n}(-1)^{k+1}\frac{1}{k}\binom{n}{k}=\sum\limits_{i=1}\limits^{n}\frac{1}{i}$

利用基本恒等式 (2)(3):

记 $f_{n} = \sum\limits_{k=1}\limits^{n}(-1)^{k+1}\frac{1}{k}\binom{n}{k}$,则:

得到递推公式

由递推公式得到:$f_{n} = 1 + \frac{1}{2} + \cdots \frac{1}{n}$


$\sum\limits_{k=0}\limits^{2n-1}(-1)^{k+1}(k+1)(\binom{2n}{k})^{-1}$

记 $y_{n} = \sum\limits_{k=0}\limits^{2n-1}(-1)^{k+1}(k+1)(\binom{2n}{k})^{-1}$,利用基本恒等式 (3)

于是:

作指标变换 $l = 2n-k-1$,当 $k$ 从 0 变到 $2n-1$ 时,$l$ 从 $2n-1$ 变到 0,因此:

因此 $y_{n} = 0$

类似的方法可以证明 $\sum\limits_{k=1}\limits^{2n-1}(-1)^{k-1}\frac{n-k}{\binom{2n}{k}} = 0$。


$\sum\limits_{k=1}\limits^{2n-1}(-1)^{k-1}(\binom{2n}{k})^{-1}$

记 $a_{n} = \sum\limits_{k=1}\limits^{2n-1}(-1)^{k-1}(\binom{2n}{k})^{-1}$,$b_{n} = \sum\limits_{k=1}\limits^{2n-1}(-1)^{k-1}k(\binom{2n}{k})^{-1}$。

则由前面的结论 $\sum\limits_{k=0}\limits^{2n-1}(-1)^{k+1}(k+1)(\binom{2n}{k})^{-1} = 0$:

再由前面的结论 $\sum\limits_{k=1}\limits^{2n-1}(-1)^{k-1}\frac{n-k}{\binom{2n}{k}} = 0$:

两式相加,得到 $a_{n} = \frac{1}{n+1}$,$b_{n} = na_{n} = \frac{n}{n+1}$


基本恒等式 + 归纳

$\sum\limits_{k=1}\limits^{n-1}\frac{1}{k(n-k)}\binom{2(k-1)}{k-1}\binom{2(n-k-1)}{n-k-1}$

下面证明 $\sum\limits_{k=1}\limits^{n-1}\frac{1}{k(n-k)}\binom{2(k-1)}{k-1}\binom{2(n-k-1)}{n-k-1} = \frac{1}{n}\binom{2(n-1)}{n-1}, n=2,3,\cdots$

由于 $\frac{n}{k(n-k)} = \frac{1}{k} + \frac{1}{n-k}$,将待证明公式两边乘以 $n$:

在右边第二个和式中令 $n - k = l$ 得:

因此可以看到,右边的两个和式是相同的,因此得到以下公式,该公式后面要用到,记为【公式 A】:

于是,待证明公式变成:

上式可以用数学归纳法证明。首先 $n=2$ 时成立。假设 $n=m$ 时成立,当 $n=m+1$ 时,上式左端为:

注意到:

代入得:

由归纳假定:

以及前面的【公式 A】:

得:

因此待证公式在 $n = m + 1$ 时成立。最终得证公式如下:

该公式在推导 $\sqrt{1+x}$ 的展开式时需要用到。


Share