杨辉三角 pro max

· · 个人记录

数学作业备份

Hockey-stick identity

我们接下来考察一个很重要的组合恒等式——Hockey-stick identity/Christmas stocking.（中文直译大概是曲棍球棒定理/圣诞袜定理）

这个恒等式的形式是：

\displaystyle{ \sum^n_{i=r}{i\choose r}={n+1\choose r+1} \qquad \text{ for } n,r\in\mathbb{N}, \quad n\geq r }

证明1：组合证明

我们考虑分配 n 个无标号小球到 k 个有标号盒子里，显然通过插板法我们得方案数：

\binom{n + k - 1}{k - 1}

我们考虑这是如何做到的，我们考虑每次对于 0 \leq i \leq n，我们钦定先给编号最大的盒子 i 个球。那么这个问题就变成了把 n - i 个球分到 k - 1 个盒子里，依次考虑，那么我们就可以得到方案数为

\sum_{i=0}^n\binom{n+k-2-i}{k-2}

联立以上二式，定义 n^{\prime} = n + k - 2,x = k - 2,并且我们注意到有 n^{\prime} - n = k - 2 = x

所以我们就可以得到

\displaystyle{ \binom{n'+1}{ r+1}=\sum_{i=0}^n \binom {n'-i}r = \sum_{i=r}^{n'} \binom {i}r . }

证明2：代数证明

我们考虑应用一个很经典的思考方法：差分法来解决。

\begin{aligned} \sum_{t=\color{blue}k}^n\binom tk &= \sum_{t=k}^n\left[ \binom {t+1}{k+1}-\binom {t}{k+1}\right]\\ &=\sum_{t=\color{green}k}^{\color{green}n}\binom {\color{green}{t+1}}{k+1} - \sum_{t=k}^n \binom t{k+1}\\ &=\sum_{t=\color{green}{k+1}}^{\color{green}{n+1}}\binom {\color{green}{t}}{k+1} - \sum_{t=k}^n \binom t{k+1}\\ &=\binom{n+1}{k+1}-\underbrace{\binom k{k+1}}_0\\ &=\binom{n+1}{k+1}. \end{aligned}

证明3：生成函数

我们有

\displaystyle{ X^r + X^{r+1} + \dots + X^{n} = \frac{X^r-X^{n+1}}{1-X} }

令 X = 1 + x，然后考察 x^r 的系数就做完了。

证明4：数学归纳法

略。

那么，这个东西为什么叫做曲棍球棒等式呢？我们考虑杨辉三角上是这样的：

\displaystyle{ \begin{array}{c} 1 \\ 1 \quad 1 \\ 1 \quad 2 \color{blue}\quad 1 \\ 1 \quad 3 {\color{blue}\quad 3} \quad 1 \\ 1 \quad 4 {\color{blue}\quad 6} \quad 4 \quad 1 \\ 1 \quad 5 {\color{blue}\quad 10} \quad 10 \quad 5 \quad 1 \\ 1 \quad 6 \quad 15 {\color{green}\quad 20} \quad 15 \quad 6 \quad 1 \\ \end{array} }

很像一个曲棍球棒！

这个东西我也不知道有啥用，但是做题用到了：https://codeforces.ml/contest/1549/problem/E

大概是这个东西。

从行的角度考察杨辉三角