默慈金數

维基百科,自由的百科全书
跳转至: 导航搜索

數學中,一個給定的數n的默慈金數是「在一個圓上的n個點間,畫出彼此不相交的的全部方法的總數」。默慈金數在幾何、组合数学数论等領域中皆有其用途。它以遞歸的方法給出的定義如下:

M_{n+1}=M_n+\sum_{i=0}^{n-1}M_iM_{n-1-i}=\frac{2n+3}{n+3}M_n+\frac{3n}{n+3}M_{n-1}

最初的幾個默慈金數如下(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)和默慈金數相關。

參見[编辑]

參照[编辑]

外部連結[编辑]