帕斯卡三角

所谓方法就是用过两次的手法。

帕斯卡三角形的边界条件：

C(n,0)=1

C(n,n)=1

帕斯卡三角形的递归公式：

C(n+1,r)=C(n,r-1)+C(n,r)

从计数的角度看,C(n,r)可以被认为是帕斯卡三角形的边界边界条件和递归公式所确定。

二项式系数的显公式：

C(n,r)=n*(n-1)*...*(n-r+1)/1*2*...*r

证明：

设C(n,0)=1

当r = n时,C(n,r)=C(n,n)=n*(n-1)*...*1/1*2*...*n=1

从而C(n,n)=1

所以公式对于r=1和r=n都成立了,我们只要证明1<r<n的情况成立就可以了。

引理1断言：对n=1是成立的,这是显然的。[显式公式对n=1成立,因为在这种情形下,r可能取的值只有r=0和r=1则会两个,而这在前面已经讲了。]

引理2断言：如果命题对于某一个n成立,那么它对于n+1也成立。

这样命题对于一切n都成立了,因为引理1对n=1成立,于是根据引理2,它对于n=2成立,同样道理,对于n=3也成立,这样可以无限下去，于是我们只要证明引理2就行了。

假设：

C(n,r)=n*(n-1)*...*(n-r+1)/1*2*...*r

对于一切r=0,1,...n都成立。

特别地,对于r>=1时,

C(n,r-1)=n*(n-1)*...*(n-r+2)/1*2...*(r-1)

将两个式子加起来,我们得到：

C(n+1,r)=C(n,r-1)+C(n,r)=

n*(n-1)*...*(n-r+1)/1*2*...*r+n*(n-1)*...*(n-r+2)/1*2...*(r-1)=

(n+1)*n*(n-1)*...*(n-r+1)/1*2*...*(r-1)

于是对n+1命题也成立.所以引理2得证。

我们有三种不同的方法去引出帕斯卡三角形里的数--二项式系数

1.几何方法

二项式系数是街道网络里介于两个给定街角间的最短锯齿状道路的数目.

2.计算方法

二项式系数都可以由递归公式和边界条件确定.

3.显公式

即上面证明的定理.

二项式系数里我们还有另一个方法：

4.二项式定理

(1+x)^n = C(n,0) + C(n,1)x + C(n,2)x^2 + C(n,3)x^3+...+C(n,n)x^n

我们还可以用别的方法引进帕斯卡三角形里的这些数,因为在很多有趣的问题里都起着重要的作用，并且具有很多有趣的性质。

雅各*贝努里 在他的《猜度术》里面写道“这张数据表具有一系列奇妙的性质,刚才我们看到了,组合论的本质就蕴含在它里面.比较熟悉几何的人都知道,它还隐藏着数学里一些重要的诀窍。”

当然时代不同了,很多贝努里时代还未发掘的事情,今天已经搞清楚了.不过对于希望作一些有趣而有意义的习题的读者来说,这仍然是一个很好的锻炼机会:它可以通过仔细观察帕斯卡三角形里面的数,并用这种或者那种或者同时用几种方法去研究它们,而发现许多东西,其中有些还可能是很有用的。