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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
Incomplete-document-purple.svg יש להשלים ערך זה: בערך זה חסר תוכן מהותי. ייתכן שתמצאו פירוט בדף השיחה.
הנכם מוזמנים להשלים את החלקים החסרים ולהסיר הודעה זו. שקלו ליצור כותרות לפרקים הדורשים השלמה, ולהעביר את התבנית אליהם.

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

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

תמורה (פרמוטציה) - סידור כלשהו של n עצמים שונים בשורה. הנוסחה למציאת מספר התמורות היא !n (קרי: n עצרת, פונקציה השווה למכפלת כל השלמים מ-1 ועד n זה בזה - למשל: 1\cdot 2\cdot 3\cdot 4=24=4!).דוגמה לתמורה עם חזרות: 12 מקומות, 12 דגלים לסדר בשורה, 5 אדומים, 4 כחולים, 3 צהובים, פתרון: (!3!4!5)/!12. כבר עבור מספר עצמים קטן נוסק מספר אפשרויות הסידור לגבהים עצומים. יש יותר מטריליון אפשרויות לסדר 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, וזו נוסחת החלוקות.

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

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

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

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

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


תמורות ללא נקודות שבת - עשרה אנשים נכנסים למסיבה ותולים את כובעיהם על קולב. בכמה דרכים שונות הם יכולים לקחת את כובעיהם חזרה כך שאף אחד לא יקבל את כובעו המקורי בחזרה? זו למעשה בעיה קומבינטורית של תמורות ללא נקודות שבת, כלומר תמורה שבה אף אחד מהאיברים לא נשאר במקומו.

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

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

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

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