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

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

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

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

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

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

מספר התמורות השונות של n עצמים הוא !n (קרי: n עצרת). פונקציית העצרת מוגדרת בצורה רקורסיבית: בסיס הרקורסיה הוא וערך הפונקציה ב- הוא . למשל: .

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

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

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

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

למשל, מספר הדרכים לכתוב מילה בת 5 אותיות. יש לבחור 5 אותיות מתוך 22, אך אפשר לבחור שוב ושוב באותה אות. הנוסחה היא .

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

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

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

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

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

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

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

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


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

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

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

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

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