מספר קטלן

מספר טבעי שמופיע בבעיות ספירה שונות בקומבינטוריקה

מספר קָטָלָן (Catalan) הוא מספר טבעי שמופיע בבעיות ספירה שונות בקומבינטוריקה. מספר קטלן ה--י מוגדר על ידי מקדם בינומי באופן הבא: מספרי קטלן הראשונים (סדרה A000108 באתר OEIS – האנציקלופדיה המקוונת לסדרות של מספרים שלמים) עבור הם: כל מספרי קטלן הם שלמים כיוון ש- , והמקדם הבינומי הוא תמיד שלם.

יישומים בקומבינטוריקה

עריכה

Cn שווה למספר מילות דיק באורך 2n

עריכה
מילת דיק (או סדרה מאוזנת) היא מחרוזת המורכבת ממספר זהה של X-ים ו-Y-ים (ואך ורק הם), כך ששום קטע באורך כלשהו מתחילת המחרוזת אינו מכיל יותר Y-ים מאשר X-ים. לדוגמה, מילות דיק באורך 6: XXXYYY ,XYXXYY ,XYXYXY ,XXYYXY ,XXYXYY ובהתאמה C3 = 5. אם נחשוב על X ו-Y כסוגריים (כאשר X הוא פותח, ו-Y סוגר), הרי שמילת דיק באורך 2n יכולה לבטא את מספר הביטויים עם n זוגות של סוגריים הממוקמים בצורה חוקית: ((())), ()(()), ()()(), (())(), (()()). ניתן לייצג מילות דיק גם כשבילים מסוימים ברשת עם n+1 על n+1 צמתים המחוברים ביניהם בקווים אנכיים ואופקיים. השבילים מתחילים בפינה השמאלית התחתונה, ומסתיימים בפינה הימנית העליונה, כאשר אפשר לנוע עליהם רק ימינה ולמעלה, ואסור להיות מעל האלכסון בין הפינות הללו. בייצוג זה - X הוא תנועה "ימינה" ו-Y הוא תנועה "למעלה".
ניתן לספור את מילות דיק באמצעות השיטה הבאה: נתמקד על המילים המכילות n מופעים של X ו-n מופעים של Y, אשר אינן מילות דיק. במילה כזו, יש למצוא את ה-Y הראשון שאינו מקיים את תנאי דיק, ואז להפוך את כל האותיות עד (וכולל) ה-Y הזה: X ל-Y, ו-Y ל-X. עתה יש בידינו מילה עם n+1 אותיות X ו-(1-n) אותיות Y. יתירה מזאת, כל מילה כזו (בעלת n+1 אותיות X ו- (1-n) אותיות Y) יכולה להתקבל בדרך זו רק באופן יחיד, מכיוון שהטרנספורמציה שתיארנו היא הפיכה. לכן מספר המילים הללו שווה ל:   אשר הוא למעשה מספר המילים שאינן מילות דיק. לכן מספר מילות דיק חייב להיות:  וזהו מספר קטלן Cn כפי שהוגדר למעלה.

מספר ביטויי הסוגריים

עריכה

Cn הוא מספר הדרכים השונות לשים סוגריים על n + 1 גורמים שונים. לדוגמה, כאשר n=3, יש 5 דרכים שונות לשים סוגריים על 4 גורמים: a(b(cd)), a((bc)d), (ab)(cd), (a(bc))d, ((ab)c)d. ביטויים כאלה ניתן לייצג באופן טבעי על ידי עצים בינאריים מסודרים עם שורש, כך ש-Cn סופר גם את מספר העצים הללו עם n + 1 עלים.

 

מסלולים בריבוע

עריכה

כאמור Cn הוא גם מספר המסלולים הקצרים ביותר מהפינה השמאלית תחתונה לפינה הימנית עליונה בסריג   שאינם עולים מעל לאלכסון:

 

ספירת שילושים (טריאנגולציות)

עריכה

Cn הוא מספר הטריאנגולציות של מצולע קמור בן n+2 צלעות (חלוקות של המצולע למשולשים).

 

מיון מחסנית

עריכה

אם w הוא רצף סופי של מספרים שלמים שונים, אנו מגדירים סידור-מחדש (S(w באופן רקורסיבי בצורה הבאה: רשום w = unv כאשר n הוא האלמנט הגדול ביותר ב-w, ו-u ו-v הם רצפים קצרים יותר, והגדר S(w) = S(u)S(v)n כאשר S הוא הזהות על רצפים בעלי אורך 1. התמורה w מתוך {1, ..., n} נקראת ניתנת למיון-מחסנית (stack-sortable) אם (S(w) = (1, ..., n. מספר התמורות הללו על {1, ..., n} שוות למספר קטלן - Cn.

תמורה ניתנת למיון-מחסנית אם ורק אם היא נמנעת מן התבנית 231 (כלומר, אין בה שלושה ערכים a,b,c, בסדר זה, המקיימים c<a<b). לכן מספר התמורות הנמנעות מן התבנית 231 הוא מספר קטלן. מתברר שלכל תמורה s על שלושה איברים, מספר התמורות באורך n הנמנעות מ-s הוא מספר קטלן ה-n-י.

נוסחת נסיגה וביטוי אסימפטוטי

עריכה

את מספר קטלן ניתן לבטא גם בעזרת נוסחת נסיגה:

 

דבר זה נובע מן העובדה שכל מילת דיק w באורך גדול או שווה ל-2 ניתן לכתוב בצורה יחידה באופן הבא:

w = Xw1Yw2

כאשר w1 and w2 הן מילות דיק (ייתכן שריקות).

הפונקציה היוצרת של מספרי קטלן מוגדרת כ:

 

ובהצבת נוסחת הנסיגה לעיל אנו רואים כי:

 

לכן -

 

אסימפטוטית, מספרי קטלן גדלים בצורה הבאה:

 

היסטוריה

עריכה

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

לקריאה נוספת

עריכה
  • Richard Stanley, ``Catalan Numbers, Cambridge University Press, 2015.

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

עריכה
  מדיה וקבצים בנושא מספר קטלן בוויקישיתוף