转毒鼠强同学对一刀n断同学提出的问题:m维空间被m-1维刀片切n次得到有多少段
登录 | 论坛导航 -> 华新鲜事 -> 求学狮城 | 本帖共有 8 楼,分 1 页, 当前显示第 1 页 : 本帖树形列表 : 刷新 : 返回上一页
<<始页  [1]  末页>>
作者:icky (等级:15 - 最接近神,发帖:7923) 发表:2008-05-07 18:29:51  楼主  关注此帖评分:
转毒鼠强同学对一刀n断同学提出的问题:m维空间被m-1维刀片切n次得到有多少段
This page is intentionally left blank
欢迎来到华新中文网,踊跃发帖是支持我们的最好方法!原文 / 传统版 / WAP版所有回复从这里展开收起列表
作者:icky (等级:15 - 最接近神,发帖:7923) 发表:2008-05-07 18:29:58  2楼
转毒鼠强同学对一刀n断同学提出的问题:m维空间被m-1维刀片切n次得到有多少段
我的解法
欢迎来到华新中文网,踊跃发帖是支持我们的最好方法!原文 / 传统版 / WAP版所有回复从这里展开收起列表
作者:icky (等级:15 - 最接近神,发帖:7923) 发表:2008-05-07 18:32:52  3楼 评分:
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
欢迎来到华新中文网,踊跃发帖是支持我们的最好方法!原文 / 传统版 / WAP版所有回复从这里展开收起列表
作者:icky (等级:15 - 最接近神,发帖:7923) 发表:2008-05-07 18:34:38  4楼
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
-->
不知有否close form
欢迎来到华新中文网,踊跃发帖是支持我们的最好方法!原文 / 传统版 / WAP版所有回复从这里展开收起列表
作者:icky (等级:15 - 最接近神,发帖:7923) 发表:2008-05-07 21:39:48  5楼
平面上划4条线,最多11个区域,对的吧
欢迎来到华新中文网,踊跃发帖是支持我们的最好方法!原文 / 传统版 / WAP版所有回复从这里展开收起列表
作者:icky (等级:15 - 最接近神,发帖:7923) 发表:2008-05-07 23:47:10  6楼 评分:
那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=11
f(3,1) = 4 因为三个点可以把一条线分成4段

我的basis写错了,应该是f(*,0)=f(0,*)=1,即一个点不管怎么分都还是一个点,任何一个空间不切割的情况下是一个partition
欢迎来到华新中文网,踊跃发帖是支持我们的最好方法!原文 / 传统版 / WAP版所有回复从这里展开收起列表
作者:icky (等级:15 - 最接近神,发帖:7923) 发表:2008-05-08 19:19:49  7楼 评分:
我那个公式是用递推式得出来的,但是我还不知道怎么解释这个公式
你看啊

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的边数有关
欢迎来到华新中文网,踊跃发帖是支持我们的最好方法!原文 / 传统版 / WAP版所有回复从这里展开收起列表
作者:icky (等级:15 - 最接近神,发帖:7923) 发表:2008-05-10 15:10:51  8楼
可以这么解释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项的和
欢迎来到华新中文网,踊跃发帖是支持我们的最好方法!原文 / 传统版 / WAP版所有回复从这里展开收起列表
论坛导航 -> 华新鲜事 -> 求学狮城 | 返回上一页 | 本主题共有 8 篇文章,分 1 页, 当前显示第 1 页 | 回到顶部
<<始页  [1]  末页>>

请登录后回复:帐号   密码