主题
Search

德兰诺数


德兰诺数 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) 的图案。


另请参阅

二项式系数, 康托函数, 卡塔兰数, 整数序列素数, 莫茨金数, 施密特问题, 施罗德数

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 中被引用

德兰诺数

引用为

Weisstein, Eric W. "德兰诺数。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/DelannoyNumber.html

主题分类