德蘭諾依數是組合數學中用於描述格點路徑方案數的特殊數列，以法國軍官、業餘數學家亨利·德蘭諾依命名。該數計算從坐標(0,0)到(m,n)的路徑總數，每一步允許沿(0,1)、(1,0)或(1,1)方向移動。
其計算需要考慮三種移動方向的組合排列：設對角線(1,1)移動k步，橫向(1,0)需移動(m-k)步，縱向(0,1)需移動(n-k)步。當m或n為0時，德蘭諾依數D(m,n)恆為1。特別地，當m=n時稱為中心德蘭諾依數，前幾項為1,3,13,63,321等（OEIS A001850），具有特定的遞推關係和生成函式。
該數列源於亨利·德蘭諾依對格路問題的研究，其矩陣形式展示了不同(m,n)組合下的數值分布規律。中心德蘭諾依數的生成函式及遞推公式進一步揭示了該數列的內在數學特性。
基本介紹
- 中文名：德蘭諾依數
- 外文名：Delannoy number
定義,示例,德蘭諾依數組,計算,
定義
在組合數學中，德蘭諾依數描述了從(0,0)到(m,n)的格路問題中，只允許按照（0,1）、（1,0）或者(1,1)的方式來走，一共有多少不同的方案數。德蘭諾依數是以法國軍官、業餘數學家亨利·德蘭諾依的名字命名的。
示例
當m=3,n=3時，德蘭諾依數D(3,3)=63,下面展示了所有63種不同方案。
德蘭諾依數
德蘭諾依數組
德蘭諾依數組以矩陣形式展示了不同m,n組合下的德蘭諾依數。
n\m | 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行(列)均為中心正方形數(OEIS A001844)。
- 第4行(列)均為中心正八面體數(OEISA001845)。
- 以左上角為頂點，構成了帕斯卡三角。
中心德蘭諾依數
中心德蘭諾依數是指m=n時的德蘭諾依數，即D(n,n).該數列的前幾項為
1, 3, 13, 63, 321, 1683, 8989, 48639, 265729,.....(OEIS A001850)
計算
假設對角線方向(1,1)一共走了k步，那么x方向(1,0)必為(m-k)步，y方向(0,1)必為(n-k)步，且三個方向上的順序可以任意調整。
故
D(m,n)的遞推關係可以寫為
當m=0或n=0時，D(m,n)=1。
由遞推關係可寫出其生成函式為：
對於中心德蘭諾依數，
中心德蘭諾依數的遞推關係為
由遞推關係求出其生成函式為
