我那个公式是用递推式得出来的,但是我还不知道怎么解释这个公式你看啊
f(n,m) = 2^n - \sum_{k=0}^{n-m-1}{n \choose k}
= \sum_{k=n-m}^{n}{n \choose k}
= \sum_{k=0}^{m}{n \choose k}
就是说这个值是杨辉三角的第n行(尖尖为第0行)前m+1项的和
n=0 1
n=1 1 1
n=2 1 2 1
n=3 1 3 3 1
n=4 1 4 6 4 1
比方说m=2的情况,我们只需把每一行的前3项相加,就是f(n,2)了
我还在想这个怎么解释,不过我初步的想法应该跟每个partition的边数有关
可以这么解释
m维空间被切n次得到的段数 = m维空间被切n-1次得到的段数 + 第n刀增加的段数
假设m维空间被切n-1次得到的段数为A,即被分成了A个m维空间。假设第n个刀片被起先的n-1刀分成k段,有k个m-1维小刀片,每个小刀片完全被包容于与A个空间中的其中一个空间,而且把它分成两半,所以总共增加了k段。
所以 f(n, m) = A + k.
很显然 A = f(n-1, m)
k = 第n个刀片(m-1维)被切n-1刀得到的段数 = f(n-1, m-1)
得证。
假设m维空间被切n-1次得到的段数为A,即被分成了A个m维空间。假设第n个刀片被起先的n-1刀分成k段,有k个m-1维小刀片,每个小刀片完全被包容于与A个空间中的其中一个空间,而且把它分成两半,所以总共增加了k段。
所以 f(n, m) = A + k.
很显然 A = f(n-1, m)
k = 第n个刀片(m-1维)被切n-1刀得到的段数 = f(n-1, m-1)
得证。