קומבינטוריקה ללא חזרה

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

קומבינטוריקה ללא חזרה נפוצה בסטטיסטיקה ובמתמטיקה. זה מתאים לסיטואציות רבות בחיים האמיתיים והיישום שלו די פשוט.

קחו למשל סטודנט שיש לו בחינה בת 4 שאלות. מתוך 4 השאלות עליו לבחור שלוש.כמה שילובים שונים יכול התלמיד לעשות? אם נחשוב מעט היינו רואים (מבלי ליישם את הנוסחה בפועל) שהתלמיד יכול לבחור כיצד לענות על שלוש השאלות בארבע דרכים שונות.

• סט / אפשרות 1: ענה על שאלות 1,2,3.
• סט / אפשרות 2: ענה על שאלות 1,2,4.
• סט / אפשרות 3: ענה על שאלות 1,3,4.
• סט / אפשרות 4: ענה על שאלות 2,3,4.

כפי שאנו רואים, התלמיד יכול ליצור 4 קבוצות (n) של 3 אלמנטים (x). לכן, הקומבינטוריקה ללא חזרה אומרת לנו כיצד ליצור או לקבץ כמות סופית של נתונים / תצפיות, בקבוצות של כמות מסוימת מבלי שאפשר לחזור על אף אחד מהאלמנטים בכל קבוצה. זהו ההבדל העיקרי בין קומבינטור עם חזרה (ניתן לחזור על אלמנטים בכל קבוצה) לבין קומבינטור ללא חזרה (לא ניתן לחזור על אלמנט בכל קבוצה)

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

במקרה הקודם, בהתחשב בכך שמספר האלמנטים הכולל קטן וכמות הסט גבוהה, מספר האפשרויות קטן וניתן להסיק בקלות מבלי להחיל את הנוסחה. במקרה של יישום הנוסחה ישירות, המונה יהיה 24 (4 * 3 * 2 * 1) והמכנה יהיה 6 (3 * 2 * 1 * 1) איתו היינו מגיעים לחישוב באותו אופן. מבלי לחשוב כיצד נוכל לקבץ את ארבע השאלות הללו לקבוצות של שלוש.

כיצד מחשבים קומבינטוריקה ללא חזרה?

הנוסחה של השילוב ללא חזרה היא:

איפה:

• נ = סך התצפיות
• איקס = מספר הפריטים שנבחרו

דוגמא של קומבינטורי ללא חזרה

בואו נדמיין מחלקה צבאית של 12 חיילים. קברניט הצבא רוצה להקים קבוצות של 2 חיילים כדי להסתנן מאחורי קווי האויב בנקודות שונות, כמה קבוצות שונות הוא יכול להקים?

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

• נ = 12
• איקס = 2

בעת החלפה:

אם אנו מיישמים את המפעל עבור המכנה, יהיו לנו 12 * 11 * 10 * … * 1 = 479.001.600. עבור המכנה יש לנו 2 * 1 * 10 * 9 * 8 … * 1 = 7,257,600. המספר המשולב שלנו הוא = 479,001,600 / 7,257,600 = 66.

כפי שאנו רואים, הקפטן יכול להקים 66 זוגות חיילים שונים מבין 12 שיש לו.