数学研发网设为首页收藏本站

数学研发论坛

 找回密码
 欢迎注册
查看: 560|回复: 19

[提问] 成对连接圆周上2n个点使弦互不相交,有多少种不同的连接方法?

[复制链接]
发表于 2017-5-13 19:18:02 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
圆周上共有 2n 个均布点,成对连接而使所得 n 条弦两两互不相交,有多少种不同的连接方法?

2 个点有 1 种连接方法,s(1)=1;
4 个点有 2 种连接方法,s(2)=2;
6 个点有 5 种连接方法,s(3)=5;
……………………………………
弦的连接方法.png
可以找到递推公式:
定义s(0)=1,  \[\ s(n+1)=\sum_{k=0}^n s(n-k)  s(k) \]但是本题要的不是递推公式,而是通项公式。
用递推公式编写的计算程序如下:
  1. Nest[#~Join~ListConvolve[#,#]&, {1}, 10]
复制代码
计算结果如下:
{1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796}
求通项公式。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2017-5-13 19:46:32 | 显示全部楼层
如果依据已知的递推公式来求通项公式,可能就会走入岐途? 您也许可以另外开辟一条新路,直接找到通项公式。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-5-14 14:47:23 | 显示全部楼层
递推式里面有卷积的形式,应该用母函数法可以求解

点评

噢,是这样啊,领教了。  发表于 2017-5-15 11:10
那个求和式,一个下标递增,一个递减,这个就是卷积  发表于 2017-5-15 08:27
有卷积吗?可能原公式中有个地方用 * 表示乘号了,版主已经改了,去掉了 * 号,以免误解。  发表于 2017-5-15 07:50
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-5-15 03:01:13 | 显示全部楼层
Catalan数。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

 楼主| 发表于 2017-5-15 07:55:37 | 显示全部楼层

高人!网上搜了下,果然就是 Catalan数。
可以化简为1阶递推关系: 如h(n)=(4n-2)/(n+1)*h(n-1)(n>1) h(0)=1
该递推关系的解为:h(n)=C(2n,n)/(n+1)=P(2n,n)/(n+1)!=(2n)!/(n!*(n+1)!) (n=1,2,3,...)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-5-15 10:20:17 | 显示全部楼层
知道是Catalan数不难。Catalan数有很多组合模型,问题是如何在两个不同的模型间建立等价的联系,比如相同的递推公式,或者一一对应关系。


@TSC999,你那奇偶分述的递推公式,是由表的卷积合并同类项后的结果。合并后把表的卷积搞残缺了,蛇(表达式)脚也长出来了,掩盖了与Catalan数的联系。

我给你改还原了,立马就看出是Catalan 数,因为递推公式相同。

程序也改成了 MMA的函数式风格。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-5-19 17:35:02 | 显示全部楼层
成对连接圆周上2n个点使弦互不相交,有多少种不同的连接方法?
答案是1,  2,  5,  14,  42, 132,  429,  1430,  4862,  16796, ......

通过旋转,翻转得到的图形重合时只能算同一种连线方法。
答案是1,1,2,3,6,11,23,47,102,214,......
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-5-23 19:11:48 | 显示全部楼层
@Wayne, @chyanog

  可否取得NestList 函数的前一步结果,使楼主的代码
  1. Nest[#~Join~ListConvolve[#,#]&, {1}, 10]
复制代码
更加简洁:
  1. NestList[list[#].Reserve@list[#]&, 1, 10]
复制代码

这里list[#]就是我所说的隐藏在NestList内部的前一步结果

点评

赞! 同意 chyanog,已经很简洁了  发表于 2017-6-6 10:43
我觉得这个用Nest已经是很简洁的了,非要用NestList应该也可以但论简洁可能会比不上Nest  发表于 2017-5-26 10:28
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-5-25 20:44:26 | 显示全部楼层
hujunhua 发表于 2017-5-23 19:11
@Wayne, @chyanog

  可否取得NestList 函数的前一步结果,使楼主的代码更加简洁:


谢谢hujunhua先生!这句话对我启发很大:
Catalan数有很多组合模型,问题是如何在两个不同的模型间建立等价的联系,比如相同的递推公式,或者一一对应关系。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-5-30 17:51:31 | 显示全部楼层
王守恩 发表于 2017-5-25 20:44
谢谢hujunhua先生!这句话对我启发很大:
Catalan数有很多组合模型,问题是如何在两个不同的模型间建 ...

此题比《珠环》还难,“带有重复元素的圆排列和环排列“的波利亚公式不够用。
此题比《汉诺塔》还难,杨辉三角与多进制也不够用。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|Archiver|数学研发网 ( 苏ICP备07505100号  

GMT+8, 2017-9-23 09:52 , Processed in 0.305115 second(s), 29 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表