成对连接圆周上2n个点使弦互不相交，有多少种不同的连接方法？

TSC999

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

2 个点有 1 种连接方法，s(1)=1；
4 个点有 2 种连接方法，s(2)=2；
6 个点有 5 种连接方法，s(3)=5；
……………………………………

可以找到递推公式：
定义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}
求通项公式。

TSC999

如果依据已知的递推公式来求通项公式，可能就会走入岐途？ 您也许可以另外开辟一条新路，直接找到通项公式。

mathe

递推式里面有卷积的形式，应该用母函数法可以求解

Lwins_G

Catalan数。

TSC999

高人！按名称搜了下，果然。
可以化简为1阶递推关系: 如\[s(n_{>0})=\frac{4n-2}{n+1}s(n-1), s(0)=1\]
该递推关系的解为:\[s(n)=\frac{C(2n,n)}{n+1}=\frac{(2n)!}{n!\cdot(n+1)!}, (n=1,2,3,...)\]

hujunhua

知道是Catalan数不难。Catalan数有很多组合模型，问题是如何在两个不同的模型间建立等价的联系，比如相同的递推公式，或者一一对应关系。
@TSC999，你那奇偶分述的递推公式，是由表的卷积合并对称项后的结果。合并后把表的卷积搞残缺了，蛇脚（表达式）也长出来了，掩盖了与Catalan数的联系。
我给你改还原了，立马就看出是Catalan 数，因为递推公式相同。
程序也改成了 MMA的函数式风格。

王守恩

如果将通过旋转、翻转得到的图形可重合的视为同一种连线方法，则前10项数据如下：
1，1，2，3，6，11，23，47，102，214，......
这个数列在OEIS上搜索不到。

王守恩

谢谢hujunhua先生！这句话对我启发很大：
Catalan数有很多组合模型，问题是如何在两个不同的模型间建立等价的联系，比如相同的递推公式，或者一一对应关系。

王守恩

一个有关的问题如下：

1，1个“+”号，有2个算式。
    1+1
    1+2
2，2个“+”号，有3个算式。
    1+1+1
    1+1+2
    1+2+3
3，3个“+”号，有5个算式。
    1+1+1+1
    1+1+1+2
    1+1+2+2
    1+1+2+3
    1+2+3+4
4，4个“+”号，有7个算式。
    1+1+1+1+1
    1+1+1+1+2
    1+1+1+2+2
    1+1+1+2+3
    1+1+2+2+3
    1+1+2+3+4
    1+2+3+4+5
    ............
我们对每个算式中各项加数约定如下：
1，第1个加数是“1”；
2，相邻加数，后项-前项=0或者1；
3，相同加数的个数：较大的不能比较小的多。

前27项如下：
2，3，5，7，11，15，22，30，42，56，77，101，135，176，231，297，385，490，627，792，1002，1255，1575，1958，2436，3010，3718

alt

http://mathworld.wolfram.com/PartitionFunctionP.html