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

קוֹמְבִּינָטוֹרִיקָה היא ענף במתמטיקה בדידה, העוסק במנייה, גם בתור דרך וגם בתור תוצאה להשגת תוצאות, ובתכונות מסוימות של מבנים סופיים שונים. קומבינטוריקה קרובה מאוד לתחומים רבים במתמטיקה ויש לה שימושים רבים, ביניהם לוגיקה, פיזיקה סטטיסטית, ביולוגיה אבולוציונית, מדעי המחשב ועוד.

קומבינטוריקה היא תחום רחב מאוד במתמטיקה, כך שאין לה גבולות ברורים. בעיות קומבינטוריות עוסקות ב:

• מניה (ספירה) של מבנים שונים
• הקיום של מבנים המסוגלים לקיים קריטריונים מסוימים
• הבניה של מבנים כאלה
• אופטימיזיה של מבנים כאלו

שאלות קומבינטוריות עולות בחקר של תחומים רבים, רובם במתמטיקה עיונית, בעיקר מאלגברה, תורת ההסתברות, טופולוגיה וגאומטריה.

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

תמורה

תמורה (פרמוטציה) - סידור כלשהו של עצמים שונים בשורה. באופן פורמלי, תמורה היא פונקציה הפיכה מקבוצה סופית לעצמה.

מספר התמורות השונות של n עצמים הוא $n!$ (קרי: n עצרת). פונקציית העצרת מוגדרת בצורה רקורסיבית: בסיס הרקורסיה הוא $0!=1$ וערך הפונקציה ב-$(n+1)$ הוא $n!\cdot (n+1)$. למשל: $1\cdot 2\cdot 3\cdot 4=4!=24$.

פונקציית העצרת גדלה בקצב מהיר מאוד. אי-שוויון הממוצעים ואינטגרל פשוט אומר כי $\left({\frac {n+1}{2}}\right)^{n}\geq n!\geq \left({\frac {n}{1+\ln(n)}}\right)^{n}$. נוסחת סטרלינג נותנת פונקציה פשוטה יותר להבנה שהיא קירוב אסימפטוטי של העצרת.

חליפות

חליפוֹת (וריאציה) - מספר האפשרויות לבחור k עצמים מתוך n עצמים שונים, עם חשיבות לסדר הבחירה.

לדוגמה, מספר הדרכים לשים k כדורים שונים בתוך n תאים שונים, כשבכל תא מקום לכדור אחד בלבד (כאן בוחרים k תאים, עבור כל כדור, מתוך n תאים). הנוסחה היא ${n! \over (n-k)!}$ או $nPr$ כש-r מציין את k, ולפעמים $(n)_{k}$.

חליפות עם חזרות - מספר האפשרויות לבחור k עצמים מתוך n עצמים שונים, עם חשיבות לסדר וכשיש אפשרות לחזרות (ייתכן ש-k גדול מ-n).

למשל, מספר הדרכים לכתוב מילה בת 5 אותיות. יש לבחור 5 אותיות מתוך 22, אך אפשר לבחור שוב ושוב באותה אות. הנוסחה היא $n^{k}$.

צירופים

צירופים (קומבינציה) - מספר האפשרויות לבחור k עצמים מתוך n עצמים שונים בלי חזרות, כאשר אין חשיבות לסדר הבחירה. בחיי היום-יום בעיות של צירופים הן שכיחות למדי. הנוסחה היא ${n \choose k}$(קרי n על k או k מתוך n), או $nCk$, כלומר ${n! \over k!(n-k)!}$.

חלוקה

חלוקות (פרטיציה) - מספר הדרכים לבחור k עצמים מתוך n עצמים (ייתכן ש-k גדול מ-n), עם חזרות ובלי חשיבות לסדר.

ניתן לראות זאת כבעיה $x_{1}+x_{2}+x_{3}+\cdot \cdot \cdot +x_{n}=k$. מה מספר הדרכים להכניס מספרים שלמים אי שליליים ב-N משתנים, כך שחיבורם יתן תוצאה k? כדי לפתור בעיה זו, אפשר לדמיין שטיחת k כדורים בשורה והנחת מחיצות ב-n-1 מהמקומות שביניהם. ממילא ייווצרו n תאים הבאים זה אחר זה, בעלי גדלים משתנים, לפי מיקום המחיצות, שהמספר הכולל של כדורים בהם הוא k (שימו לב לאפשרות שתא אינו מכיל כדורים כלל). כלומר, מונחת לפנינו שורה ובה מקום ל-n-1 מחיצות ול-k כדורים, ויש לבחור היכן למקם את המחיצות. זו בעיית צירופים, והפתרון לה הוא ${k+n-1 \choose k}$ כלומר k+n-1 על k. עוד דוגמה לחלוקות היא יצירת רצף בן k צורות כאשר הצורות נבחרות מ-n אפשרויות שונות.

