מספר דלנואה

מספר דלנואה (בצרפתית: Delannoy) במתמטיקה מתאר את מספר המסלולים בסריג מלבני מהפינה הדרום-מערבית (0,0) עד הפינה הצפון-מזרחית (m,n) תוך התקדמות צפונה, מזרחה או צפון-מזרחה בלבד. מספרי דלנואה נקראים על-שם המתמטיקאי הצרפתי הנרי דלנואה. מספרים אלה גם נותנים את:

• מספר הרצפים הגלובלי של שני רצפים באורך m ו n
• מספר הנקודות בסריג בעל מספר שלם m של ממדים במרחק צעדים מקסימלי n.
• באוטומט תאי את מספר התאים בסביבת פון נוימן במימד m וברדיוס n.

דוגמה

מספר דלנואה (3,3) הוא 63. באיור הבא מוצגים 63 מסלולי דלנואה בסריג 3 x‏ 3:

תת הקבוצה של מסלולים שאינם חוצים את האלכסון דרום-מערב - צפון-מזרח ניתנת על ידי משפחת מספרים אחרת מספרי שרדר.

מערך דלנואה

מערך דלנואה הוא מטריצה אינסופית של מספרי דלנואה.

m / 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
          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

מספרי דלנואה מרכזיים

סדרת מספרי דלנואה המרכזיים היא אלכסון המערך ונותנת את מספר המסלולים בסריגים ריבועיים n X n. האיברים הראשונים של הסדרה הם: 1, 3, 13, 63, 321, 1683,... זו סדרה רקורסיבית :

$nD(n)=3(2n-1)D(n-1)-(n-1)D(n-2)$

ניתן לבטא אותה באמצעות פולינומי לז'נדר $P_{n}(x)$:

$D(n)=P_{n}(3)$

הפונקציה היוצרת היא:

$\sum D(n)x^{n}=(1-6x+x^{2})^{-1/2}$

ראו גם

• מספר מוצקין

קישורים חיצוניים

• מספר דלנואה, באתר MathWorld (באנגלית)