转毒鼠强同学对一刀n断同学提出的问题：m维空间被m-1维刀片切n次得到有多少段[icky (5-7 18:29, Long long ago)] [ 传统版 | sForum ][登录后回复]1楼
我的解法[icky (5-7 18:29, Long long ago)] [ 传统版 | sForum ][登录后回复]2楼
(引用 icky:我的解法)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[icky (5-7 18:32, Long long ago)]
[ 传统版 |
sForum ][登录后回复]3楼
(引用 icky: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 [icky (5-7 18:34, Long long ago)] [ 传统版 | sForum ][登录后回复]4楼
m=2, n=4, answer is 11?[吴永铮 (5-7 21:32, Long long ago)] [ 传统版 | sForum ][登录后回复]5楼
(引用 吴永铮:m=2, n=4, answer is 11?)平面上划4条线，最多11个区域，对的吧[icky (5-7 21:39, Long long ago)] [ 传统版 | sForum ][登录后回复]6楼
(引用 icky:平面上划4条线，最多11个区域，对的吧)那f(n,m)=f(n-1,m)+f(n-1,m-1)就不对咯。f(4,2)=f(3,2)+1=...=4[吴永铮 (5-7 22:57, Long long ago)] [ 传统版 | sForum ][登录后回复]7楼
(引用 吴永铮:那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[icky (5-7 23:47, Long long ago)]
[ 传统版 |
sForum ][登录后回复]8楼
(引用 icky:f(4,2)=(f(3,2)+f(3,1)=7+4=11f(3,1) = 4 因为三个点可以把一条线分成4段 我的basis写错了，应该是f(*,0)=f(0,*)=1,即一个点不管怎么分�...)厉害[吴永铮 (5-8 13:38, Long long ago)] [ 传统版 | sForum ][登录后回复]9楼
(引用 吴永铮:厉害)我那个公式是用递推式得出来的，但是我还不知道怎么解释这个公式你看啊
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的边数有关
[icky (5-8 19:19, Long long ago)]
[ 传统版 |
sForum ][登录后回复]10楼
(引用 icky:我那个公式是用递推式得出来的，但是我还不知道怎么解释这个公式你看啊
f(n,m) = 2^n - \sum_{k=0}^{n-m-1}{n \choose k}
= \sum_{k=n-...)可以这么解释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)
得证。[大树下 (5-9 19:11, Long long ago)]
[ 传统版 |
sForum ][登录后回复]11楼
(引用 大树下:可以这么解释m维空间被切n次得到的段数 = m维空间被切n-1次得到的段数 + 第n刀增加的段数 假设m维空间被切n-1次得到的段数为A，即被分成...)恩，我是问怎么解释这个数刚好是杨辉三角前m+1项的和[icky (5-10 15:10, Long long ago)] [ 传统版 | sForum ][登录后回复]12楼
(引用 icky:恩，我是问怎么解释这个数刚好是杨辉三角前m+1项的和)...你认为这两个之间有hidden connection？
我觉得只是巧合。因为杨辉三角第n行前m项的和也符合这个式子S(n,m)=S(n-1,m)+S(n-1,m-1),根据杨辉三角的性质【杨辉三角第n行第m项Y(n,m)=Y(n-1,m)+Y(n-1,m-1)】很容易推导出来的。
[大树下 (5-12 12:02, Long long ago)]
[ 传统版 |
sForum ][登录后回复]13楼