Mathematik: Derangement-Zahlen
Released by matroid on Fr. 23. März 2001 14:23:44 [Statistics]
Written by matroid - 4686 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\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}\)

Frage

Folgende 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)

Antwort

Diese 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\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Grundstudium Mathematik :: Kombinatorik :: Stochastik :: Mathematik :
Derangement-Zahlen [von matroid]  
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?
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 4686
 
Aufrufstatistik des Artikels
Insgesamt 568 externe Seitenaufrufe zwischen 2012.01 und 2022.12 [Anzeigen]
DomainAnzahlProz
https://matheplanet.com10.2%0.2 %
http://google.de37766.4%66.4 %
https://google.de10618.7%18.7 %
https://google.com407%7 %
https://www.bing.com101.8%1.8 %
http://suche.t-online.de91.6%1.6 %
https://www.ecosia.org50.9%0.9 %
http://google.com40.7%0.7 %
http://isearch.avg.com40.7%0.7 %
http://www.bing.com30.5%0.5 %
http://google.at20.4%0.4 %
http://de.search.yahoo.com20.4%0.4 %
https://duckduckgo.com10.2%0.2 %
http://search.tb.ask.com10.2%0.2 %
http://r.duckduckgo.com10.2%0.2 %
http://www.matheboard.de10.2%0.2 %
http://www.zahlreich.de10.2%0.2 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 1 Aufruf in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2022.12.03 17:21fav.php?agid=1&keyword=Stochastik&keyword2=Mathematik

Häufige Aufrufer in früheren Monaten
Insgesamt 537 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2012-2014 (139x)http://google.de/url?sa=t&rct=j&q=derangement zahlen
2020-2022 (102x)https://google.de/
2013-2016 (95x)http://google.de/url?sa=t&rct=j&q=
2020-2022 (40x)https://google.com/
201202-02 (37x)http://google.de/url?sa=t&rct=j&q=n besucher hut stochastik
201205-05 (26x)http://google.de/url?sa=t&rct=j&q=n hüte stochastik
201206-06 (25x)http://google.de/url?sa=t&rct=j&q=garderoben problem erwartungswert
2012-2013 (24x)http://google.de/url?sa=t&rct=j&q=Derangement-Zahlen
201207-07 (13x)http://google.de/url?sa=t&rct=j&q=garderobenproblem erwartungswert
2020-2021 (9x)https://www.bing.com/
2012-2016 (7x)http://suche.t-online.de/fast-cgi/tsc?lang=any&dia=suche&pageSection=&searchS...
201405-05 (7x)http://google.de/url?sa=t&source=web&cd=3&ved=0CDMQFjAC
2020-2021 (5x)https://www.ecosia.org/
201705-12 (4x)http://google.de/
202104-04 (4x)https://google.de

[Top of page]

"Mathematik: Derangement-Zahlen" | 0 Comments
The authors of the comments are responsible for the content.

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]