主題
Search

德蘭諾數

DOWNLOAD Mathematica Notebook下載 Wolfram 筆記本

德蘭諾數 D(a,b) 是從 (0,0) 到 (b,a) 的格路數量，其中只允許向東 (1, 0), 向北 (0, 1), 和東北 (1, 1) 步 (即 ->, ^, 和 ->)。它們由以下遞推關係給出

D(a,b)=D(a-1,b)+D(a,b-1)+D(a-1,b-1),
(1)

其中 D(0,0)=1。它們也由以下求和公式給出

D(n,k)=sum_(d=0)^(n)(k; d)(n+k-d; k)
(2)
=sum_(d=0)^(n)2^d(k; d)(n; d)
(3)
=(n+k; k)_2F_1(-n,-k;-(k+n);-1),
(4)

其中 _2F_1(a,b;c;z) 是一個超幾何函式。

德蘭諾數的數值表如下所示

1 1 1 1 1 1 1 1 1 ...; 1 3 5 7 9 11 13 15 17 ...; 1 5 13 25 41 61 85 113 145 ...; 1 7 25 63 129 231 377 575 833 ...; 1 9 41 129 321 681 1289 2241 3649 ...; 1 11 61 231 681 1683 3653 7183 13073 ...
(5)

(OEIS A008288) 對於 m=0, 1, ... 從左到右遞增，以及 n=0, 1, ... 從上到下遞增。

它們具有生成函式

sum_(p,q=1)^inftyD(p,q)x^py^q=(1-x-y-xy)^(-1)
(6)

(Comtet 1974, p. 81)。

DelannoyNumber

取 n=a=b 得到中心德蘭諾數 D(n,n)，它是從 (0,0) 角到 n×n 正方形的右上角 (n,n) 的 “國王步數”。 這些由以下公式給出

D(n,n)=P_n(3),
(7)

其中 P_n(x) 是一個勒讓德多項式 (Moser 1955; Comtet 1974, p. 81; Vardi 1991)。 另一個表示式是

D(n)=D(n,n)
(8)
=sum_(k=0)^(n)(n; k)(n+k; k)
(9)
=_2F_1(-n,n+1;1,-1),
(10)

其中 (a; b) 是一個二項式係數，而 _2F_1(a,b;c;z) 是一個超幾何函式。 這些數字與康託集 (Cantor set) 有著驚人的聯絡 (E. W. Weisstein, Apr. 9, 2006)。

它們也滿足遞推方程

D(n)=(3(2n-1)D(n-1)-(n-1)D(n-2))/n.
(11)

它們具有生成函式

G(x)=1/(sqrt(1-6x+x^2))
(12)
=1+3x+13x^2+63x^3+321x^4+....
(13)

D(n) 的值 D(n) 對於 n=1, 2, ... 是 3, 13, 63, 321, 1683, 8989, 48639, ... (OEIS A001850)。 D(10^n,10^n) 的十進位制位數 D(10^n,10^n) 對於 n=0, 1, ... 是 1, 7, 76, 764, 7654, 76553, 765549, 7655510, ... (OEIS A114470)，其中位數接近 log_(10)(3+2sqrt(2))=0.765551... 的位數 (OEIS A114491)。

最開始的幾個素數德蘭諾數是 3, 13, 265729, ... (OEIS A092830)，對應於索引 1, 2, 8, ...，對於 n<1.1×10^5 沒有其他素數 (Weisstein, Mar. 8, 2004)。

施羅德數 (Schröder numbers) 與德蘭諾數的關係，正如卡塔蘭數 (Catalan numbers) 與二項式係數的關係。

令人驚訝的是，對 D(a,b) 的方陣進行喬列斯基分解 (Cholesky decomposition)，轉置，並將其乘以對角矩陣 diag(2^(-0/2),2^(-1/2),2^(-2/2),...)，得到帕斯卡三角形 (Pascal's triangle) 的方陣（即下三角矩陣）版本 (G. Helms, 私人通訊, Aug. 29, 2005)。

DelannoyNumberArrays

透過繪製 D(a,b) (mod m) 可以獲得美麗的fractal (分形) 圖案 (E. Pegg, Jr., 私人通訊, Aug. 29, 2005)。 特別是，m=3 的情況對應於類似於謝爾賓斯基地毯 (Sierpiński carpet) 的圖案。

另請參閱

二項式係數, 康託函式, 卡塔蘭數, 整數序列素數, 莫茨金數, 施密特問題, 施羅德數

使用 探索

參考文獻

Banderier, C. and Schwer, S. "為什麼是德蘭諾數？" 即將發表於 J. Stat. Planning Inference. http://www-lipn.univ-paris13.fr/~banderier/Papers/delannoy2004.ps.Comtet, L. 高階組合數學：有限與無限展開的藝術，修訂擴充套件版。 Dordrecht, Netherlands: Reidel, pp. 80-81, 1974.Dickau, R. M. "德蘭諾數和莫茨金數。" http://www.prairienet.org/~pops/delannoy.html.Goodman, E. and Narayana, T. V. "帶有對角步的格路。" Canad. Math. Bull. 12, 847-855, 1969.Moser, L. "棋盤上的國王路徑。" Math. Gaz. 39, 54, 1955.Moser, L. and Zayachkowski, H. S. "帶有對角步的格路。" Scripta Math. 26, 223-229, 1963.Sloane, N. J. A. “整數序列線上百科全書”中的序列 A001850/M2942, A008288 , A092830, A114470, 和 A114491."Stocks, D. R. Jr. "E^3 中帶有對角步的格路。" Canad. Math. Bull. 10, 653-658, 1967.Vardi, I. Mathematica 中的計算娛樂。 Reading, MA: Addison-Wesley, 1991.

在 中被引用

德蘭諾數

引用為

Weisstein, Eric W. "德蘭諾數。" 來自 Web 資源。 https://mathworld.tw/DelannoyNumber.html

主題分類