数学研发论坛

 找回密码
 欢迎注册
查看: 281|回复: 10

[讨论] 圆周20个点连线问题

[复制链接]
发表于 2019-10-22 13:11:31 | 显示全部楼层 |阅读模式

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

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

x
圆周上分布20个相异的点。用10条互不相交且无公共端点的线段连接这些点,有多少种不同的连法?
圆周上分布20个点.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-10-22 14:06:53 | 显示全部楼层
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-10-22 14:31:39 | 显示全部楼层
递推关系。
黑色数学114关.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

 楼主| 发表于 2019-10-22 14:41:36 | 显示全部楼层
9724+2860+1716+1320+1176=16,796;
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-10-22 14:50:54 | 显示全部楼层
f(0)=f(2)=1
f(2k+1)=0
f(2k)=sum_i(f(i)*f(2k-i-2))
忘记怎么算通项了
f(4)=2
f(6)=f(0)f(4)+f(2)f(2)+f(4)f(0)=5
f(8)=f(0)f(6)+f(2)f(4)+f(4)f(2)+f(6)f(0)=14
f(10)=f(0)f(8)+f(2)f(6)+f(4)f(4)+f(6)f(2)+f(8)f(0)=42
事实上,这就是Catalan numbers,证明略,反正代码在这里:
  1. a={0:1,2:1}
  2. def f(x):
  3.   if a.get(x):return(a.get(x))
  4.   return(a.setdefault(x,sum(f(i)*f(x-2-i) for i in range(0,x,2))))
复制代码

>>> f(20)
16796
就完事了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-10-24 00:42:36 | 显示全部楼层
本帖最后由 王守恩 于 2019-10-24 00:47 编辑

1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012,
742900, 2674440, 9694845, 35357670, 129644790, 477638700,
1767263190, 6564120420, 24466267020, 91482563640, ............
a(n)=2/2×6/3×10/4×14/5×18/6×22/7×26/8×30/9×.....
还可以化简吗?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-10-24 14:01:42 | 显示全部楼层
本帖最后由 dlpg070 于 2019-10-24 16:37 编辑

回复6#:
有关的通项公式有很多,你的公式有点特别,正确无误
a[n_]:= \(\prod _{i=0}^{i=n} \frac{4 i+2}{i+2}\);
Table[a[n],{n,0,20}]

可以化简为
as[n_]:= \(\frac{4^{n+1} \Gamma \left(n+\frac{3}{2}\right)}{\sqrt{\pi } \Gamma (n+3)}\);
Table[as[n],{n,0,20}]
计算速度快一些

以n=100为例 快5倍
a[0---100]:  0.0108秒  {0.010793854222191432`,Null}  
as[0---100]: 0.0021秒 {0.0020702519389168236`,Null}




毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 前天 21:39 | 显示全部楼层
本帖最后由 dlpg070 于 2019-11-18 21:43 编辑
.·.·. 发表于 2019-10-22 14:50
f(0)=f(2)=1
f(2k+1)=0
f(2k)=sum_i(f(i)*f(2k-i-2))


本题的正确答案似乎不是 16796  而是    852
不是 Catalan Number 而是 a002995
下面是计算结果的小结
grid不相交弦.png

说明:
此题是平面上园,圆周上的点是unlabeled,应去掉中心旋转对称解,
没有翻转对称解
如果是类似剪纸,炉箅子之类,则需要去掉翻转对称解
表格中:
labeled   我计算的结果(假设圆周上的点是labeled),已画图验证
unlabeled 我计算的结果(此题圆周上的点是unlabeled)已画图验证
Catalan   圆周上的点是labeled条件下,理论解个数,Catalan number
          我计算结果labeled与Catalan 一致
a002995   圆周上的点是unlabeled条件下,理论解个数(圆桌客人握手)
          我计算结果unlabeled与a002995 一致
我在计算和画图到n=16以后发现解符合 a002995,没必要再验证下去
得 n=20 此题应解 852

计算结果

计算结果

点评

的确,在点不等间隔分布条件下,答案:Catalan数,在点等间隔分布条件下,答案:A002995  发表于 昨天 22:07
其实题目中没说20个点等间隔分布的……果然是前辈嫌题目太简单吗?  发表于 昨天 17:44
可怕……明明没说那20个点间隔相同……前辈硬生生把题目难度拔高一个档次……还做出来了  发表于 昨天 17:43
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-11-20 16:58 , Processed in 0.068910 second(s), 20 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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