בלבול (קומבינטוריקה) – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
Galabra העביר את הדף בלבול (קומבינטוריקה) לשם בלבול (פסיכולוגיה): כפילות בין שני ערכים |
יצירה באמצעות תרגום הדף "Derangement" |
||
שורה 1:
ב[[קומבינטוריקה]], '''בלבול''' (באנגלית: Derangement) הוא [[תמורה (מתמטיקה)|תמורה]] של איברי [[קבוצה]], כך שאף איבר אינו מופיע במיקומו המקורי.
במילים אחרות, בלבול הוא תמורה שאינה מכילה [[נקודת שבת|נקודות קבועות]].
מספר הבלבולים של קבוצה בגודל ''n'', בדרך כלל נכתב ''D<sub>n</sub>'', ''d,<sub>n</sub>'', או ''n!'', נקרא גם "מספר de Montmort". '''פונקציית הבלבול''' (בשונה מ-n [[עצרת]], ''!n'')שולחת מ-''n'' ל-''n!''.<ref>The name "subfactorial" originates with [//en.wikipedia.org/wiki/William_Allen_Whitworth William Allen Whitworth]; see {{citation|last=Cajori|first=Florian|title=A History of Mathematical Notations: Two Volumes in One|url=https://books.google.com/books?id=gxrO8ZnMK_YC&pg=RA1-PA77|year=2011|authorlink=Florian Cajori|page=77|publisher=Cosimo, Inc.,|isbn=9781616405717}}.</ref> לפונקצייה זו אין סימון מוסכם ולעיתים משתמשים ב-''n''¡ במקום ב-!''n''.<ref>Ronald L. Graham, Donald E. Knuth, Oren Patashnik, ''Concrete Mathematics'' (1994), Addison–Wesley, Reading MA. </ref>
הראשון שהתייחס לבעיה של ספירת הבלבולים היה פייר ריימונד דה מונמור<ref>de Montmort, P. R. (1708). </ref>, בשנת 1708; הוא פתר אותה בשנת 1713, בערך באותו זמן שעשה זאת ניקולאס ברנולי.
== דוגמה ==
[[קובץ:Derangement4.png|ימין|ממוזער|9 בלבולים מוקפים, מתוך 24 תמורות]]
נניח שמורה בוחן 4 תלמידים - A, B, C, ו-D - ורוצה שכל תלמיד יבדוק מבחן של אחד מעמיתיו. כמובן שאף תלמיד לא אמור לבדוק את המבחן של עצמו. בכמה דרכים יכול המורה לחלק את המבחנים לתלמידיו כדי שאלה יבדקו אותם? מתוך 24 תמורות אפשריות (4!) לחלוקת המבחנים:
: {| style="font: 125%/1 monospace; border-collapse: collapse; margin-bottom: 10px;"
|ABCD,
|ABDC,
|.צ. ב.ד,
| - CDB,
| - DBC,
|ADCB,
|-
|BA,CD,
|BADC,
|BCAד,
|BCDA,
|BDAC,
|BDC,
|-
|מוניתD,
|CADB,
|CBAD,
|CBDA,
|CDAB,
|CDBA,
|-
|DABC,
|דהC,B,
|DBAC,
|דלפנה " ס,
|DCAB,
|DCBA.
|}
יש רק 9 בלבולים (מסומנים בכתב כחול נטוי). בשאר התמורות של הקבוצה בת 4 האיברים, לפחות תלמיד אחד מקבל את המבחן שלו בחזרה (מסומנות בכתב אדום מודגש).
גרסה נוספת של הבעיה עוסקת במספר הדרכים להכניס ''n'' מכתבים, שכל אחד מהם ממוען לאדם אחר, ל-''n'' מעטפות שכבר כתובות עליהן כתובות, כך שאף מכתב לא יוכנס למעטפה הנכונה.
== ספירת בלבולים ==
נניח שיש ''n'' אנשים ממוספרים 1, 2, ..., ''n''. וכן ''n'' כובעים ממוספרים 1, 2, ..., ''n''. עלינו למצוא את מספר הדרכים בהן אף אחד לא מקבל את הכובע שממוספר כמוהו. נניח כי האדם הראשון לוקח את הכובע הממוספר ב-''i'', מתוך ''n'' − 1 אפשרויות. כעת יש שתי אפשרויות - תלוי אם האדם ה-''i'' לוקח את כובע מספר 1:
# האדם ה-''i'' לא לוקח את כובע מספר 1. מקרה זה שקול לפתרון הבעיה עם ''n'' − 1 אנשים ו- ''n'' − 1 כובעים: לכל אחד מבין ''n'' − 1 האנשים יש בדיוק בחירה אחת אסורה מבין שאר ''n'' − 1 הכובעים (לאדם ה-''i'' אסור לבחור בכובע 1).
# האדם ה-''i'' לוקח את כובע מספר 1. עכשיו הבעיה מצטמצמת ל-''n'' − 2 אנשים ו- ''n'' − 2 כובעים.
מכאן ניתן להגיע לנוסחה הבאה:
: <math />
כאשר n!, המכונה פונקציית הבלבול, מייצג את מספר הבלבולים, עם תנאי ההתחלה !0 = 1 ו- !1 = 0.
אותה נוסחת נסיגה עובדת גם עבור עצרת, עם תנאי התחלה שונים: 0! = 1, 1! = 1
: <math />
וזה עוזר להוכיח את הגבול עם [[e]] בהמשך.
כמו כן, הנוסחאות להלן ידועות גם כן:<ref>Hassani, M. "Derangements and Applications." </ref>
: <math />
: <math />
כאשר <math /> היא [[פונקציית קיטום|פונקציית הקיטום]] (מעגלת למספר השלם הקרוב) ו <math /> הוא פונקציית הרצפה (מעגלת למספר השלם הנמוך).
: <math />
: <math />
להלן נוסחה נוספת:<ref>See the notes for {{OEIS|id=A000166}}.</ref>
: <math />
החל מ- ''n'' = 0, מספר הבלבולים של ''n'' הם:
: 1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, ... {{OEIS}}.
שיטה ידועה לספירת בלבולים משתמשת ב[[עקרון ההכלה וההפרדה]]: ראשית לספור את כל התמורות, לחסר את אלה שמיקומו של אחד האיברים נשאר בהן קבוע ולבצע תמורות של שאר האיברים, להוסיף בחזרה את התמורות בהן שני איברים שומרים על מיקומם המקורי, וכו'.
: <math />
חישוב ''n''! נותן את הנוסחה הבאה: <math />
[[קובץ:N!_v_!n.svg|ממוזער|300x300 פיקסלים|מספר התמורות והבלבולים של n איברים. הגרף הכחול מייצג את הערך של n עצרת, מספר התמורות, ואילו הגרף האדום מייצג את מספר הבלבולים האפשריים ל-n איברים. כלומר, שאף איבר לא נמצא במקומו המקורי.
{| class="wikitable collapsible collapsed" style="margin: 0px 0px 10px;" width="100%"
! colspan="4" |טבלת ערכים<br>
|-
! <math>n</math>
! nowrap="" | תמורות, <math>n!</math>
! nowrap="" | בלבולים, <math>!n</math>
! <math>\frac{!n}{n!}</math>
|-
| align="center" | 0
| 1
=1×10<sup>0</sup>
| 1
=1×10<sup>0</sup>
| = 1
|-
| align="center" | 1
| 1
=1×10<sup>0</sup>
| 0
| = 0
|-
| align="center" | 2
| 2
=2×10<sup>0</sup>
| 1
=1×10<sup>0</sup>
| = 0.5
|-
| align="center" | 3
| 6
=6×10<sup>0</sup>
| 2
=2×10<sup>0</sup>
| align="right" | ≈0.33333 33333
|-
| align="center" | 4
| 24
=2.4×10<sup>1</sup>
| 9
=9×10<sup>0</sup>
| = 0.375
|- style="border-top: 2px solid rgb(170, 170, 170);"
| align="center" | 5
| 120
=1.20×10<sup>2</sup>
| 44
=4.4×10<sup>1</sup>
| align="right" | ≈0.36666 66667
|-
| align="center" | 6
| 720
=7.20×10<sup>2</sup>
| 265
=2.65×10<sup>2</sup>
| align="right" | ≈0.36805 55556
|-
| align="center" | 7
| 5 040
≈5.04×10<sup>3</sup>
| 1 854
≈1.85×10<sup>3</sup>
| align="right" | ≈0.36785 71429
|-
| align="center" | 8
| 40 320
≈4.03×10<sup>4</sup>
| 14 833
≈1.48×10<sup>4</sup>
| align="right" | ≈0.36788 19444
|-
| align="center" | 9
| 362 880
≈3.63×10<sup>5</sup>
| 133 496
≈1.33×10<sup>5</sup>
| align="right" | ≈0.36787 91887
|- style="border-top: 2px solid rgb(170, 170, 170);"
| align="center" | 10
| 3 628 800
≈3.63×10<sup>6</sup>
| 1 334 961
≈1.33×10<sup>6</sup>
| align="right" | ≈0.36787 94643
|-
| align="center" | 11
| 39 916 800
≈3.99×10<sup>7</sup>
| 14 684 570
≈1.47×10<sup>7</sup>
| align="right" | ≈0.36787 94392
|-
| align="center" | 12
| 479 001 600
≈4.79×10<sup>8</sup>
| 176 214 841
≈1.76×10<sup>8</sup>
| align="right" | ≈0.36787 94413
|-
| align="center" | 13
| 6 227 020 800
≈6.23×10<sup>9</sup>
| 2 290 792 932
≈2.29×10<sup>9</sup>
| align="right" | ≈0.36787 94412
|-
| align="center" | 14
| 87 178 291 200
≈8.72×10<sup>10</sup>
| 32 071 101 049
≈3.21×10<sup>10</sup>
| align="right" | ≈0.36787 94412
|- style="border-top: 2px solid rgb(170, 170, 170);"
| align="center" | 15
| style="font-size: 80%;" | 1 307 674 368 000
≈1.31×10<sup>12</sup>
| style="font-size: 80%;" | 481 066 515 734
≈4.81×10<sup>11</sup>
| align="right" | ≈0.36787 94412
|-
| align="center" | 16
| style="font-size: 80%;" | 20 922 789 888 000
≈2.09×10<sup>13</sup>
| style="font-size: 80%;" | 7 697 064 251 745
≈7.70×10<sup>12</sup>
| align="right" | ≈0.36787 94412
|-
| align="center" | 17
| style="font-size: 80%;" | 355 687 428 096 000
≈3.56×10<sup>14</sup>
| style="font-size: 80%;" | 130 850 092 279 664
≈1.31×10<sup>14</sup>
| align="right" | ≈0.36787 94412
|-
| align="center" | 18
| style="font-size: 80%;" | 6 402 373 705 728 000
≈6.40×10<sup>15</sup>
| style="font-size: 80%;" | 2 355 301 661 033 953
≈2.36×10<sup>15</sup>
| align="right" | ≈0.36787 94412
|-
| align="center" | 19
| style="font-size: 80%;" | 121 645 100 408 832 000
≈1.22×10<sup>17</sup>
| style="font-size: 80%;" | 44 750 731 559 645 106
≈4.48×10<sup>16</sup>
| align="right" | ≈0.36787 94412
|- style="border-top: 2px solid rgb(170, 170, 170);"
| align="center" | 20
| style="font-size: 80%;" | 2 432 902 008 176 640 000
≈2.43×10<sup>18</sup>
| style="font-size: 80%;" | 895 014 631 192 902 121
≈8.95×10<sup>17</sup>
| align="right" | ≈0.36787 94412
|-
| align="center" | 21
| style="font-size: 80%;" | 51 090 942 171 709 440 000
≈5.11×10<sup>19</sup>
| style="font-size: 80%;" | 18 795 307 255 050 944 540
≈1.88×10<sup>19</sup>
| align="right" | ≈0.36787 94412
|-
| align="center" | 22
| style="font-size: 80%;" | 1 124 000 727 777 607 680 000
≈1.12×10<sup>21</sup>
| style="font-size: 80%;" | 413 496 759 611 120 779 881
≈4.13×10<sup>20</sup>
| align="right" | ≈0.36787 94412
|-
| align="center" | 23
| style="font-size: 80%;" | 25 852 016 738 884 976 640 000
≈2.59×10<sup>22</sup>
| style="font-size: 80%;" | 9 510 425 471 055 777 937 262
≈9.51×10<sup>21</sup>
| align="right" | ≈0.36787 94412
|-
| align="center" | 24
| style="font-size: 80%;" | 620 448 401 733 239 439 360 000
≈6.20×10<sup>23</sup>
| style="font-size: 80%;" | 228 250 211 305 338 670 494 289
≈2.28×10<sup>23</sup>
| align="right" | ≈0.36787 94412
|- style="border-top: 2px solid rgb(170, 170, 170);"
| align="center" | 25
| style="font-size: 80%;" | 15 511 210 043 330 985 984 000 000
≈1.55×10<sup>25</sup>
| style="font-size: 80%;" | 5 706 255 282 633 466 762 357 224
≈5.71×10<sup>24</sup>
| align="right" | ≈0.36787 94412
|-
| align="center" | 26
| style="font-size: 80%;" | 403 291 461 126 605 635 584 000 000
≈4.03×10<sup>26</sup>
| style="font-size: 80%;" | 148 362 637 348 470 135 821 287 825
≈1.48×10<sup>26</sup>
| align="right" | ≈0.36787 94412
|-
| align="center" | 27
| style="font-size: 80%;" | 10 888 869 450 418 352 160 768 000 000
≈1.09×10<sup>28</sup>
| style="font-size: 80%;" | 4 005 791 208 408 693 667 174 771 274
≈4.01×10<sup>27</sup>
| align="right" | ≈0.36787 94412
|-
| align="center" | 28
| style="font-size: 80%;" | 304 888 344 611 713 860 501 504 000 000
≈3.05×10<sup>29</sup>
| style="font-size: 80%;" | 112 162 153 835 443 422 680 893 595 673
≈1.12×10<sup>29</sup>
| align="right" | ≈0.36787 94412
|-
| align="center" | 29
| style="font-size: 80%;" | 8 841 761 993 739 701 954 543 616 000 000
≈8.84×10<sup>30</sup>
| style="font-size: 80%;" | 3 252 702 461 227 859 257 745 914 274 516
≈3.25×10<sup>30</sup>
| align="right" | ≈0.36787 94412
|- style="border-top: 2px solid rgb(170, 170, 170);"
| align="center" | 30
| style="font-size: 80%;" | 265 252 859 812 191 058 636 308 480 000 000
≈2.65×10<sup>32</sup>
| style="font-size: 80%;" | 97 581 073 836 835 777 732 377 428 235 481
≈9.76×10<sup>31</sup>
| align="right" | ≈0.36787 94412
|}
]]
== סיבוכיות חישוב ==
השאלה האם קבוצת תמורות מכילה בלבולים כלשהם היא בעיית NP שלמה.<ref>{{citation|last=Lubiw|first=Anna|title=Some NP-complete problems similar to graph isomorphism|year=1981|authorlink=Anna Lubiw|journal=[[SIAM Journal on Computing]]|volume=10|issue=1|pages=11–21|doi=10.1137/0210002|mr=605600}}. </ref>
== הפניות ==
{{Reflist}}
== קישורים חיצוניים ==
* {{Cite web|url=http://math.ucr.edu/home/baez/qg-winter2004/derangement.pdf|title=Let's get deranged!|last=Baez, John|authorlink=John Baez|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=Eric W. Weisstein}}
[[קטגוריה:סדרות של שלמים]]
| |||