デラノワ数

Number of paths between grid corners, allowing diagonal steps

デラノワ数

名前の由来	アンリ・オーギュスト・ドラノワ
既知の用語の数	無限
式	${\displaystyle D(m,n)=\sum _{k=0}^{\min(m,n)}{\binom {m}{k}}{\binom {n}{k}}2^{k}}$
OEIS指数	A008288 デラノワの正方形配列

数学において、デラノワ数は 、長方形の格子の南西隅 (0, 0) から北東隅 ( m , n ) までの経路を、北、北東、または東への単一のステップのみで数える数です。デラノワ数は、フランス軍将校でありアマチュア数学者でもあったアンリ・デラノワにちなんで名付けられました。^[1] ${\displaystyle D}$

デラノワ数は、長さが と の2つのシーケンスの大域的な配列も数える。[ ^2] m次元整数格子または交差多面体における原点から最大でnステップの距離にある点^[3]および、セルオートマトンにおける半径nのm次元フォンノイマン近傍内のセル^[4]も数える。 ${\displaystyle D(m,n)}$ ${\displaystyle m}$ ${\displaystyle n}$

例

デラノワ数D (3, 3)は63です。次の図は、(0, 0)から(3, 3)までの63個のデラノワパスを示しています。

SW-NE対角線より上に上がらないパスのサブセットは、関連する数のファミリーであるシュレーダー数によってカウントされます。

デラノワ配列

デラノイ配列はデラノイ数の無限行列である: ^[5]

メートル n	0	1	2	3	4	5	6	7	8
0	1	1	1	1	1	1	1	1	1
1	1	3	5	7	9	11	13	15	17
2	1	5	13	25	41	61	85	113	145
3	1	7	25	63	129	231	377	575	833
4	1	9	41	129	321	681	1289	2241	3649
5	1	11	61	231	681	1683	3653	7183	13073
6	1	13	85	377	1289	3653	8989	19825	40081
7	1	15	113	575	2241	7183	19825	48639	108545
8	1	17	145	833	3649	13073	40081	108545	265729
9	1	19	181	1159	5641	22363	75517	224143	598417

この配列では、1行目の数はすべて1、2行目の数は奇数、 3行目の数は中心平方数、4行目の数は中心八面体数です。あるいは、同じ数をパスカルの三角形（トリボナッチ三角形とも呼ばれます）に似た三角形に並べることもできます。^[6]この場合、各数はその上にある3つの数の和になります。

 1 1 1 1 3 1 1 5 5 1 1 7 13 7 1 1 9 25 25 9 11 11 41 63 41 11 1

三角形の行の和はペル数1、2、5、12、29、70、169、…となり、対角線の和はトリボナッチ数1、1、2、4、7、13、24、… となる^{[7] 。}

中央デラノワ番号

中心デラノワ数 D ( n ) = D ( n , n ) は、 n × nの正方格子における数である。最初のいくつかの中心デラノワ数（n = 0 から始まる）は以下の通りである。

1、3、13、63、321、1683、8989、48639、265729、...（OEISのシーケンスA001850）。

計算

デラノワ数

対角線（つまり北東）方向のステップでは、点に到達するためには方向のステップと方向のステップが必要です。これらのステップは任意の順序で実行できるため、そのような経路の数は多項式係数によって与えられます。したがって、閉じた形式の式は次のようになります。 ${\displaystyle k}$ ${\displaystyle m-k}$ ${\displaystyle x}$ ${\displaystyle n-k}$ ${\displaystyle y}$ ${\displaystyle (m,n)}$ ${\displaystyle {\binom {m+n-k}{k,m-k,n-k}}={\binom {m+n-k}{m}}{\binom {m}{k}}}$

${\displaystyle D(m,n)=\sum _{k=0}^{\min(m,n)}{\binom {m+n-k}{m}}{\binom {m}{k}}.}$

別の表現は次のようになる。

${\displaystyle D(m,n)=\sum _{k=0}^{\min(m,n)}{\binom {m}{k}}{\binom {n}{k}}2^{k}}$

あるいは無限級数によって

${\displaystyle D(m,n)=\sum _{k=0}^{\infty }{\frac {1}{2^{k+1}}}{\binom {k}{n}}{\binom {k}{m}}.}$

そしてまた

${\displaystyle D(m,n)=\sum _{k=0}^{n}A(m,k),}$

