בלבול (קומבינטוריקה)

בקומבינטוריקה, בלבול או תמורה ללא נקודות שבת (באנגלית: Derangement) הוא תמורה של איברי קבוצה, כך שאף איבר אינו מופיע במיקומו המקורי. במילים אחרות, בלבול הוא תמורה שאינה מכילה נקודות קבועות.

מספר הבלבולים של קבוצה בגודל , בדרך כלל נכתב בתור ‏, Dn‏, dn‏ או n¡ ונקרא גם "מספר de Montmort" ה-n-י. הראשון שהתייחס לבעיה של ספירת הבלבולים היה פייר ריימונד דה מונמור(אנ'),[1] בשנת 1708; הוא פתר אותה בשנת 1713, בערך באותו זמן שעשה זאת ניקולאס ברנולי(אנ').

השאלה האם חבורת תמורות (הנתונה על ידי קבוצת יוצרים) מכילה בלבולים כלשהם היא בעיית NP שלמה.[2]

דוגמהעריכה

 
מתוך כל התמורות של הקבוצה {A,B,C,D} יש רק 9 בלבולים (מסומנים בכתב כחול נטוי). בשאר התמורות של הקבוצה בת 4 האיברים, לפחות תלמיד אחד מקבל את המבחן שלו בחזרה (מסומנות בכתב אדום מודגש).

נניח שמורה בוחן 4 תלמידים - A, B, C, ו-D - ורוצה שכל תלמיד יבדוק מבחן של אחד מעמיתיו. כמובן שאף תלמיד לא אמור לבדוק את המבחן של עצמו. בכמה דרכים יכול המורה לחלק את המבחנים לתלמידיו כדי שאלה יבדקו אותם? מתוך 24 תמורות אפשריות (4!) לחלוקת המבחנים:

יש רק 9 בלבולים (מסומנים בכתב כחול נטוי). בשאר התמורות של הקבוצה בת 4 האיברים, לפחות תלמיד אחד מקבל את המבחן שלו בחזרה (מסומנות בכתב אדום מודגש).

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

ספירת בלבוליםעריכה

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

נניח שיש n אנשים ממוספרים 1, 2, ..., n. וכן n כובעים ממוספרים 1, 2, ..., n. עלינו למצוא את מספר הדרכים בהן אף אחד לא מקבל את הכובע שממוספר כמוהו. נניח כי האדם הראשון לוקח את הכובע הממוספר ב-i, מתוך n − 1 אפשרויות. כעת יש שתי אפשרויות - תלוי אם האדם ה-i לוקח את כובע מספר 1:

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

מכאן ניתן להגיע לנוסחה הבאה:

 

כאשר  , המכונה פונקציית הבלבול, מייצג את מספר הבלבולים, עם תנאי ההתחלה !0 = 1 ו- !1 = 0.

אותה נוסחת נסיגה עובדת גם עבור עצרת, עם תנאי התחלה שונים: 0! = 1, 1! = 1

 

וזה עוזר להוכיח את הגבול עם e בהמשך.

כמו כן, הנוסחאות להלן ידועות גם כן:[3]

 
 

כאשר   היא פונקציית העיגול (מעגלת למספר השלם הקרוב) ו   היא פונקציית הרצפה (מעגלת למספר השלם הנמוך).

 
 

להלן נוסחה נוספת:[4]

 

החל מ- n = 0, מספר הבלבולים של n הם:

1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, ... (סדרה A000166 ב-OEIS).

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

 

חישוב   נותן את הנוסחה הבאה:  

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

תמורות עם נקודות שבתעריכה

מספר התמורות האפשריות בגודל n עם בדיוק k נקודות שבת ניתן בנוסחה:  

קישורים חיצונייםעריכה

הערות שולייםעריכה

  1. ^ de Montmort, P. R. (1708).
  2. ^ Lubiw, Anna (1981), "Some NP-complete problems similar to graph isomorphism", SIAM Journal on Computing 10 (1): 11–21, MR 605600, doi:10.1137/0210002 .
  3. ^ Hassani, M. "Derangements and Applications."
  4. ^ See the notes for סדרה {{{1}}} ב-OEIS.