圆周20个点连线问题
圆周上分布20个相异的点。用10条互不相交且无公共端点的线段连接这些点，有多少种不同的连法？ https://bbs.emath.ac.cn/thread-9507-1-1.html 递推关系。9724+2860+1716+1320+1176=16,796; 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，证明略，反正代码在这里：a={0:1,2:1}
def f(x):
if a.get(x):return(a.get(x))
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: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×.....
还可以化简吗？
本帖最后由 dlpg070 于 2019-10-24 16:37 编辑
回复6#：
有关的通项公式有很多，你的公式有点特别，正确无误
a:= \(\prod _{i=0}^{i=n} \frac{4 i+2}{i+2}\);
Table,{n,0,20}]
可以化简为
as:= \(\frac{4^{n+1} \Gamma \left(n+\frac{3}{2}\right)}{\sqrt{\pi } \Gamma (n+3)}\);
Table,{n,0,20}]
计算速度快一些
以n=100为例 快5倍
a:0.0108秒{0.010793854222191432`,Null}
as: 0.0021秒 {0.0020702519389168236`,Null}
本帖最后由 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
页:
[1]