מספר קטלן

מספר קָטָלָן (Catalan) הוא מספר טבעי שמופיע בבעיות ספירה שונות בקומבינטוריקה. מספר קטלן ה-$\ n$-י מוגדר על ידי מקדם בינומי באופן הבא:

$C_{n}={\frac {1}{n+1}}{2n \choose n}\qquad {\mbox{ for }}n\geq 0$

מספרי קטלן הראשונים (סדרה A000108, באתר OEIS – האנציקלופדיה המקוונת לסדרות של מספרים שלמים) עבור $\ n=0,1,2,\ldots$ הם:

$1,1,2,5,14,42,132,429,1430,4862,\ldots$

כל מספרי קטלן הם שלמים כיוון ש-$\,C_{n}={2n \choose n}-{2n \choose n-1}.$.

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

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

מילת דיק (או סדרה מאוזנת) היא מחרוזת המורכבת ממספר זהה של X-ים וY-ים (ואך ורק הם), כך ששום קטע באורך כלשהו מתחילת המחרוזת אינו מכיל יותר Y-ים מאשר X-ים. לדוגמה, מילות דיק באורך 6: XXXYYY ,XYXXYY ,XYXYXY ,XXYYXY ,XXYXYY, ובהתאמה C₃ = 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$ אותיות Y ו$\ n-1$ אותיות X. יתירה מזאת, כל מילה כזו (בעלת $n+1$ אותיות Y ו$n-1$ אותיות X) יכולה להתקבל בדרך זו רק באופן יחיד, מכיוון שהטרנספורמציה שתיארנו היא הפיכה. לכן מספר המילים הללו שווה ל: ${2n \choose n-1}$ אשר הוא למעשה מספר המילים שאינן מילות דיק. לכן מספר מילות דיק חייב להיות:${2n \choose n}-{2n \choose n-1}$ וזהו מספר קטלן C_n כפי שהוגדר למעלה.

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

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

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

כאמור C_n הוא גם מספר המסלולים הקצרים ביותר מהפינה השמאלית תחתונה לפינה הימנית עליונה בסריג $n\times n$ שאינם עולים מעל לאלכסון:

ספירת שילושים

C_n הוא מספר הטריאנגולציות של מצולע קמור בן 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} שוות למספר קטלן - C_n.

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

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

$C_{0}=1\qquad {\mbox{and}}\qquad C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i}\quad {\mbox{for }}n\geq 1$

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

w = Xw₁Yw₂

כאשר w₁ and w₂ הן מילות דיק (ייתכן שריקות).

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

$c(x)=\sum _{n=0}^{\infty }C_{n}x^{n}$

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

$c(x)=1+xc(x)^{2}\,$

לכן -

$c(x)={\frac {1-{\sqrt {1-4x}}}{2x}}.$

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

$C_{n}\sim {\frac {4^{n}}{n^{3/2}{\sqrt {\pi }}}}$

היסטוריה

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

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

• טום דיוויס, Catalan Numbers - בעיות ופתרונן, אוניברסיטת קליפורניה בברקלי, 2006.