medie2005 发表于 2008-5-12 14:48:30

一个计数问题

原题链接:http://topic.csdn.net/u/20080510/12/e30fe78d-9503-495f-a24f-c85644a8346f.html
把一个多边形分成三角形和四边形的个数是多少，具体有啥公式啊？当然那些分割线不能相交，比如对于
3
4
5
6
7
8
9
10
对应的方法为：
1
3
10
38
154
654
2871
12925

zgg___ 发表于 2008-5-12 16:38:55

http://www.research.att.com/~njas/sequences/A001002

medie2005 发表于 2008-5-12 16:57:56

呵呵,有点出乎意料.
我没有找出递归关系,所以怀疑公式的存在性.没想到zgg__找到了资料了.

mathe 发表于 2008-5-12 17:02:48

假设n边形划分数为f(n),而且为方便起见，记f(2)=1
考虑一个指定的边（图最左边的边），这条边为一个三角形的边的情况如图:

这条边属于一个四边形的情况有如下几种


(其中上面这个图还有一个对称情况）


于是我们可以得到递推公式
$f(n)=sum_{i=2}^{n-1}f(i)f(n+1-i) + 2sum_{i=3}^{n-3}f(i)f(n-i)+sum_{i=2}^{n-2}f(i)f(n-i)+sum_{ {: (i+j+k=n+2),(i>=3),(j>=3),(k>=3) :} } f(i)f(j)f(k)$

medie2005 发表于 2008-5-12 17:45:26

呵呵,mathe原来一直在潜水啊.
明白了.这个递归式好象不好求.

medie2005 发表于 2008-5-12 17:47:08

我的意思是递归式不好解.:loveliness:

无心人 发表于 2008-5-12 18:30:39

觉得就是稍微复杂点
应该好解

无心人 发表于 2008-5-12 18:32:24

:)

用函数式语言描述这个公式应该容易些

medie2005 发表于 2008-5-12 18:49:35

哦,无心人说说解法啊.

无心人 发表于 2008-5-12 19:54:56

:)
我在学呢
还没学好呢
什么时候学会写了
我会写在我专门学习的haskell帖子里
页: [1] 2 3 4
查看完整版本: 一个计数问题