סידור לעומת בחירה: תמורות, דגימה סידורית וצירופים

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

סדר, בחירה והחזרה

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

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

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

תמורה: סידור של כל העצמים

תמורה היא סידור בשורה של כל n העצמים השונים שבאוסף. מספר התמורות הוא n! = n×(n-1)×(n-2)×...×2×1. הסיבה היא שיש n אפשרויות לבחירת העצם הראשון, n-1 אפשרויות לשני, n-2 לשלישי, וכך עד שנותר עצם אחד.

לדוגמה, מספר הדרכים לסדר ארבעה ספרים שונים על מדף הוא 4! = 24. מספר הדרכים להעמיד חמישה חיילים בטור הוא 5! = 120. בשני המקרים כל העצמים משתתפים בסידור, ולכן זו תמורה ולא בחירה של חלק מהעצמים.

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

דגימה סידורית ללא החזרה

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

הנוסחה נובעת מעיקרון הכפל: יש n אפשרויות לבחירה הראשונה, n-1 אפשרויות לשנייה, n-2 לשלישית, וכן הלאה עד k בחירות. לכן מכפילים n×(n-1)×...×(n-k+1). הסימון n!/(n-k)! הוא דרך קצרה לכתוב את המכפלה הזאת.

לדוגמה, בחירת שלושה תלמידים מתוך עשרה לשלושה תפקידים שונים היא דגימה סידורית ללא החזרה. התפקידים שונים, ולכן הסדר חשוב; ותלמיד אינו יכול למלא יותר מתפקיד אחד. מספר האפשרויות הוא 10×9×8 = 720.

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

דגימה סידורית עם החזרה

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

לדוגמה, קוד בן ארבע ספרות, שבו מותר גם להתחיל בספרה 0 וכל ספרה יכולה לחזור, נותן 10×10×10×10 = 10,000 קודים. זו דגימה סידורית עם החזרה: הסדר בין הספרות חשוב, וכל ספרה יכולה להופיע שוב. אם מדובר בקוד ואסור לחזור על ספרה, מספר האפשרויות הוא 10×9×8×7. אם מדובר במספר בן ארבע ספרות, הספרה הראשונה אינה יכולה להיות 0 ולכן יש להתייחס אליה בנפרד.

צירוף: בחירה ללא חשיבות לסדר

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

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

דוגמה: בחירת שלושה תלמידים מתוך עשרה לוועד שבו כל החברים שווים היא צירוף. מספר האפשרויות הוא C(10,3) = 120. אם לאותם שלושה תלמידים מחלקים תפקידים שונים, כל ועד יכול להופיע ב-3! = 6 סידורים פנימיים, ולכן מתקבל 120×6 = 720.

הקשר בין סידור לבחירה

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

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

זיהוי סוג הספירה בבעיה

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

אם הסדר חשוב, בודקים החזרה: בלי החזרה — דגימה סידורית ללא החזרה; עם החזרה — דגימה סידורית עם החזרה. אם הסדר אינו חשוב והבחירה היא ללא החזרה, מדובר בצירוף.

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

תנאים נפוצים בסידור ובבחירה

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

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