EM@组合数学@朱世杰恒等式@曲棍球恒等式Hockey-stick identity

文章目录

- refs
- 朱世杰恒等式(曲棍球恒等式)👺
- - 变形
  - 证明
  - - 递归方法
    - 组合方法
- 公式形式总结
- 应用
- - 基础套用
  - 等幂求和问题

refs

Hockey-stick identity - Wikipedia

朱世杰恒等式(曲棍球恒等式)👺

朱世杰恒等式是组合数的一阶求和公式。元朝数学家朱世杰在《四元玉鉴》中，利用垛积术、招差术给出：
$\sum_{i=a}^{n} \binom{i}{a} = \binom{n+1}{a+1}$

将上式记为式(0)

变形

若以 $m - 1$ 代 $n$ ,得到式(1)
$\sum_{i=a}^{m-1} \binom{i}{a} = \binom{m}{a+1}$
与上式作差，写成：记为式(2)
$\sum_{i=m}^{n} \binom{i}{a} = \binom{n+1}{a+1} - \binom{m}{a+1}$

证明

递归方法

欲证式(0),即证式(2),而式(2)移项得到式(3)
$\binom{m}{a+1}+\sum_{i=m}^{n} \binom{i}{a} = \binom{n+1}{a+1}$
将其展开得到式(4)如下:
$\binom{m}{a+1} + \binom{m}{a} + \binom{m+1}{a} + \cdots + \binom{n}{a} =\binom{n+1}{a+1},$
最后证明式(0)等价于证明式(4)

可以反复使用帕斯卡法则合并式(4)等号左边首两项,最终得到其等于等号右边的结论

帕斯卡法则如下:
$\binom{n-1}{k} + \binom{n-1}{k-1} = \binom{n}{k}$
从排列组合的角度(构造适当的排列组合问题模型)容易证明该等式

组合方法

从 $n$ 元集 $\{a_1, a_2, a_3, \ldots, a_n\}$ 选 $r$ 个元素，有 $\binom{n}{r}$ 种方法。将这些方法分类:

必有 $a_1$ 时，再在 $n - 1$ 个元素中选 $r - 1$ 个元素；这类方法有 $\binom{n-1}{r-1}$ 种
排除 $a_{1}$ 时,在 $n - 1$ 个元素中选 $r$ 个元素,这类方法有 $\binom{n-1}{r}$ 种;我们在这种大类情况在继续细分
- 排除 $a_1$ ，且必有 $a_2$ 时，在 $n - 2$ 个元素中选 $r - 1$ 个元素；这类方法有 $\binom{n-2}{r-1}$ 种
- 排除 $a_1$ , 并排除 $a_{2}$ (即排除 $a_1,a_2$ ),在 $n - 2$ 个元素中选 $r$ 个元素,这类方法有 $\binom{n-2}{r}$ 种
- 排除 $a_{1},a_{2}$ ,情况下
  - 包含 $a_{3}$ 的方法数有 $\binom{n-3}{r-1}$
  - 排除 $a_{3}$ ,的方法数有 $\binom{n-3}{r}$
  - 排除 $a_{1},a_{2},a_{3}$ 情况下
    - 包含 $a_{4}$ 的方法数 $\binom{n-4}{r-1}$
    - 排除 $a_{4}$ 的方法数 $\binom{n-4}{r}$
    - …
如此类推，直到必有 $a_{n-r+1}$ 时，在 $r - 1$ 个元素中选 $r - 1$ 个元素,此时方法数为 $1$ ,为了统一,仍然记为 $\binom{r-1}{r-1}$
- 这里 $a_{n-r+1}$ 的下标如何确定?对于 $a_{1}\cdots{a_{x}}\cdots{a_{n}}$ ,最后一次类推处理,要求 $a_{x}\cdots_{a_{n}}$ 有 $r$ 个元素,那么 $n - x + 1$ 是 $a_{x}\cdots{a_{n}}$ 的元素数量,所以令 $n - x + 1 = r$ ,得出 $x = n - r + 1$
- 不过在这里我们不是非得求出 $x$ ,只需要知道存在这么一个 $x$ 使得剩余元素恰好足够 $r$ 个
整理
$\binom{n-1}{r-1}+\binom{n-2}{r-1}+\cdots+\binom{r-1}{r-1}=\binom{n}{r}$

将上述等式改写为求和式表示(可以先将等式左边调整一下顺序在改写为求和式)
$\binom{r-1}{r-1}+\cdots+\binom{n-2}{r-1}+\binom{n-1}{r-1}$

$\sum\limits_{k=r-1}^{n-1}\binom{k}{r-1}=\binom{n}{r}$

为了形式的美观性,由求和式的性质特点,等价变形求和指标,得到
$\sum_{k=r}^{n} \binom{k-1}{r-1} = \binom{n}{r}$
或者求和指标变量用 $i$ 来表示,总结如下

公式形式总结

$\sum_{i=a}^{n} \binom{i-1}{a-1} = \binom{n}{a}$
$\sum_{i=a}^{n} \binom{i}{a} = \binom{n+1}{a+1}$

如果将恒等式的左右两端对调,可以说,朱世杰恒等式将一个组合数 $\binom{n}{a}$ 展开成 $\binom{n-1}{r-1}+\binom{n-2}{r-1}+\cdots+\binom{r-1}{r-1}$ 共 $n - a + 1$ 项
- 形式2中,将左边的求和式的上标和下标分别加一,分别作为等式右边 $\binom{r_1}{r_2}$ 中的 $r_1,r_2$
形式1和形式2其实是完全等价的
- 令 $n = n - 1$ , $a = a - 1$ ,带入到形式2,并等价调整求和号的上下标以及被求和表达式,就得到形式1
- 或者令 $n = n + 1$ , $a = a + 1$ ,带入形式1,也可以得到形式2
  - $\sum\limits_{i=a+1}^{n+1}\binom{i-1}{a}$ = $\sum\limits_{i=a}^{n}\binom{i}{a}$ = $\binom{n+1}{a+1}$

应用

基础套用

利用朱世杰恒等式计算 $\binom{4}{2}$

分别用形式1,2计算

$\binom{4}{2}$ = $\sum\limits_{i=2}^{4}\binom{i-1}{1}$ = $\binom{1}{1}+\binom{2}{1}+\binom{3}{1}$ = $6$
$\binom{4}{2}$ = $\binom{3+1}{1+1}$ = $\sum\limits_{i=1}^{3}\binom{i}{1}$ = $6$

等幂求和问题

例如：
$\sum_{i=1}^{n} i = \sum_{i=1}^{n} \binom{i}{1} = \binom{n+1}{2}$

$\sum_{i=1}^{n} i(i+1)$ = $\sum_{i=1}^{n} \binom{i+1}{2}$ = $2\sum\limits_{i=2}^{n+1}\binom{i}{2}$ = $\binom{n+2}{3}$

上面的例子中出现的 $\sum_{i=1}^{n} \binom{i+1}{2}$ ,求和符号和被求和式的形式不符合朱世杰恒等式的基础(标准)形式,我们根据求和符号的变形特点对该式子变形,将求和号的指标变量 $i$ 的起始值改为 $2$ (也就是增加1,此时需要调整商标 $n$ ,也增加1,最后将求和式中的指标变量减去1)