# عدد ديلانوي

في الرياضيات، عدد ديلانوي $D$ يحسب المسارات من الزاوية الجنوبية الغربية (0, 0) لشبكة مستطيلة إلى الزاوية الشمالية الشرقية (m, n)، باستخدام خطوات مفردة فقط باتجاه الشمال أو الشمال الشرقي أو الشرق. تم تسمية أرقام ديلانوي على اسم ضابط الجيش الفرنسي وعالم رياضيات الهواة هنري ديلانوي.
يحسب رقم ديلانوي $D(m,n)$ أيضًا التراصف لتسلسلين بطولين $m$ و$n$، النقاط في شبكة عددية صحيحة أو متعدد السطوح متقاطع الأبعاد والتي تبعد n خطوة على الأكثر عن الأصل، وفي الأتمتة الخلوية، الخلايا في جوار فون نيومان في m بُعد بنصف قطر n.

## مثال

عدد ديلانوي D (3، 3) يساوي 63. يوضح الشكل التالي مسارات ديلانوي البالغ عددها 63 من (0، 0) إلى (3، 3):
يتم حساب المجموعة الفرعية من المسارات التي لا ترتفع فوق الخط القطري من الجنوب الغربي إلى الشمال الشرقي بواسطة عائلة ذات صلة من الأرقام، وهي أرقام شرودر.

## مجموعة ديلانوي

مصفوفة ديلانوي عبارة عن مصفوفة لا نهائية من أرقام ديلانوي:
| | 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 |
في هذه المصفوفة، الأرقام في الصف الأول هي واحد، والأرقام في الصف الثاني هي أرقام فردية، والأرقام في الصف الثالث هي أرقام المربع المركزي، والأرقام في الصف الرابع هي أرقام ثماني السطوح المركزية. وبدلاً من ذلك، يمكن ترتيب نفس الأرقام في مصفوفة مثلثية تشبه مثلث باسكال، والذي يُسمى أيضًا مثلث تريبوناتشي، حيث يكون كل رقم هو مجموع الأرقام الثلاثة التي فوقه:

## أرقام ديلانوي المركزية

أرقام ديلانوي المركزية D(n) = D(n, n) هي أرقام شبكة مربعة n × n. الأرقام المركزية القليلة الأولى لديلانوي (تبدأ بـ n = 0) هي:
    1، 3، 13، 63، 321، 1683، 8989، 48639، 265729، ... (التسلسل A001850 في OEIS).

## حساب
### أرقام ديلانوي

لـ $k$ خطوات قطرية (أي شمال شرقية)، يجب أن تكون هناك $m-k$ خطوات في الاتجاه $x$ و $n-k$ خطوات في الاتجاه $y$ من أجل الوصول إلى النقطة $(m,n)$؛ نظرًا لأنه يمكن تنفيذ هذه الخطوات بأي ترتيب، فإن عدد هذه المسارات يُعطى بواسطة معامل متعدد الحدود ${\binom {m+n-k}{k,m-k,n-k}}={\binom {m+n-k}{m}}{\binom {m}{k}}$. ومن ثم، نحصل على تعبير مغلق الشكل:
    $D(m,n)=\sum _{k=0}^{\min(m,n)}{\binom {m+n-k}{m}}{\binom {m}{k}}.$
يتم تقديم التعبير البديل بواسطة:
    $D(m,n)=\sum _{k=0}^{\min(m,n)}{\binom {m}{k}}{\binom {n}{k}}2^{k}$
أو بالسلسلة اللانهائية:
    $D(m,n)=\sum _{k=0}^{\infty }{\frac {1}{2^{k+1}}}{\binom {k}{n}}{\binom {k}{m}}.$
وأيضا:
    $D(m,n)=\sum _{k=0}^{n}A(m,k),$
حيث $A(m,k)$ يتم إعطاؤه مع (متسلسلة A266213 في OEIS).
من السهل رؤية العلاقة التكرارية الأساسية لأرقام ديلانوي على أنها:
    $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}}$
تؤدي علاقة التكرار هذه أيضًا بشكل مباشر إلى الدالة المولدة:
    $\sum _{m,n=0}^{\infty }D(m,n)x^{m}y^{n}=(1-x-y-xy)^{-1}.$

### أرقام ديلانوي المركزية

استبدال $m=n$ في أول تعبير مغلق أعلاه، يتم استبدال $k\leftrightarrow n-k$، يعطي:
    $D(n)=\sum _{k=0}^{n}{\binom {n}{k}}{\binom {n+k}{k}},$
في حين أن التعبير الثاني أعلاه يصبح:
    $D(n)=\sum _{k=0}^{n}{\binom {n}{k}}^{2}2^{k}.$
تلبي أرقام ديلانوي المركزية أيضًا علاقة تكرار ثلاثية الحدود فيما بينها،
    $nD(n)=3(2n-1)D(n-1)-(n-1)D(n-2),$
ولها دالة توليد:
    $\sum _{n=0}^{\infty }D(n)x^{n}=(1-6x+x^{2})^{-1/2}.$
يتم إعطاء السلوك المقارب الرائد لأرقام ديلانوي المركزية بواسطة:
    $D(n)={\frac {c\,\alpha ^{n}}{\sqrt {n}}}\,(1+O(n^{-1}))$
حيث $\alpha =3+2{\sqrt {2}}\approx 5.828$ و $c=(4\pi (3{\sqrt {2}}-4))^{-1/2}\approx 0.5727$ .

## انظر أيضا

* رقم موتسكين
* رقم شرودر

## مراجع

* ↑ Banderier، Cyril؛ Schwer، Sylviane (2005)، "Why Delannoy numbers?"، Journal of Statistical Planning and Inference، ج. 135، ص. 40–54، arXiv:math/0411128، DOI:10.1016/j.jspi.2005.02.004، MR:2202337
* ↑ Covington، Michael A. (2004)، "The number of distinct alignments of two strings"، Journal of Quantitative Linguistics، ج. 11، ص. 173–182، DOI:10.1080/0929617042000314921
* ↑ Luther، Sebastian؛ Mertens، Stephan (2011)، "Counting lattice animals in high dimensions"، Journal of Statistical Mechanics: Theory and Experiment، ج. 2011، ص. P09026، arXiv:1106.1078، Bibcode:2011JSMTE..09..026L، DOI:10.1088/1742-5468/2011/09/P09026
* ↑ Breukelaar، R.؛ Bäck، Th. (2005)، "Using a Genetic Algorithm to Evolve Behavior in Multi Dimensional Cellular Automata: Emergence of Behavior"، Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation (GECCO '05)، New York, NY, USA: ACM، ص. 107–114، DOI:10.1145/1068009.1068024، ISBN:1-59593-010-8
* ↑ Sulanke، Robert A. (2003)، "Objects counted by the central Delannoy numbers" (PDF)، Journal of Integer Sequences، ج. 6، ص. Article 03.1.5، Bibcode:2003JIntS...6...15S، MR:1971435، مؤرشف من الأصل (PDF) في 2023-12-05
* ↑ Peart، Paul؛ Woan، Wen-Jin (2002). "A bijective proof of the Delannoy recurrence". Congressus Numerantium. ج. 158: 29–33. ISSN:0384-9864. MR:1985142. Zbl:1030.05003.