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

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

מספר הבלבולים של קבוצה בגודל ${\displaystyle n}$, בדרך כלל נכתב בתור ${\displaystyle !n}$‏, ${\displaystyle D_{n}}$‏, ${\displaystyle d_{n}}$‏ או n¡.

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

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

דוגמה

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

נניח שמורה בוחן 4 תלמידים ${\displaystyle A,B,C,D}$ ורוצה שכל תלמיד יבדוק מבחן של אחד מעמיתיו, כאשר אף תלמיד לא יבדוק את המבחן של עצמו. בכמה דרכים יכול המורה לחלק את המבחנים לתלמידיו כדי שאלה יבדקו אותם? מתוך 24 = !4 תמורות אפשריות לחלוקת המבחנים:

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

גרסאות נוספות של הבעיה הן שליחת ${\displaystyle n}$ מכתבים ממוענים כך שאף מכתב לא יגיע לכתובתו הנכונה, או בעיית האנשים והכובעים להלן.

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

הגרף הכחול הוא מספר התמורות, והגרף האדום הוא מספר הבלבולים האפשריים ל-${\displaystyle n}$ איברים. כלומר, שאף איבר לא נמצא במקומו המקורי.

טבלת ערכים
${\displaystyle n}$	תמורות (${\displaystyle n!}$)	בלבולים (${\displaystyle !n}$)	${\displaystyle {\frac {!n}{n!}}}$
0	1	1	1
1	1	0	0
2	2	1	0.5
3	6	2	1/3
4	24	9	0.375
5	120	44	11/30
6	720	265	≈ 0.3680555
7	5,040	1854	≈ 0.367857142
8	40,320	14833	≈ 0.367881944
9	362880	133496	≈ 0.3678791887
10	3628800	1334961	≈ 0.3678794643
11	39916800	14684570	≈ 0.3678794392
12	479001600	176214841	≈ 0.3678794413
13	6227020800	2290792932	≈ 0.3678794412
14	87178291200	32071101049	≈ 0.3678794412
15	1307674368000	481066515734	≈ 0.3678794412
16	20922789888000	7697064251745	≈ 0.3678794412
17	355687428096000	130850092279664	≈ 0.3678794412

נתונים ${\displaystyle n}$ אנשים ממוספרים ${\displaystyle 1,\ldots ,n}$ בעלי כובעים ממוספרים ${\displaystyle a_{1},\ldots ,a_{n}}$ בהתאמה. עלינו למצוא את מספר הדרכים בהן איש לא יקבל את כובעו שלו.

נניח כי ${\displaystyle a_{1}=k}$ מתוך ${\displaystyle n-1}$ אפשרויות. כעת יש שתי אפשרויות:

1. אם ${\displaystyle a_{k}=1}$ אזי הבעיה מצטמצמת ל-${\displaystyle n-2}$ אנשים ו-${\displaystyle n-2}$ כובעים.
2. אם ${\displaystyle a_{k}\neq 1}$ אזי הבעיה מצטמצמת ל-${\displaystyle n-1}$ אנשים ו-${\displaystyle n-1}$ כובעים.

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

${\displaystyle {\begin{aligned}&!n=(n-1){\bigl (}!(n-1)\,+\,!(n-2){\bigr )}\\&!0=1,\,!1=0\end{aligned}}}$

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

${\displaystyle {\begin{aligned}&n!=(n-1){\bigl (}(n-1)!+(n-2)!{\bigr )}\\&0!=1!=1\end{aligned}}}$

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

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

${\displaystyle !n=n!\sum _{i\,=\,0}^{n}{\frac {(-1)^{i}}{i!}}=\left[{\frac {n!}{e}}\right]=\left\lfloor {\frac {n!}{e}}+{\frac {1}{2}}\right\rfloor ,\quad n\geq 1}$

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

${\displaystyle {\begin{aligned}!n&={\bigl \lfloor }(e+e^{-1})n!{\bigr \rfloor }-\lfloor en!\rfloor ,\quad n\geq 2\\&=n!-\sum _{i\,=\,1}^{n}{\binom {n}{i}}\cdot !(n-i)\end{aligned}}}$

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

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

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

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

${\displaystyle {\begin{aligned}!n&=n!-{\binom {n}{1}}(n-1)!+{\binom {n}{2}}(n-2)!-\cdots (-1)^{n}{\binom {n}{n}}0!\\&=\sum _{i\,=\,0}^{n}(-1)^{i}{\binom {n}{i}}(n-i)!\\&=n!\sum _{i\,=\,0}^{n}{\frac {(-1)^{i}}{i!}}\end{aligned}}}$

לכן ההסתברות שתמורה אקראית תהיה בלבול היא ${\displaystyle {\frac {!n}{n!}}}$, וזהו טור טיילור של הפונקציה ${\displaystyle e^{\pm x}}$ בנקודה ${\displaystyle x=\mp 1}$ וערכו בגבול הוא ${\displaystyle {\frac {1}{e}}}$.

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

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

${\displaystyle D_{n,k}={\binom {n}{k}}\cdot D_{n-k,0}={\binom {n}{k}}\cdot !(n-k)}$

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

${\displaystyle D_{n,k}\cdot \sum _{i\,=\,0}^{n-k}{\frac {(-1)^{i}}{i!}}={\binom {n}{k}}\cdot D_{n-k,0}\cdot \sum _{i\,=\,0}^{n-k}{\frac {(-1)^{i}}{i!}}={\binom {n}{k}}\cdot !(n-k)\cdot \sum _{i\,=\,0}^{n-k}{\frac {(-1)^{i}}{i!}}}$

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

• 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 (באנגלית)

הערות שוליים

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, doi:10.1137/0210002, MR 0605600.
3. Hassani, M. "Derangements and Applications."
4. ראו הערה בסדרה A000166 באתר OEIS – האנציקלופדיה המקוונת לסדרות של מספרים שלמים.