הצגת המקור של הדף "בלבול (קומבינטוריקה)"

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

מספר הבלבולים של קבוצה בגודל <math>n</math>, בדרך כלל נכתב בתור <math>!n</math>{{כ}}, <math>D_n</math>{{כ}}, <math>d_n</math>{{כ}} או n¡.

הראשון שהתייחס לבעיה של ספירת הבלבולים היה [[פייר ריימונד דה מונמור]] {{אנ|Pierre Raymond de Montmort}},{{הערה|de Montmort, P. R. (1708).}} בשנת 1708; הוא פתר אותה בשנת 1713, בערך באותו זמן שעשה זאת [[ניקולאס ברנולי]] {{אנ|Nicolaus I Bernoulli}}.

השאלה האם [[חבורת תמורות]] (הנתונה על ידי קבוצת יוצרים) מכילה בלבולים כלשהם היא [[NP (מחלקת סיבוכיות)|בעיית NP שלמה]].{{הערה|{{citation|last=Lubiw|first=Anna|title=Some NP-complete problems similar to graph isomorphism|year=1981|authorlink=|journal=[[SIAM Journal on Computing]]|volume=10|issue=1|pages=11–21|doi=10.1137/0210002|mr=605600}}.  }}

==דוגמה==
[[קובץ:דוגמה לבלבול.png|ממוזער|מתוך כל התמורות של הקבוצה {A,B,C,D} יש רק 9 בלבולים (מסומנים בכתב כחול נטוי). בשאר התמורות של הקבוצה בת 4 האיברים, לפחות תלמיד אחד מקבל את המבחן שלו בחזרה (מסומנות בכתב אדום מודגש).]]
נניח שמורה בוחן 4 תלמידים <math>A,B,C,D</math> ורוצה שכל תלמיד יבדוק מבחן של אחד מעמיתיו, כאשר אף תלמיד לא יבדוק את המבחן של עצמו. בכמה דרכים יכול המורה לחלק את המבחנים לתלמידיו כדי שאלה יבדקו אותם? מתוך 24 = !4 תמורות אפשריות לחלוקת המבחנים:

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

גרסאות נוספות של הבעיה הן שליחת <math>n</math> מכתבים ממוענים כך שאף מכתב לא יגיע לכתובתו הנכונה, או בעיית האנשים והכובעים להלן.

==ספירת בלבולים==
[[קובץ:N!_v_!n.svg|ממוזער|300x300 פיקסלים|הגרף הכחול הוא מספר התמורות, והגרף האדום הוא מספר הבלבולים האפשריים ל-<math>n</math> איברים. כלומר, שאף איבר לא נמצא במקומו המקורי.
{|class="wikitable collapsible collapsed" style="text-align:center; margin:0;" width="100%"
!colspan=4| טבלת ערכים
|-
! <math>n</math>
!nowrap| תמורות (<math>n!</math>)
!nowrap| בלבולים (<math>!n</math>)
! <math>\frac{!n}{n!}</math>
|-
| 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
|style=font-size:80%| ≈ 0.367857142
|-
| 8
| 40,320
| 14833
|style=font-size:80%| ≈ 0.367881944
|-
| 9
| 362880
| 133496
|style=font-size:80%| ≈ 0.3678791887
|-
| 10
| 3628800
| 1334961
|style=font-size:80%| ≈ 0.3678794643
|-
| 11
| 39916800
| 14684570
|style=font-size:80%| ≈ 0.3678794392
|-
| 12
| 479001600
| 176214841
|style=font-size:80%| ≈ 0.3678794413
|-
| 13
|style=font-size:80%| 6227020800
|style=font-size:80%| 2290792932
|style=font-size:80%| ≈ 0.3678794412
|-
| 14
|style=font-size:80%| 87178291200
|style=font-size:80%| 32071101049
|style=font-size:80%| ≈ 0.3678794412
|-
| 15
|style=font-size:80%| 1307674368000
|style=font-size:80%| 481066515734
|style=font-size:80%| ≈ 0.3678794412
|-
| 16
|style=font-size:80%| 20922789888000
|style=font-size:80%| 7697064251745
|style=font-size:80%| ≈ 0.3678794412
|-
| 17
|style=font-size:80%| 355687428096000
|style=font-size:80%| 130850092279664
|style=font-size:80%| ≈ 0.3678794412
|}]]

נתונים <math>n</math> אנשים ממוספרים <math>1,\ldots,n</math> בעלי כובעים ממוספרים <math>a_1,\ldots,a_n</math> בהתאמה. עלינו למצוא את מספר הדרכים בהן איש לא יקבל את כובעו שלו.

