默慈金数

维基百科,自由的百科全书
跳到导航 跳到搜索

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

Motzkin Number

默慈金数也可以表示为



最初的几个默慈金数如下(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种方法”:

MotzkinChords4.svg

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

MotzkinChords5.svg

“默慈金质数”是同时为质数的默慈金数,直至2007年10月止,共有四个已知的“默慈金质数”,它们分别如下(OEIS中的数列A092832):

2, 127, 15511, 953467954114363

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

以下为例,下例显现了从(0,0)至(4,0)照上述的走法中,九种可行的路径:

Motzkin4.svg

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

参见[编辑]

参照[编辑]

外部链接[编辑]