About Pascal's Triangle

莫名其妙的发现

注意这个公式：

$$f(m,n)=\frac{1}{(m-1)!}\prod_{i=0}^{m-2}{(n+i)}$$

看上去有一种挺熟悉的感觉，但又说不上来。仔细想想…欸！当m=3时原式不就等于：

$$f(1,n)=\frac{n(n+1)}{2}$$

这不正是我们的求和公示吗！嘶…可哪里会用到这么个式子呢？我们小学或初中时可能会接触到这么个三角形：

_n=1
n=2 01_m=1
n=3 01 01_m=2
n=4 01 02 01_m=3
n=5 01 03 03 01_m=4
n=6 01 04 06 04 01_m=5
n=7 01 05 10 10 05 01_m=6
n=8 01 06 15 20 15 06 01_m=7
    01 07 21 35 35 21 07 01_m=8
...

这便是大名鼎鼎的杨辉三角，当然还有一位叫**布莱士·帕斯卡 ** (Blaise Pascal)的伟大数学家从组合公式中发现的规律：

$${n \choose k}=\frac{n}{k}·{n-1 \choose k-1}=\frac{n}{n-k}·{n-1 \choose k}$$

∴

$${n-1 \choose k-1}=\frac{k}{n}·{n \choose k},{n-1 \choose k}=\frac{n-k}{n}·{n-1 \choose k}$$

可见:

$${n \choose k}={n-1 \choose k-1}+{n-1 \choose k}$$

如果你有很好的递归直觉，便可得

$${n \choose k} = \begin{cases} 1, & \text{if } k = 0 \text{ or } k = n \\ {n-1 \choose k-1} + {n-1 \choose k}, & \text{otherwise} \end{cases}$$

其中 ${n \choose k}$ 就是帕斯卡三角中第 $n$ 行第 $k$ 个数。

如下是数值版本的帕斯卡三角：

假设在${i \choose j}$,(i > 1, j > 1)处∴${i \choose j}$ = ${i-1 \choose j-1}$ + ${i-1 \choose j}$即

$$f(i,j)=f(i-1,j)+f(i,j-1),(i > 1, j > 1)$$

$$f(i,j)=1,(i=1 \text{ or } j=1)$$

∵

$$f(i,j-1)= \begin{cases} 1,& i=1\text{ or }j=1\\ f(i-1,j-1)+f(i,j-2) & \text{otherwise} \end{cases}$$

以此类推直到${j-n=2}$时，剩

$$f(i,j-n-1)=f(i-1,j-n-1)=f(i-1,1)$$

∴

$$f(i,j)=\sum_{k=1}^{j-1}{f(i-1,j-k)}$$

而对于${\sum}$中的$f(i-k,j-1)$又可以用${\sum f(m,n)}$来表示，这样的话可能会有些棘手，所以我们可以换一种表达方式，

注意,

$$\begin{aligned} &f(1, j) \quad =\ 1 \\ &f(2, j) \quad =\ \sum_{k=1}^{j} f(1, k) = 1 \cdot j = j \\ &f(3, j) \quad =\ \sum_{k=1}^{j} f(2, k) = \frac{(1 + j) \cdot j}{2} \end{aligned}$$

对于 $f(4, j)$ 可以将 $f(3, j)$ 化简：

$$\begin{aligned} &f(3, j) \quad =\ \frac{1}{2}j^2 + \frac{1}{2}j \\ &f(4, j) \quad =\ \sum_{k=1}^{j} f(3, k) = \sum_{k=1}^{j} \left( \frac{1}{2}k^2 + \frac{1}{2}k \right) \\ &\phantom{f(4, j)} \quad =\ \frac{1}{2} \sum_{k=1}^{j} k^2 + \frac{1}{2} \sum_{k=1}^{j} k \\ &\phantom{f(4, j)} \quad =\ \frac{1}{2} \cdot \frac{j(j+1)(2j+1)}{6} + \frac{1}{2} \cdot \frac{j(j+1)}{2} \\ &\phantom{f(4, j)} \quad =\ \frac{j(j+1)(j+2)}{6}\\ \end{aligned}$$

同样可得

$$f(5,j)=\frac{j(j+1)(j+2)(j+3)}{24}$$

欸，好像有个规律！赶紧来证明一下,看一看帕斯卡三角：

$$\begin{array}{ccccccccc} &&&& {0 \choose 0} &&&& \\[8pt] &&& {1 \choose 0} && {1 \choose 1} &&& \\[8pt] && {2 \choose 0} && {2 \choose 1} && {2 \choose 2} && \\[8pt] & {3 \choose 0} && {3 \choose 1} && {3 \choose 2} && {3 \choose 3} & \\[8pt] {4 \choose 0} && {4 \choose 1} && {4 \choose 2} && {4 \choose 3} && {4 \choose 4} \\ \end{array}$$

每个元素 ${n \choose k}$ 表示帕斯卡三角第 $n$ 行第 $k$ 列的数。
可知

$$f(i,j)={i+j-1 \choose i-1}$$

哈哈！我们惊喜地发现我们闹了一个笑话，推出了一个更复杂的公式。但是，不能说一点用没有，若我们对两边加上对数：

$$\ln(f(m,n))=\ln(\frac{1}{(m-1)!}\prod_{i=0}^{m-2}{(n+i)}))\\ \ln(f(m,n))=\ln(\frac{1}{(m-1)!})+\ln(\prod_{i=0}^{m-2}{n+i})\\ \ln(f(m,n))=-\ln((m-1)!)+\sum_{i=0}^{m-2}{\ln(n+i)}\\ \ln(f(m,n))=\sum_{i=0}^{m-2}{\ln(n+i)}-\sum_{i=1}^{m-1}{\ln(m-i)}\\ \ln(f(m,n))=\sum_{i=0}^{m-2}{\ln(n+i)}-\sum_{i=0}^{m-2}{\ln(m-i-1)}\\ \ln(f(m,n))=\sum_{i=0}^{m-2}{\ln(\frac{n+i}{m-i-1})}\\ f(m,n)=\prod_{i=0}^{m-2}{\frac{n+i}{m-i-1}}$$

∴

$${m+n-1 \choose m-1}=\prod_{i=0}^{m-2}{\frac{n+i}{m-i-1}}$$

∴

$${x \choose y}=\prod_{i=0}^{y+1}{\frac{x-y+i}{y-i}}=\prod_{i=0}^{y+1}{(\frac{x}{y-i}-1)}$$

这样当面对对组合的拆解就不用害怕了。