בעיות ושיטות נוספות

עם בעיות קומבינטוריקה מורכבות יותר מתמודד משפט פוליה, העושה שימוש בפונקציית אוילר. השאלה שעליה עונה משפט פוליה היא: "כיצד ניתן להכין מחרוזת בת n חרוזים מתוך מלאי חרוזים לא מוגבל ב-k צבעים שונים".

סדרות נסיגה - חלק מבעיות הספירה ניתנות לפתרון באופן רקורסיבי. לדוגמה, אם אדם יכול לעלות בגרם מדרגות בעליית מדרגה או בעליית שתי מדרגות בבת אחת, מספר הדרכים שבהן הוא יכול להגיע למדרגה ה-n, הוא מספר הדרכים שביכולתו להגיע למדרגה ה-n-1 ועוד מספר הדרכים שבהן הוא יכול להגיע למדרגה ה-n-2 (קל לזהות כאן את סדרת פיבונאצ'י).

בעיית נסיגה מפורסמת אחרת היא מגדלי האנוי, משחק הדורש העברה של n טבעות בגודל שונה ממוט אחד לשני, תוך כדי הסתייעות במוט שלישי, ובהקפדה על כך שטבעת לא תונח על גבי קטנה ממנה. מספר הצעדים הנדרשים במשחק כדי להעביר n טבעות הוא המכפלה בשתיים של מספר הצעדים הנדרשים להעברת n-1 טבעות, בתוספת אחת.

פותחו נוסחאות המאפשרות חישוב ישיר של איבר בנוסחת נסיגה, מבלי צורך לחשב איבר אחר איבר. שיטה אחת להוכחת נוסחה כללית היא האינדוקציה.

עקרון ההכלה וההפרדה - מאפשר לחשב את האיחוד של כמה קבוצות, באמצעות הגודל של כל אחת מהן ושל החיתוך של כל משפחה של קבוצות מתוכן. אחת הדוגמאות המוכרות לשימוש בעיקרון זה היא ספירה של התמורות ללא נקודות שבת: דוור מבולבל מחלק באקראי n מכתבים ל-n תיבות. מהו הסיכוי שאף מכתב לא יגיע לתעודתו הנכונה? מתברר שסיכוי זה שואף ל-${\frac {1}{e}}$, כאשר e הוא בסיס הלוגריתם הטבעי. פתרון הבעיה נעשה באמצעות "עקרון ההכלה וההפרדה". יש להפחית מסך האפשרויות הכללי את מספר המקרים שבהם אחד מהנמענים מקבל את המכתב המיועד לו. אלא שהפחתה זו מקטינה מדי, שכן הופחתו כל האפשרויות שבהן נמען א' מקבל את מכתבו ובנוסף, כל האפשרויות שבהן נמען ב' מקבל את מכתבו, אולם אפשרויות אלו נחתכות. בחלק מהמקרים גם נמען א' מקבל את מכתבו וגם נמען ב' מקבל את המכתב שנשלח אליו, ואין סיבה לגרוע מקרים אלו פעמיים. על כן יש להוסיף את מספר המקרים שבהם נמען א' ונמען ב' שניהם מקבלים את מכתביהם, אך זו הוספה מופרזת, משום שכך מונים יתר על המידה את המקרים שבהם נמען א', נמען ב' ונמען ג' מקבלים יחדיו את מכתביהם. לפיכך צריך להוסיף ולהפחית לסירוגין.

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

נושאים נוספים

• משפט החתונה עוסק באפשרות לבחירה של איברים מייצגים שונים זה מזה למשפחה של קבוצות.
• משפט רמזי עוסק בצורה שבה סדר חייב להתקיים בקבוצה אם היא גדולה מספיק.
• בעיית הנהגים הגחמנים היא בעיה העוסקת במספר הדרכים לשבץ n עצמים ב-n מקומות, כאשר לכל עצם יש מקום מועדף, ועצם שהמקום המועדף עליו תפוס, מוסט באופן עקבי כלפי מעלה.

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

• גדי אלכסנדרוביץ', מהי קומבינטוריקה?, באתר "לא מדויק", 20 ביוני 2010
• קומבינטוריקה, באתר אנציקלופדיה למתמטיקה (באנגלית)
• מחשבון אפשרויות בעברית
• קומבינטוריקה, באתר MathWorld (באנגלית)
• קומבינטוריקה, באתר אנציקלופדיה בריטניקה (באנגלית)
• אנליזה קומבינטורית, דף שער בספרייה הלאומית

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

35926013קומבינטוריקה