מספר קטלן
מתוך ויקיפדיה, האנציקלופדיה החופשית
מספר קָטָלָן (Catalan) הוא מספר טבעי שמופיע בבעיות ספירה שונות בקומבינטוריקה. מספר קטלן הn-י מוגדר על ידי מקדם בינומי באופן הבא:
מספרי קטלן הראשונים (רצף A000108 בOEIS) לn=0,1,2,3 וכו' הם:
כל מספרי קטלן הם טבעיים כיוון שניתן להוכיח ש:
[עריכה] יישומים בקומבינטוריקה
- 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-ים וY-ים, אשר אינן מילות דיק. במילה כזו, יש למצוא את הY הראשון שאינו מקיים את תנאי דיק, ואז להפוך את כל האותיות אשר באות אחרי ה-Y הזה: X לY, וY לX. עתה יש בידינו מילה עם n + 1 אותיות Y וn - 1 אותיות X, ולמעשה כל מילה כזו יכולה להתקבל בדרך זו רק באופן יחיד. מספר המילים הללו שווה ל:
- אשר הוא למעשה מספר המילים שאינן מילות דיק; לכן מספר מילות דיק חייב להיות:
- זהו כמובן מספר קטלן 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 הוא גם מספר הדרכים שניתן לחלק מצולע עם 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.
[עריכה] נוסחת נסיגה וביטוי אסימפטוטי
את מספר קטלן ניתן לבטא גם בעזרת נוסחת נסיגה:
דבר זה נובע מן העובדה שכל מילת דיק w באורך גדול או שווה ל2 ניתן לכתוב בצורה יחידה באופן הבא:
- w = Xw1Yw2
כאשר w1 and w2 הן מילות דיק (ייתכן שריקות).
הפונקציה היוצרת של מספרי קטלן מוגדרת כ:
ובהצבת נוסחת הנסיגה לעיל אנו רואים כי:
לכן -
אסימפטוטית, מספרי קטלן גדלים בצורה הבאה
[עריכה] היסטוריה
סדרת מספרי קטלן תוארה לראשונה במאה ה18 על ידי לאונרד אוילר, אשר התעניין במספר הדרכים השונות לחלק מצולע למשולשים. הסדרה נקראת על שמו של יוג'ין צ'ארלס קטלן, אשר גילה את הקשר לביטויי סוגריים. טריק הספירה למילות דיק שתואר בהתחלה התגלה על ידי ד. אנדרה בשנת 1887.










