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

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

מספר הבלבולים של קבוצה בגודל $n$, בדרך כלל נכתב בתור $!n$‏, D_n‏, d_n‏ או n¡ ונקרא גם "מספר de Montmort" ה-n-י. הראשון שהתייחס לבעיה של ספירת הבלבולים היה פייר ריימונד דה מונמור, בשנת 1708; הוא פתר אותה בשנת 1713, בערך באותו זמן שעשה זאת ניקולאס ברנולי.

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

דוגמה

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

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

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

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

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

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

טבלת ערכים
$n$	תמורות, $n!$	בלבולים, $!n$	${\frac {!n}{n!}}$
0	1 =1×100	1 =1×100	= 1
1	1 =1×100	0	= 0
2	2 =2×100	1 =1×100	= 0.5
3	6 =6×100	2 =2×100	≈0.3333333333
4	24 =2.4×101	9 =9×100	= 0.375
5	120 =1.20×102	44 =4.4×101	≈0.3666666667
6	720 =7.20×102	265 =2.65×102	≈0.3680555556
7	5,040 ≈5.04×103	1854 ≈1.85×103	≈0.3678571429
8	40320 ≈4.03×104	14833 ≈1.48×104	≈0.3678819444
9	362880 ≈3.63×105	133496 ≈1.33×105	≈0.3678791887
10	3628800 ≈3.63×106	1334961 ≈1.33×106	≈0.3678794643
11	39916800 ≈3.99×107	14684570 ≈1.47×107	≈0.3678794392
12	479001600 ≈4.79×108	176214841 ≈1.76×108	≈0.3678794413
13	6227020800 ≈6.23×109	2290792932 ≈2.29×109	≈0.3678794412
14	87178291200 ≈8.72×1010	32071101049 ≈3.21×1010	≈0.3678794412
15	1307674368000 ≈1.31×1012	481066515734 ≈4.81×1011	≈0.3678794412
16	20922789888000 ≈2.09×1013	7697064251745 ≈7.70×1012	≈0.3678794412
17	355687428096000 ≈3.56×1014	130850092279664 ≈1.31×1014	≈0.3678794412

נניח שיש 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=(n-1)(!(n-1)+!(n-2)).\,$

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

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

$n!=(n-1)((n-1)!+(n-2)!)\,$

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

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

$!n=n!\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}},$

$!n=\left[{\frac {n!}{e}}\right]=\left\lfloor {\frac {n!}{e}}+{\frac {1}{2}}\right\rfloor ,\quad n\geq 1$

כאשר $\left[x\right]$ היא פונקציית העיגול (מעגלת למספר השלם הקרוב) ו $\left\lfloor x\right\rfloor$ היא פונקציית הרצפה (מעגלת למספר השלם הנמוך).

$!n=\left\lfloor (e+e^{-1})n!\right\rfloor -\lfloor en!\rfloor ,\quad n\geq 2,$

$!n=n!-\sum _{i=1}^{n}{n \choose i}\cdot !(n-i),$

להלן נוסחה נוספת:

$!n=n[!(n-1)]+(-1)^{n}$

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

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

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

$!n=n!-{n \choose 1}(n-1)!+{n \choose 2}(n-2)!-\cdots \pm {n \choose n}0!=n!+\sum _{i=1}^{n}(-1)^{i}{n \choose i}(n-i)!.$

חישוב $!n$ נותן את הנוסחה הבאה: $!n=n!\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}}$

לכן ההסתברות שתמורה אקראית תהיה בלבול היא ${!n \over n!}=\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}}$. טור זה הוא טור טיילור של הפונקציה $\ e^{-x}$ בנקודה 1 (או טור טיילור של הפונקציה $\ e^{x}$ בנקודה $\,-1$). על כן, כאשר $\,n$ שואף לאינסוף, שואף סכום הטור ל-${\frac {1}{e}}$.

תמורות עם נקודות שבת

מספר התמורות האפשריות בגודל n עם בדיוק k נקודות שבת ניתן בנוסחה: $D_{n,k}={n \choose k}\cdot D_{n-k,0}={n \choose k}\cdot !(n-k)$

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

• Baez, John (2003). "Let's get deranged!" (PDF).
• Bogart, Kenneth P.; Doyle, Peter G. (1985). "Non-sexist solution of the ménage problem".
• Dickau, Robert M. "Derangement diagrams". Mathematical Figures Using "Mathematica".
• Hassani, Mehdi. "Derangements and Applications". Journal of Integer Sequences (JIS), Volume 6, Issue 1, Article 03.1.2, 2003.
• Weisstein, Eric W. "Derangement". MathWorld–A Wolfram Web Resource.
• בלבול, באתר MathWorld (באנגלית)

הערות שוליים

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

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