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

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

תמורה (פרמוטציה) - סידור כלשהו של עצמים שונים בשורה. באופן פורמלי, תמורה היא פונקציה הפיכה מקבוצה סופית לעצמה. 
מספר התמורות השונות של n עצמים הוא !n (קרי: n עצרת). פונקציית העצרת מוגדרת בצורה רקורסיבית: בסיס הרקורסיה הוא  וערך הפונקציה ב- הוא . למשל: .  
פונקציית העצרת גדלה בקצב מהיר מאוד. אי-שוויון הממוצעים ואינטגרל פשוט אומר כי . נוסחת סטרלינג נותנת פונקציה פשוטה יותר להבנה שהיא קירוב אסימפטוטי של העצרת. 
חליפות - מספר האפשרויות לבחור k עצמים מתוך n עצמים שונים, עם חשיבות לסדר הבחירה. 
לדוגמה, מספר הדרכים לשים k כדורים שונים בתוך n תאים שונים, כשבכל תא מקום לכדור אחד בלבד (כאן בוחרים k תאים, עבור כל כדור, מתוך n תאים). הנוסחה היא או  כש-r מציין את k, ולפעמים  .
חליפות עם חזרות - מספר האפשרויות לבחור k עצמים מתוך n עצמים שונים, עם חשיבות לסדר וכשיש אפשרות לחזרות (ייתכן ש-k גדול מ-n). 
למשל, מספר הדרכים לכתוב מילה בת 5 אותיות. יש לבחור 5 אותיות מתוך 22, אך אפשר לבחור שוב ושוב באותה אות. הנוסחה היא .
צירופים - מספר האפשרויות לבחור k עצמים מתוך n עצמים שונים בלי חזרות, כאשר אין חשיבות לסדר הבחירה. בחיי היום-יום בעיות של צירופים הן שכיחות למדי. הנוסחה היא (קרי n על k או k מתוך n), או , כלומר .
חלוקות - מספר הדרכים לבחור 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 הוא בסיס הלוגריתם הטבעי.
פתרון הבעיה נעשה באמצעות "עקרון ההכלה וההפרדה". יש להפחית מסך האפשרויות הכללי את מספר המקרים שבהם אחד מהנמענים מקבל את המכתב המיועד לו. אלא שהפחתה זו מקטינה מדי, שכן הופחתו כל האפשרויות שבהן נמען א' מקבל את מכתבו ובנוסף, כל האפשרויות שבהן נמען ב' מקבל את מכתבו, אולם אפשרויות אלו נחתכות. בחלק מהמקרים גם נמען א' מקבל את מכתבו וגם נמען ב' מקבל את המכתב שנשלח אליו, ואין סיבה לגרוע מקרים אלו פעמיים.
על כן יש להוסיף את מספר המקרים שבהם נמען א' ונמען ב' שניהם מקבלים את מכתביהם, אך זו הוספה מופרזת, משום שכך מונים יתר על המידה את המקרים שבהם נמען א', נמען ב' ונמען ג' מקבלים יחדיו את מכתביהם. לפיכך צריך להוסיף ולהפחית לסירוגין.
תמורות ללא נקודות שבת (אי סדר מלא) - עשרה אנשים נכנסים למסיבה ותולים את כובעיהם על קולב. בכמה דרכים שונות הם יכולים לקחת את כובעיהם חזרה כך שאף אחד לא יקבל את כובעו המקורי בחזרה? זו למעשה בעיה קומבינטורית של תמורות ללא נקודות שבת, כלומר תמורה שבה אף אחד מהאיברים לא נשאר במקומו. 
בתורת ההסתברות ובתורת הגרפים נעשה שימוש נרחב בקומבינטוריקה. כמו כן, קיימת קומבינטוריקה גאומטרית החוקרת למשל את האפשרויות לסידור מיטבי של כדורים בתיבה.