בלבול (קומבינטוריקה) – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
הגהה, ניסוח |
מ עריכה |
||
שורה 1:
ב[[קומבינטוריקה]], '''בלבול''' (באנגלית: Derangement) הוא [[תמורה (מתמטיקה)|תמורה]] של איברי [[קבוצה (מתמטיקה)|קבוצה]], כך שאף איבר אינו מופיע במיקומו המקורי.
במילים אחרות, בלבול הוא תמורה שאינה מכילה [[נקודת שבת|נקודות קבועות]].
שורה 5:
הראשון שהתייחס לבעיה של ספירת הבלבולים היה פייר ריימונד דה מונמור<ref>de Montmort, P. R. (1708). </ref>, בשנת 1708; הוא פתר אותה בשנת 1713, בערך באותו זמן שעשה זאת ניקולאס ברנולי.
השאלה האם קבוצת תמורות מכילה בלבולים כלשהם היא בעיית 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>▼
== דוגמה ==
שורה 43 ⟵ 45:
חישוב ''n''! נותן את הנוסחה הבאה:
<math>!n = n! \sum_{i=0}^n \frac{(-1)^i}{i!}.</math>
▲השאלה האם קבוצת תמורות מכילה בלבולים כלשהם היא בעיית 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}}
| |||