מספר קטלן

מספר קָטָלָן (Catalan) הוא מספר טבעי שמופיע בבעיות ספירה שונות בקומבינטוריקה. מספר קטלן ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} -י מוגדר על ידי מקדם בינומי באופן הבא: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_n = {2n\choose n} - {2n\choose n+1} = \frac{1}{n+1}{2n\choose n} \qquad\mbox{ for }n\ge 0} מספרי קטלן הראשונים (סדרה A000108 באתר OEIS – האנציקלופדיה המקוונת לסדרות של מספרים שלמים) עבור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n =0, 1, 2, \ldots} הם: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, \ldots} כל מספרי קטלן הם שלמים כיוון ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,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 אותיות X ו-(1-n) אותיות Y. יתירה מזאת, כל מילה כזו (בעלת n+1 אותיות X ו- (1-n) אותיות Y) יכולה להתקבל בדרך זו רק באופן יחיד, מכיוון שהטרנספורמציה שתיארנו היא הפיכה. לכן מספר המילים הללו שווה ל: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle {2n\choose n+1}} אשר הוא למעשה מספר המילים שאינן מילות דיק. לכן מספר מילות דיק חייב להיות:הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle {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. ביטויים כאלה ניתן לייצג באופן טבעי על ידי עצים בינאריים מסודרים עם שורש, כך ש-C_n סופר גם את מספר העצים הללו עם n + 1 עלים.

קובץ:Catalan number binary tree example.png

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

כאמור C_n הוא גם מספר המסלולים הקצרים ביותר מהפינה השמאלית תחתונה לפינה הימנית עליונה בסריג הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \times n } שאינם עולים מעל לאלכסון:

קובץ:Catalan number 4x4 grid example.svg

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

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

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

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

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 = Xw₁Yw₂

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

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c(x)=\sum_{n=0}^\infty C_n x^n}

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c(x)=1+xc(x)^2\,}

לכן -

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c(x) = \frac{1-\sqrt{1-4x}}{2x}.}

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}}

היסטוריה

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

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

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

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

לקריאה נוספת

• Richard Stanley, ``Catalan Numbers, Cambridge University Press, 2015.

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

מספר קטלן32996114Q270513