默慈金數
在數學中,一個給定的數n的默慈金數是「在一個圓上的n個點間,畫出彼此不相交的弦的全部方法的總數」。默慈金數在幾何、组合数学和数论等領域中皆有其用途。它以遞歸的方法給出的定義如下:
![](http://178.128.105.246/cars-http-upload.wikimedia.org/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