عدد ديلانوي

عدد ديلانوي

سبب التسمية	هنري أوغست ديلانوي
عدد العناصر المعروفة	ما لا نهاية
Formula	${\displaystyle D(m,n)=\sum _{k=0}^{\min(m,n)}{\binom {m}{k}}{\binom {n}{k}}2^{k}}$
موسوعة المتتاليات الصحيحة على الإنترنت index	A008288 مجموعة ديلانوي المربعة

في الرياضيات، عدد ديلانوي ${\displaystyle D}$ يحسب المسارات من الزاوية الجنوبية الغربية (0, 0) لشبكة مستطيلة إلى الزاوية الشمالية الشرقية (m, n)، باستخدام خطوات مفردة فقط باتجاه الشمال أو الشمال الشرقي أو الشرق. تم تسمية أرقام ديلانوي على اسم ضابط الجيش الفرنسي وعالم رياضيات الهواة هنري ديلانوي. [1]

يحسب رقم ديلانوي ${\displaystyle D(m,n)}$ أيضًا التراصف لتسلسلين بطولين ${\displaystyle m}$ و${\displaystyle n}$، [2] النقاط في شبكة عددية صحيحة أو متعدد السطوح متقاطع الأبعاد والتي تبعد n خطوة على الأكثر عن الأصل، [3] وفي الأتمتة الخلوية، الخلايا في جوار فون نيومان في m بُعد بنصف قطر n. [4]

مثال

عدد ديلانوي D (3، 3) يساوي 63. يوضح الشكل التالي مسارات ديلانوي البالغ عددها 63 من (0، 0) إلى (3، 3):

يتم حساب المجموعة الفرعية من المسارات التي لا ترتفع فوق الخط القطري من الجنوب الغربي إلى الشمال الشرقي بواسطة عائلة ذات صلة من الأرقام، وهي أرقام شرودر.

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

مصفوفة ديلانوي عبارة عن مصفوفة لا نهائية من أرقام ديلانوي: [5]

	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 1
     1 3 1
    1 5 5 1
   1 7 13 7 1
  1 9 25 25 9 1
1 11 41 63 41 11 1

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

أرقام ديلانوي المركزية D(n) = D(n, n) هي أرقام شبكة مربعة n × n. الأرقام المركزية القليلة الأولى لديلانوي (تبدأ بـ n = 0) هي:

1، 3، 13، 63، 321، 1683، 8989، 48639، 265729، ... (التسلسل A001850 في OEIS).

حساب

أرقام ديلانوي

لـ ${\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),}$

حيث ${\displaystyle A(m,k)}$ يتم إعطاؤه مع (متسلسلة A266213 في OEIS).

من السهل رؤية العلاقة التكرارية الأساسية لأرقام ديلانوي على أنها:

${\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}},}$

في حين أن التعبير الثاني أعلاه يصبح:

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

تلبي أرقام ديلانوي المركزية أيضًا علاقة تكرار ثلاثية الحدود فيما بينها، [6]

${\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)، "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
2. Covington، Michael A. (2004)، "The number of distinct alignments of two strings"، Journal of Quantitative Linguistics، ج. 11، ص. 173–182، DOI:10.1080/0929617042000314921
3. 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
4. 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
5. 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
6. 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.

روابط خارجية

• إيريك ويستاين، Delannoy Number، ماثوورلد Mathworld (باللغة الإنكليزية).