ここで、 は ( OEISのシーケンスA266213 ) で与えられます。 ${\displaystyle A(m,k)}$

デラノワ数の基本的な再帰関係は次のように簡単に分かる。

${\displaystyle D(m,n)={\begin{cases}1&{\text{if }}m=0{\text{ or }}n=0\\D(m-1,n)+D(m-1,n-1)+D(m,n-1)&{\text{otherwise}}\end{cases}}}$

この再帰関係は生成関数に直接つながる。

${\displaystyle \sum _{m,n=0}^{\infty }D(m,n)x^{m}y^{n}=(1-x-y-xy)^{-1}.}$

中央デラノワ番号

上記の最初の閉じた式に代入し、と少し代数を加えると、 ${\displaystyle m=n}$ ${\displaystyle k\leftrightarrow n-k}$

${\displaystyle D(n)=\sum _{k=0}^{n}{\binom {n}{k}}{\binom {n+k}{k}},}$

一方、上記の2番目の式は

${\displaystyle D(n)=\sum _{k=0}^{n}{\binom {n}{k}}^{2}2^{k}.}$

中心デラノワ数は、それら自身の間にも3項再帰関係を満たす。^[8]

${\displaystyle nD(n)=3(2n-1)D(n-1)-(n-1)D(n-2),}$

生成関数を持つ

${\displaystyle \sum _{n=0}^{\infty }D(n)x^{n}=(1-6x+x^{2})^{-1/2}.}$

中心デラノワ数の主な漸近挙動は次のように与えられる。

${\displaystyle D(n)={\frac {c\,\alpha ^{n}}{\sqrt {n}}}\,(1+O(n^{-1}))}$

ここで 、および 。 ${\displaystyle \alpha =3+2{\sqrt {2}}\approx 5.828}$ ${\displaystyle c=(4\pi (3{\sqrt {2}}-4))^{-1/2}\approx 0.5727}$

参照

• モツキン数
• ナラヤナ番号
• シュレーダー・ヒッパルコス数
• シュレーダー数

参考文献

1. Banderier, Cyril; Schwer, Sylviane (2005)、「なぜデラノイ数なのか？」、Journal of Statistical Planning and Inference、135 (1): 40– 54、arXiv : math/0411128、doi :10.1016/j.jspi.2005.02.004、MR  2202337、S2CID  16226115
2. Covington, Michael A. (2004)、「2つの文字列の異なるアラインメントの数」、Journal of Quantitative Linguistics、11 (3): 173– 182、doi :10.1080/0929617042000314921、S2CID  40549706
3. ルーサー、セバスチャン; メルテンス、ステファン (2011)、「高次元における格子動物の計数」、Journal of Statistical Mechanics: Theory and Experiment、2011 (9) P09026、arXiv : 1106.1078、Bibcode :2011JSMTE..09..026L、doi :10.1088/1742-5468/2011/09/P09026、S2CID  119308823
4. Breukelaar, R.; Bäck, Th. (2005)、「遺伝的アルゴリズムを用いた多次元セルオートマトンにおける行動の進化：行動の出現」、第7回遺伝的・進化的計算に関する年次会議（GECCO '05）の議事録、ニューヨーク、ニューヨーク州、米国：ACM、pp.  107– 114、doi :10.1145/1068009.1068024、ISBN 1-59593-010-8、S2CID  207157009
5. Sulanke, Robert A. (2003)、「中心デラノイ数で数えられたオブジェクト」(PDF)、Journal of Integer Sequences、6 (1): Article 03.1.5、Bibcode :2003JIntS...6...15S、MR  1971435
6. Sloane, N. J. A. (編). 「数列 A008288 (デラノア数列 D(i,j) (i >= 0, j >= 0) の正方配列を反対角線で読み取る)」.オンライン整数数列百科事典. OEIS Foundation.
7. Alladi, K. ; Hoggatt Jr., VE (1977). 「トリボナッチ数と関連関数について」. The Fibonacci Quarterly . 15 (1): 42– 45. doi :10.1080/00150517.1977.12430503.
8. パート、ポール;ウォアン、ウェンジン (2002)。 「デラノイ再発の全客観的証拠」。議会ヌメランティウム。158 : 29–33。ISSN 0384-9864 。 ​ MR  1985142。Zbl 1030.05003  。

外部リンク

• ワイスタイン、エリック・W.「デラノワ数」。MathWorld。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Delannoy_number&oldid=1321323496"