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

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

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

מספר הבלבולים של קבוצה בגודל , בדרך כלל נכתב , נקרא גם "מספר de Montmort".[1] לפונקציה זו אין סימון מוסכם ולעיתים משתמשים ב־ במקום ב־ .[2]

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

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

דוגמה

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

נניח שמורה בוחן 4 תלמידים ורוצה שכל תלמיד יבדוק מבחן של אחד מעמיתיו, כאשר אף תלמיד לא יבדוק את המבחן של עצמו. בכמה דרכים יכול המורה לחלק את המבחנים לתלמידיו כדי שאלה יבדקו אותם? מתוך 24 = !4 תמורות אפשריות לחלוקת המבחנים:

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

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

ספירת בלבולים

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

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

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

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

עם תנאי ההתחלה .

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

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

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

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

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

ראו טבלה משמאל עבור ערכי הסדרה A000166 ב־OEIS.

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

קישורים חיצוניים

הערות שוליים

  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
    שגיאות פרמטריות בתבנית:OEIS

    פרמטרים [ id ] לא מופיעים בהגדרת התבנית
    סדרה , באתר OEIS – האנציקלופדיה המקוונת לסדרות של מספרים שלמים   המזהה לא מולא ולא נמצא בוויקינתונים, נא למלא את הפרמטר..


Logo hamichlol.png
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0