ויקיפדיה:מיזמי ויקיפדיה/אתר האנציקלופדיה היהודית/מיון נושאים: לוויקי/קומבינטוריקה

שגיאות פרמטריות בתבנית:להשלים
פרמטרי חובה [ נושא ] חסרים

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

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

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

מספר התמורות של n עצמים הוא !n (קרי: n עצרת, פונקציה השווה למכפלת כל השלמים מ-1 ועד n זה בזה: $n!={\begin{cases}1\cdot 2\cdot 3\cdot \cdot \cdot n,&n\in \mathbb {N} \\1,&n=0\end{cases}}$ . למשל: $1\cdot 2\cdot 3\cdot 4=4!=24$)
יש יותר מטריליון אפשרויות לסדר 15 עצמים שונים בשורה.

הסיבה לכך ש-$\ n!$ הוא מספר האפשרויות לסדר $n$ עצמים שונים בשורה היא פשוטה: בכמה מקומות ניתן לשים את העצם הראשון? $n$ מקומות (כל המקומות פנויים). בכמה מקומות ניתן לשים את העצם השני? $n-1$ מקומות, שכן מקום אחד כבר תפוס על ידי העצם הראשון. כך הלאה, עד לעצם האחרון, לו נשאר רק מקום אחד פנוי. בסך-הכל יש $n$ אפשרויות לסידור העצם הראשון; על כל אפשרות כזו יש $n-1$ אפשרויות לסידור העצם השני, וכן הלאה: $n\cdot (n-1)\cdot \cdot \cdot 3\cdot 2\cdot 1=n!$

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

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

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

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

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

במקורות היהדות

בספר יצירה נאמר ”שתי אבנים - בונות שתי בתים; שלש - בונות ששה בתים; ארבע - בונות עשרים וארבעה בתים; חמש - בונות ק"ך בתים; שש - בונות שבע מאות ועשרים בתים; שבע - בונות חמשת אלפים וארבעים בתים; מכאן ואילך - צא וחשוב מה שאין הפה יכול לדבר, ולא האזן יכולה לשמוע”. המשנה מפרטת את התמורות השונות של עד שבעה עצמים, ומשם ואילך המספר גדול כל כך עד "שאין הפה יכול לדבר, ולא האוזן יכולה לשמוע" (ובאמת $8!=40,320$ וגדילת המספר הלאה היא בהפרשים גדולים ביותר).

"צירופי שמות" בקבלה הם כל האפשרויות לכתוב את אותיות השם. למשל שם י-ה-ו-ה יש לו 12 צירופים כי יש שתי פעמים את האות ה' אבל שם א-ד-נ-י יש לו 24 צירופים ושם ש-ד-י יש לו 6 צירופים.

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

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

הערות שוליים

*