מספר קטלן

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

C_n = \frac{1}{n+1}{2n\choose n} \qquad\mbox{ for }n\ge 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}..

יישומים בקומבינטוריקה[עריכת קוד מקור | עריכה]

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 אותיות Y ו\ n-1 אותיות X. יתירה מזאת, כל מילה כזו (בעלת n+1 אותיות Y וn-1 אותיות X) יכולה להתקבל בדרך זו רק באופן יחיד, מכיוון שהטרנספורמציה שתיארנו היא הפיכה. לכן מספר המילים הללו שווה ל: {2n\choose n-1} אשר הוא למעשה מספר המילים שאינן מילות דיק. לכן מספר מילות דיק חייב להיות:{2n\choose n}-{2n\choose n-1} וזהו מספר קטלן 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 עלים.

Catalan number binary tree example.png

מסלולים בריבוע[עריכת קוד מקור | עריכה]

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

Catalan number 4x4 grid example.svg

ספירת שילושים[עריכת קוד מקור | עריכה]

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

Catalan-Hexagons-example.svg

מיון מחסנית[עריכת קוד מקור | עריכה]

אם 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.

נוסחת נסיגה וביטוי אסימפטוטי[עריכת קוד מקור | עריכה]

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

C_0 = 1 \qquad \mbox{and} \qquad C_n=\sum_{i=0}^{n-1}C_i C_{n-1-i}\quad\mbox{for }n\ge 1

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

w = Xw1Yw2

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

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

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.

קישורים חיצוניים[עריכת קוד מקור | עריכה]