默慈金數

在數學中，一個給定的數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.