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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה לניווט קפיצה לחיפוש

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

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

הראשון שהתייחס לבעיה של ספירת הבלבולים היה פייר ריימונד דה מונמור[3], בשנת 1708; הוא פתר אותה בשנת 1713, בערך באותו זמן שעשה זאת ניקולאס ברנולי.

השאלה האם קבוצת תמורות מכילה בלבולים כלשהם היא בעיית NP שלמה.[4]

דוגמה[עריכת קוד מקור | עריכה]

מתוך כל התמורות של הקבוצה {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 כובעים.

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

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

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

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

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

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

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

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

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

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

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

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ The name "subfactorial" originates with William Allen Whitworth (אנ'); see Cajori, Florian (2011), A History of Mathematical Notations: Two Volumes in One, Cosimo, Inc.,, עמ' 77, ISBN 9781616405717 .
  2. ^ Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics (1994), Addison–Wesley, Reading MA.
  3. ^ de Montmort, P. R. (1708).
  4. ^ 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 .
  5. ^ Hassani, M. "Derangements and Applications."
  6. ^ See the notes for סדרה {{{1}}} ב-OEIS.