פרמוטציות ושילובים, הדרכים השונות בהן ניתן לבחור עצמים מקבוצה, בדרך כלל ללא החלפה, ליצירת קבוצות משנה. בחירה זו של קבוצות משנה נקראת פרמוטציה כאשר סדר הבחירה הוא גורם, שילוב כאשר הסדר אינו גורם. בהתחשב ביחס בין מספר קבוצות המשנה הרצויות למספר כל קבוצות המשנה האפשריות למשחקי סיכוי רבים במאה ה -17, המתמטיקאים הצרפתים בלייז פסקל ופייר דה פרמה העניקו תנופה להתפתחות הקומבינטוריקה ותורת ההסתברות.
קומבינטוריקה: מקדמים בינומיים
אובייקטים n נקרא פרמוטציה של n דברים שצולמו r בכל פעם. מספר התמורות הוא
ניתן להמחיש את המושגים וההבדלים בין פרמוטציות ושילובים על ידי בחינת כל הדרכים השונות בהן ניתן לבחור זוג אובייקטים מחמישה עצמים מובחנים - כמו האותיות A, B, C, D ו- E. אם שניהם נשקלות האותיות שנבחרו וסדר הבחירה, ואז אפשריות 20 התוצאות הבאות:
כל אחת מעשרים הבחירות האפשריות השונות נקרא פרמוטציה. בפרט, הם נקראים פרמוטציות של חמישה אובייקטים שצולמו שניים בכל פעם, ומספר התמורות כאלה האפשריות מסומן על ידי הסמל 5 P 2, קרא "5 permute 2." באופן כללי, אם יש n אובייקטים זמינים לבחירה, ויש ליצור תעלות (P) באמצעות k של האובייקטים בכל פעם, מספר התעלות השונות האפשריות מסומן על ידי הסמל n P k. הנוסחה להערכתה היא n P k = n! / (N - k)! הביטוי n! —Read "n factorial" - מציין כי יש לכפול את כל המספרים השלמים החיוביים הרצופים בין 1 עד וכלל n, ו 0! מוגדר כשווה 1. לדוגמה, באמצעות נוסחה זו, מספר התמריציות של חמישה אובייקטים שצולמו שניים בכל פעם הוא
(עבור k = n, n P k = n! לפיכך, עבור 5 עצמים ישנם 5! = 120 סידורים.)
עבור שילובים, אובייקטים k נבחרים מתוך קבוצה של n אובייקטים לייצור קבוצות משנה ללא הזמנה. בניגוד לדוגמת הפרמוטציה הקודמת עם השילוב המקביל, קבוצות המשנה של AB ו- BA אינן עוד בחירות מובחנות; על ידי ביטול מקרים כאלה נותרו רק 10 קבוצות משנה שונות - AB, AC, AD, AE, BC, BD, BE, CD, CE ו- DE.
המספר של קבוצות משנה כאלה מסומן על ידי n C k, קרא "n בחר k." עבור שילובים, מכיוון שאובייקטים k הם בעלי k! סידורים, יש k! פרמוטים בלתי ניתנים להבחנה עבור כל בחירה באובייקטים k; ומכאן חלוקת נוסחת הפרמוטציה ב- k! מניב את נוסחת השילוב הבאה:
זהה למקדם הבינומי (n, k) (ראה משפט בינומי). לדוגמה, מספר השילובים של חמישה אובייקטים שצולמו שניים בכל פעם הוא
הפורמולות עבור n P k ו n C k נקראים נוסחאות הספירה מאז הם יכולים לשמש כדי לספור את מספר התמורות האפשריות או שילובים במצב נתון מבלי לפרט את כולם.
