圆周20个点连线问题

markfang2050

圆周上分布20个相异的点。用10条互不相交且无公共端点的线段连接这些点，有多少种不同的连法？

mathe

https://bbs.emath.ac.cn/thread-9507-1-1.html

markfang2050

递推关系。

markfang2050

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，证明略，反正代码在这里：

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
就完事了

王守恩

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

回复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}

dlpg070

.·.·. 发表于 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