默慈金数

在数学中，一个给定的数n的默慈金数是“在一个圆上的n个点间，画出彼此不相交的弦的全部方法的总数”。默慈金数在几何、组合数学和数论等领域中皆有其用途。它以递归的方法给出的定义如下：

Motzkin Number

$M_{n+1}=M_{n}+\sum _{i=0}^{n-1}M_{i}M_{n-1-i}={\frac {2n+3}{n+3}}M_{n}+{\frac {3n}{n+3}}M_{n-1}$

默慈金数也可以表示为

$M_{n}=\sum _{k=0}^{\lfloor n/2\rfloor }{\binom {n}{2k}}C_{k}.$

$M_{n}=\sum _{k=0}^{\infty }{\frac {(-1)^{k}}{n+2-k}}*{\binom {n}{k}}*{\binom {2n+2-2k}{n+1-k}}$

最初的几个默慈金数如下（OEIS数列A001006）：

1, 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, 15511, 41835, 113634, 310572, 853467, 2356779, 6536382, 18199284, 50852019, 142547559, 400763223, 1129760415, 3192727797, 9043402501, 25669818476, 73007772802, 208023278209, 593742784829

下图显示了“在一个圆上的4个点间，画出彼此不相交的弦的所有9种方法”：

下图显示了“在一个圆上的5个点间，画出彼此不相交的弦的所有21种方法”：

“默慈金质数”是同时为质数的默慈金数，直至2007年10月止，共有四个已知的“默慈金质数”，它们分别如下（OEIS数列A092832）：

2, 127, 15511, 953467954114363

默慈金数亦出现在别的地方，像例如在一个“网格”上，若限定“每步只能向右移动一格（可以向右上、右下横向向右），并禁止移动到y=0以下的地方”，则以这种走法用n步从（0,0）移动至（n,0）的可能形成的路径的总数为n的默慈金数。

以下为例，下例显现了从（0,0）至（4,0）照上述的走法中，九种可行的路径：

根据Donaghey & Shapiro (1977)对默慈金数的调查，在数学的各分支中，默慈金数至少有十四个彼此不同的展现存在；Guibert, Pergola & Pinzani (2001)指出旗手轮换（Vexillary permutation）和默慈金数相关。

参见

• 迪兰尼数（Delannoy number）
• 那罗延数（Narayana number）
• 施罗德数（Schröder number）

参照

• Donaghey, R.; Shapiro, L. W., Motzkin numbers, Journal of Combinatorial Theory, Series A, 1977, 23 (3): 291–301, MR 0505544, doi:10.1016/0097-3165(77)90020-6 
• Guibert, O.; Pergola, E.; Pinzani, R., Vexillary involutions are enumerated by Motzkin numbers, Annals of Combinatorics, 2001, 5 (2): 153–174, ISSN 0218-0006, MR 1904383, doi:10.1007/PL00001297 
• Motzkin, T. S., Relations between hypersurface cross ratios, and a combinatorial formula for partitions of a polygon, for permanent preponderance, and for non-associative products, Bulletin of the American Mathematical Society, 1948, 54 (4): 352–360, doi:10.1090/S0002-9904-1948-09002-4 

外部链接

• 埃里克·韦斯坦因. Motzkin Number. MathWorld.