מספר מוצקין

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

מספרי מוצקין הראשונים הם:
1, 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, 15511, 41835, 113634, 310572, 853467, 2356779, 6536382, 18199284, 50852019, 142547559, 400763223, 1129760415, 3192727797, 9043402501, 25669818476, 73007772802, 208023278209, 593742784829.

התרשים הבא מראה את 9 הדרכים לחבר 4 נקודות על היקף מעגל בלי מיתרים חוצים:

קובץ:MotzkinChords4.svg

והתרשים הבא מראה את 21 הדרכים לחבר 5 נקודות על מעגל בלי מיתרים חוצים:

קובץ:MotzkinChords5.svg

הגדרות מקבילות למספרי מוצקין: מספר מוצקין ה-n-י שווה גם למספר הסדרות של מספרים שלמים חיוביים, שאורכן n-1, הן מסתיימות ומתחילות ב 1 או 2, וההפרש בין כל שני איברים רצופים בהן הוא 0, 1 או 1-.

כמו כן, מספר מוצקין ה-n-י שווה למספר המסלולים האפשריים ברביע הימני העליון של רשת קואורדינטות, מהנקודה (0,0) לנקודה (n,0) כאשר בכל צעד מותר לזוז רק לכיוון ימין, (ישירות ימינה, ימינה ולמעלה או ימינה ולמטה) ובשום שלב אסור לרדת מתחת לציר ה-x. התרשים הבא מראה את 9 המסלולים החוקיים מהנקודה (0,0) לנקודה (4,0):

קובץ:Motzkin4.svg

ב-1977 הציגו דונהיי ושפירו 14 הגדרות שונות למספרי מוצקין בענפים שונים של המתמטיקה.

ראו גם
 מספר דלנואה

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




קטגוריה:קומבינטוריקה
קטגוריה:סדרות של שלמים