נניח כי <math>a_1=k</math> מתוך <math>n-1</math> אפשרויות. כעת יש שתי אפשרויות:
#אם <math>a_k=1</math> אזי הבעיה מצטמצמת ל-<math>n-2</math> אנשים ו-<math>n-2</math> כובעים.
#אם <math>a_k\ne1</math> אזי הבעיה מצטמצמת ל-<math>n-1</math> אנשים ו-<math>n-1</math> כובעים.
מכאן ניתן להגיע לנוסחה הבאה:
:<math>\begin{align}&!n=(n-1)\bigl(!(n-1)\,+\,!(n-2)\bigr)\\&!0=1,\,!1=0\end{align}</math>
אותה נוסחת נסיגה פועלת גם עבור עצרת, עם תנאי התחלה שונים:
:<math>\begin{align}&n!=(n-1)\bigl((n-1)!+(n-2)!\bigr)\\&0!=1!=1\end{align}</math>
וזה עוזר להוכיח את הגבול עם [[e (קבוע מתמטי)|e]] בהמשך.

כמו כן, הנוסחאות להלן ידועות גם כן:{{הערה|Hassani, M. "Derangements and Applications." }}
:<math>!n=n!\sum_{i\,=\,0}^n\frac{(-1)^i}{i!}=\left[\frac{n!}{e}\right]=\left\lfloor\frac{n!}{e}+\frac12\right\rfloor,\quad n\ge1</math>
כאשר <math>[x]</math> היא [[פונקציית קיטום|פונקציית הקיטום]] (מעגלת למספר השלם הקרוב) ו-<math>\lfloor x\rfloor</math> היא [[פונקציית הערך השלם|פונקציית הרצפה]] (מעגלת למספר השלם הנמוך).
:<math>\begin{align}!n&=\bigl\lfloor(e+e^{-1})n!\bigr\rfloor-\lfloor en!\rfloor,\quad n\ge2\\&=n!-\sum_{i\,=\,1}^n\binom{n}{i}\cdot!(n-i)\end{align}</math>
להלן נוסחה נוספת:{{הערה|ראו הערה ב{{OEIS|A000166}}.}}
:<math>!n=n[!(n-1)]+(-1)^n</math>
ראו טבלה משמאל עבור ערכי ה[[סדרה (מתמטיקה)|סדרה]] [[oeis:A000166|A000166]] ב־[[האנציקלופדיה המקוונת לסדרות של מספרים שלמים|OEIS]].

שיטה ידועה לספירת בלבולים משתמשת ב[[עקרון ההכלה וההפרדה]]: ראשית לספור את כל התמורות, לחסר את אלה שמיקום אחד האיברים נשאר בהן קבוע ולבצע תמורות של שאר האיברים, להוסיף בחזרה את התמורות בהן שני איברים שומרים על מיקומם המקורי וכדומה.
:<math>\begin{align}!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{align}</math>
לכן ה[[הסתברות]] שתמורה אקראית תהיה בלבול היא <math>\frac{!n}{n!}</math>, וזהו [[טור טיילור]] של הפונקציה <math>e^{\pm x}</math> בנקודה <math>x=\mp1</math> וערכו בגבול הוא <math>\frac{1}{e}</math>.

==תמורות עם נקודות שבת==
מספר התמורות האפשריות בגודל <math>n</math> עם לפחות <math>k</math> נקודות שבת ניתן בנוסחה:
:<math>D_{n,k}=\binom{n}{k}\cdot D_{n-k,0}=\binom{n}{k}\cdot!(n-k)</math>
מספר התמורות האפשריות בגודל <math>n</math> עם <math>k</math> נקודות שבת ניתן בנוסחה:
:<math>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!}</math>

==קישורים חיצוניים==
<div class="mw-content-ltr">
*{{Cite web|url=http://math.ucr.edu/home/baez/qg-winter2004/derangement.pdf|title=Let's get deranged!|last=Baez, John|authorlink=|year=2003}}
*{{Cite web|url=http://www.math.dartmouth.edu/~doyle/docs/menage/menage/menage.html|title=Non-sexist solution of the ménage problem|last=Bogart, Kenneth P.|last2=Doyle, Peter G.|year=1985}}
*{{Cite web|url=http://mathforum.org/advanced/robertd/derangements.html|title=Derangement diagrams|website=Mathematical Figures Using "Mathematica"|last=Dickau, Robert M.}}
*{{Cite web|url=http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Hassani/hassani5.html|title=Derangements and Applications|publisher=Journal of Integer Sequences (JIS), Volume 6, Issue 1, Article 03.1.2, 2003|last=Hassani, Mehdi}}
*{{Cite web|url=http://mathworld.wolfram.com/Derangement.html|title=Derangement|publisher=MathWorld–A Wolfram Web Resource|last=Weisstein, Eric W|authorlink=}}
*{{MathWorld}}</div>

==הערות שוליים==
<div class="mw-content-ltr">{{הערות שוליים}}</div>

[[קטגוריה:ערכים שבהם תבנית בריטניקה אינה מתאימה]]
[[קטגוריה:קומבינטוריקה]]
[[קטגוריה:סדרות של שלמים]]