 \(\begingroup\)\(\newcommand{\IX}{\mathbb{X}}
\newcommand{\IW}{\mathbb{M}}
\newcommand{\politician}[1]{\text{Ich habe die Frage nicht verstanden. #1}}
\newcommand{\ba}{\begin{aligned}}
\newcommand{\ea}{\end{aligned}}
\newcommand{\bpm}{\begin{pmatrix}}
\newcommand{\epm}{\end{pmatrix}}
\newcommand{\bc}{\begin{cases}}
\newcommand{\ec}{\end{cases}}
\newcommand{\on}{\operatorname}
\newcommand{\ds}{\displaystyle}\)
FrageFolgende Frage erreicht mich vor einiger Zeit: Unser Lehrer hat heut gemeint, er wettet dass niemand hinter eine Formel zu folgendem Sachverhalt kommt. Also angenommen man hat 4 beschriftete Umschläge, und dazu 4 passende Briefe.
Wie hoch ist die Wahrscheinlichkeit wenn man die Briefe in die Umschläge tut, dass KEINER im richtigen Umschlag ist. Kennt jemand die Aufgabe vielleicht und kann mir da ne allgemeine Formel sagen, mit der man die Wahrscheinlichkeit sofort berechnen kann? (schätze mal ist ziemlich kompliziert) AntwortDiese Zahlen heißen Derangement-Zahlen - zu deutsch etwa "Unordnungs-Zahlen", denn sie zählen die Möglichkeiten für komplette Unordnung (Niemand bekommt seinen Hut!). Weiterführende Links dazu sind in der Datenbank (Mathematik-Kombinatorik)
Folgender Text ist eine Übersetzung aus dem englischen. Original-Artikel von David Karr.
An einer Garderobe haben n Personen ihre Hüte abgegeben. Nach der Veranstaltung werden die Hüte wieder ausgeteilt.
Wieviele Möglichkeiten gibt es, die Hüte so auszuteilen, daß niemand seinen eigenen Hut erhält?
Zunächst zählen wir alle möglichen Verteilungen. Dann subtrahieren wir die Möglichkeiten, bei denen eine Personen tatsächlich den eigenen Hut in der Hand hat. Damit zählen wir aber alle Möglichkeiten doppelt, bei denen zwei Personen den richtigen Hut haben, also müssen wir die dafür die Anzahl wieder zu addieren. Aber nun haben wir alle Möglichkeiten mit drei richtig ausgeteilten Hüten doppelt gezählt, und wir müssen deren Anzahl subtrahieren. Jetzt das gleiche Argument für 4.richtig-ausgeteilte-Hüte usw. Wir müssen abwechselnd addieren und subtrahieren, solange bis wir bei n angelangt sind.Drücken wir es jetzt mal mit Wahrscheinlichkeiten aus: Die Wahrscheinlicheit der Gesamtmenge ist 1. Für eine gegebene Teilmenge von k Personen ist die Wahrscheinlichkeit, daß diese k Personen den eigenen Hut erhalten, gleich (n-k)!/n! , und außerdem gibt es (n;k) Auswahlen von k aus n Personen. Darum ist (n;k)*(n-k)!/n! = n!/((n-k)!*k!)*(n-k)!/n! = 1/k! die Gesamtwahrscheinlichkeit, daß genau (beliebige) k Personen den eigenen Hut erhalten.Die gesuchte Wahrscheinlichkeit kann nun als endliche Summe angegeben werden: 1 - 1/1! + 1/2! - 1/3! + ... +- 1/n! Das sind aber genau die ersten n+1 Terme der Taylor-Reihe von f(x) = ex um x0 an x= -1. Diese Reihe konvergiert sehr schnell gegen 1/e.
Man kann die exakte Wahrscheinlichkeit für jedes n >= 1 einfach durch Rundung von n!/e zur nächsten ganzen Zahl und anschließende Division wieder durch n! angeben.
Übrigens mir scheint, daß für ungerade n immer abgerundet und für gerade n immer aufgerundet wird.Zum Beispiel, 12!/e = 176214840.95798... weicht absolut nur 0.05 vom korrekten Ergebnis 176214841 ab.
[Ende der Übersetzung]
Mit Dn bezeichnet man die n-te Derangement-Zahl.
Es ist D2=1, denn es gibt nur eine Möglichkeit die Hüte von zwei Personen falsch auszuteilen. D3 ist 2, D4 ist 9.
Dann wachsen die Zahlen sehr schnell. D12 ist 176214841 und D16 ist 7.697.064.251.745.
\(\endgroup\)
| 
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
Printer-friendly version
Get link to this article
Comments
Für diesen Artikel gibt es keine pdf-Datei
Dieser Artikel ist im Verzeichnis der 
