我的解法

f(n,m)=f(n-1,m)+f(n-1,m-1)with f(1,*)=1 and f(*,1)=1 化简之后可得 f(n,m) = 2^n - \sum_{k=0}^{n-m-1}{(n+1) \choose k} 不知有否close form

m=2, n=4, answer is 11?

平面上划4条线，最多11个区域，对的吧

那f(n,m)=f(n-1,m)+f(n-1,m-1)就不对咯。f(4,2)=f(3,2)+1=...=4

f(4,2)=(f(3,2)+f(3,1)=7+4=11f(3,1) = 4 因为三个点可以把一条线分成4段 我的basis写错了，应该是f(*,0)=f(0,*)=1,即一个点不管怎么分都还是一个点，任何一个空间不切割的情况下是一个partition

厉害

我那个公式是用递推式得出来的，但是我还不知道怎么解释这个公式你看啊 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+1项的和