路徑與素數

迪蘭尼素數

迪蘭尼數 (Delannoy Number) D(a,b) 是指由 (0,0) 至 (a,b),只可向上、右或右上方向走的可行路徑數。

如 D(2,2) = 16

其實我們有一遞推公式 (Recurrence Equation) 求出迪蘭尼數:

D(a,b) = D(a-1,b) + D(a, b-1) + D(a-1,b-1) 其中 D(0,0) = 1

求出迪蘭尼數亦是初中、高小數學競賽中常見的問題。

若取 a = b = n 的話,我們稱作中心迪蘭尼數 (Central Delannoy Number) 的一數列: 3, 13, 63, 321, 1683, 8989, 48639, ...... (OEIS A001850)

其中的素數,即中心迪蘭尼素數 (Central Delannoy Prime) 或迪蘭尼素數 (Delannoy Prime),首 11000 個迪蘭尼數中就僅有 3, 13, 265729 三個素數 (OEIS A902830) 。

 

莫斯堅素數

莫斯堅數 (Motzkin Number) 的定義和迪蘭尼數相若,不過這次是考慮由 (0,0) 至 (n,0) 的可行路徑數,但只可向右上、右下或正右方向走,這簡記為 M(n) 或 Mn

如 M0 = 1, M1 = 1, M2 = 2, ....

我們可以用一遞推公式求出莫斯堅數:

Mn = (n+2)-1 * [3(n-1)Mn-2 + (2n+1)Mn-1]

其中 M0 = 1, M1 = 1。

其中的素數,即莫斯堅素數 (Motzkin Prime) ,首 263000 個莫斯堅數中就僅有 2, 127, 15511, 953467954114363 四個素數 (OEIS A902832) 。

 

參考文獻及網址

Weisstein, E. W. "Delannoy Number." From MathWorld. http://mathworld.wolfram.com/DelannoyNumber.html.

Weisstein, E. W. "Motzkin Number." From MathWorld. http://mathworld.wolfram.com/MotzkinNumber.html.