RT
解答:
若在r维空间中,n个r-1维超平面最多可以把空间切割成W(n,r)部分,则W(n,r)= C(n,0)+C(n,1)+C(n,2)+…+C(n,r)。
(其中,C(n,i) =n!/(i!(n-i)!)表示n个数中取i个数组合的个数(i=0,1,2,…,r),当n<r时,C(n,i)=0)证明如下:
设r维空间的n-1个r-1维超平面可把空间分割的部分最多为W(n-1,r),再加入一个r-1维超平面,要保证使这n个r-1维超平面把空间分割的部分最多,就必须使已有的n-1个超平面和这超平面相交的n-1条r-2维超直线把后加入的这个r-1维超平面分割的部分最多,因此得到
W(n,r)-W(n-1,r)=W(n-1,r-1) (1)
对r用数学归纳法证明:
W(n,r)=C(n,0)+C(n,1)+C(n,2)+…+C(n,r)。
当r=1时,即n个点最多可以把直线分为n+1部分,而n+1=C(n,0)+C(n,1),即r=1时结论成立。
假设r=k-1时结论成立,即k-1维超平面M上的i(i=n-1,…,1)条k-2维超直线可把M分割为:
W(n-1,k-1)=C(n-1,0)+C(n-1,1)+C(n-1,2)+…+C(n-1,k-1)
W(n-2,k-1)=C(n-2,0)+C(n-2,1)+C(n-2,2)+…+C(n-2,k-1) …… …… …… …… …… …… ……
W(k-1,k-1)=C(k-1,0)+C(k-1,1)+C(k-1,2)+…+C(k-1,k-1)
W(k-2,k-1)=C(k-1,0)+C(k-1,1)+C(k-1,2)+…+C(k-2,k-2) …… …… …… …… …… …… ……
W(2,k-1)=C(2,0)+C(2,1)+C(2,2)
W(1,k-1)=C(1,0)+C(1,1)
而由(1)可得
W(n,k)-W(n-1,k)=W(n-1,k-1)
W(n-1,k)-W(n-2,k)= W (n-2,k-1)
…… …… …… …… …… …… ……
W(2,k)-W(1,k)=W(1,k-1)
将上面n-1个等式两端相加得
W(n,k)-W(1,k)=W(1,k-1)+W(2,k-1)+…+W(n-1,k-1)因为一个k-1维超平面只能把经过它的k维超平面切为两部分,
因此W(1,k)=2=1+C(1,1),从而有
W(n,k)=C(n,0)+[C(1,1)+C(1,0)+C(2,0)+…+C(n-1,0)]
+[C(1,1)+C(2,1)+C(3,1)+…+C(n-1,1)]
+[C(2,2)+C(3,2)+…+C(n-1,2)]
…… …… …… …… ……
+[C(k-1,k-1)+C(k,k-1)+…+C(n-1,k-1)] (2)
由杨辉三角恒等式C(m,n)+C(m,n+1)=C(m+1,n+1)有
C(1,1)+C(1,0)+C(2,0)+…+C(n-1,0)
=[C(1,1)+C(1,0)]+C(2,0)+…+C(n-1,0)
=[C(2,1)+C(2,0)]+…+C(n-1,0)
…… …… …… …… ……
=C(n-1,1) +C(n-1,0)=C(n,1)同理可得:
C(1,1)+C(2,1)+C(3,1)+…+C(n-1,1)=C(n,2)
C(2,2)+C(3,2)+…+C(n-1,2)=C(n,3)
…… …… …… …… ……
C(k-1,k-1)+C(k,k-1)+…+C(n-1,k-1)=C(n,k)代入(2)得
W(n,k)=1+C(n,1)+C(n,2)+C(n,3)+…+C(n,k)
W(n,k)=C(n,0)+C(n,1)+C(n,2)+C(n,3)+…+C(n,k)
由数学归纳法原理知,对任意的r维空间,n个r-1维超平面最多可以把空间切割成W(n,r)部分,
则W(n,r)=C(n,0)+C(n,1)+C(n,2)+…+C(n,r)。