5 Briefe-5 Kuverts < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:11 Di 12.07.2005 | | Autor: | umberto |
(Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt,jedoch keine brauchbare Antwort erhalten:
http://matheplanet.com/default3.html?call=viewforum.php?forum=-2&ref=http://www.google.at/search?hlX=de%26qX=mathe+forum%26metaX=)
Ich verzweifle an folgender Aufgabe:
Es gibt 5 Briefe und 5 zugehörige Kuverts. Wieviele Möglichkeiten gibt es , dass kein Brief im richtigen Kuvert landet?
ad Lösung:
Mir ist die Lösung bekannt, auch der Lösungsweg:
5!- [mm] \vektor{5 \\ 1} [/mm] *4!+ [mm] \vektor{5 \\ 2} [/mm] *3!- [mm] \vektor{5 \\ 3} [/mm] *2!+ [mm] \vektor{5 \\ 4} [/mm] *1!-1=44
Mir ist auch klar, dass der zweite Summand für die Möglichkeiten, dass MINDESTENS ein Brief im richtigen Kuvert ist,steht,der dritte für MINDESTENS zwei Briefe im richtigen Kuvert usw...
Auch verstehe ich, dass etwa durch [mm] \vektor{5 \\ 1} [/mm] *4! Fälle mehrfach gezählt werden, die dann anschließend wieder abgezogen werden müssen.
Im Detail hakt es jedoch bei mir, denn:
Ich habe durch Auflistung aller Fälle herausbekommen, dass durch Berechnung von [mm] \vektor{5 \\ 1} [/mm] *4!
....der Fall, dass genau drei Briefe im richtigen Kuvert landen, 21 mal zu oft gezählt wird
...der Fall, dass genau zwei Briefe im richtigen Kuvert landen, 19 mal zu oft gezählt wird
...dass genau ein Brief im richtigen Kuvert landet, 4 mal zu oft gezählt wird
Fürs erste würde ich gerne wissen, ob diese Zahlen stimmen (was ich nicht glaube) , bzw. wie man einfacher darauf kommt, was wie oft zu viel gezählt wurde.
Vielen Dank für eure Hilfe
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:51 Di 12.07.2005 | | Autor: | Stefan |
Hallo!
Du hast dich vertan!
Die Fälle, wo genau zwei Briefe im gleichen Kuvert stecken, werden $20$ mal zu oft gewählt.
Denn es gibt ${5 [mm] \choose [/mm] 2}=10$ solche Paare, die fest bleiben. Jedes Paar wird ja doppelt gezählt, und zwar so oft, wie dieses Paar (mit keinen weiteren Fixpunkten) vorkommt. Nun gibt es aber $2$ fixpunktfreie Permutationen einer dreielementigen Menge.
Die Fälle, wo genau drei Briefe im gleichen Kuvert stecken, werden ebenfalls $20$ mal zu oft gewählt.
Denn es gibt ${5 [mm] \choose [/mm] 3}=10$ solche Tripel, die fest bleiben. Jedes solche Tripel wird ja dreifach gezählt (also zweimal zu viel!) und zwar so oft, wie dieses Tripel (mit keinen weiteren Fixpunkten) vorkommt. Nun gibt es aber nur eine fixpunktfreie Permutation einer zweielementigen Menge.
Der letzte Fall ist trivial: Offenbar werden die Quintupel, die fest bleiben, viermal zu oft gezählt. Dafür braucht man keine kombinatorischen Überlegungen. 
Insgesamt werden also zu Beginn $20+20+4=44$ Fälle zu oft abgezogen, die dann anschließend wieder addiert werden. Da der Wert nach dem ersten Abziehen $0$ beträgt, muss er somit am Ende $44$ betragen.
Viele Grüße
Stefan
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:48 Di 12.07.2005 | | Autor: | umberto |
Vielen Dank für meine Antwort!
Ich kann deine Erklärung gut nachvollziehen.
Das heißt, eigentlich wäre ich an dieser Stelle fertig, denn es gilt "Anzahl der Möglichkeiten, dass kein Brief im richtigen Kuvert"=120 Möglichkeiten minus "Anzahl der Möglichkeiten, dass mind. 1 Brief im richtigen Kuvert (ohne Wiederholungen)"=120-66=44
Ich kapiere jedoch nicht, wie hier die Siebformel (ich kenne sie unter dem Namen Ein- und Ausschaltformel) Verwendung findet.
Es gilt P(A [mm] \cup [/mm] B)=P(A)+P(B)-P(A [mm] \cap [/mm] B) für zwei Mengen A und B, ich weiß auch, wie die Formel für mehrere Mengen funktioniert, aber ich verstehe nicht, was in meinem Beispiel diese Mengen sein sollen.
Denn: Ich habe ja nicht bloß das Problem, dass die Menge ("mind. 1 Brief richtig") auch 2 Briefe richtig, 3 Briefe richtig, 4 Briefe richtig enthält, sondern dass etwa die Formel [mm] \vektor{5\\ 1} [/mm] *4! bereits zu viel zählt (Anzahl Möglichkeiten "mind. 1 Brief richtig" ist ja nicht [mm] \vektor{5\\ 1} [/mm] *4! sondern [mm] \vektor{5\\ 1} [/mm] *4!-44)
Es wäre sehr nett, könntest du mir erklären, wie die in meinem 1. Posting ganz zu Beginn erwähnte Lösung begründet wird.
Vielen herzlichen Dank!!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:25 Di 12.07.2005 | | Autor: | Stefan |
Hallo umberto!
Die Siebformel für Mächtigkeiten lautet allgemein:
[mm] $\left\vert \bigcup\limits_{j=1}^n A_j \right\vert [/mm] = [mm] \sum\limits_{r=1}^n (-1)^{r-1} \cdot \sum\limits_{1\le i_1 < \ldots < i_r \le n} \left\vert A_{i_1} \cap \ldots \cap A_{i_r} \right\vert$.
[/mm]
Ein wichtiger Spezialfall der Siebformel (der hier auch greift) ergibt sich, wenn für jedes $r$ mit $1 [mm] \le [/mm] r [mm] \le [/mm] n$ und jede Wahl von [mm] $i_1,i_2,\ldots,i_r$ [/mm] mit $1 [mm] \le i_1 [/mm] < [mm] \ldots [/mm] < [mm] i_r \le [/mm] n$ die Mächtigkeit des Durchschnittes [mm] $A_{i_1} \cap \ldots \cap A_{i_r}$ [/mm] nur von der Anzahl $r$, aber nicht von der speziellen Wahl der Ereignisse [mm] $A_{i_1},\ldots,A_{i_r}$ [/mm] aus [mm] $A_1,\ldots,A_n$ [/mm] abhängt. In diesem speziellen Fall gilt hier:
[mm] $\left\vert \bigcup\limits_{j=1}^n A_j \right\vert [/mm] = [mm] \sum\limits_{r=1}^n (-1)^{r-1} [/mm] {n [mm] \choose [/mm] r} [mm] \cdot \left\vert A_1 \cap \ldots \cap A_r \right\vert$.
[/mm]
Wie sieht es bei uns aus?
Es sei [mm] $A_j$ [/mm] die Menge aller Permutationen aus [mm] $S_5$, [/mm] die mindestens das Element $j$ festhalten, für $j=1,2,3,4,5$, d.h. es gilt:
[mm] $A_j:=\{(a_1,a_2,a_3,a_4,a_5) \in S_5\, : \, a_j=j\}$.
[/mm]
Dann ist [mm] $\bigcup\limits_{j=1}^5 A_j=A_1 \cup A_2 \cup A_3 \cup A_4 \cup A_5$ [/mm] die Menge aller Permutationen, die mindestens einen Fixpunkt haben; also gerade das Komplement der gesuchten Menge.
Nach der obigen Siebformel gilt mit $n=5$:
[mm] $|A_1 \cup A_2 \cup A_3 \cup A_4 \cup A_4| [/mm] = {5 [mm] \choose [/mm] 1} [mm] \cdot |A_1| [/mm] - {5 [mm] \choose [/mm] 2} [mm] \cdot |A_1 \cap A_2| [/mm] + {5 [mm] \choose [/mm] 3} [mm] \cdot |A_1 \cap A_2 \cap A_3| [/mm] - {5 [mm] \choose [/mm] 4} [mm] \cdot |A_1 \cap A_2 \cap A_3 \cap A_4| [/mm] + {5 [mm] \choose [/mm] 5} [mm] \cdot |A_1 \cap A_2 \cap A_3 \cap A_4 \cap A_5|$.
[/mm]
Nun ist für alle [mm] $r\in \{1,2,3,4,5\}$ [/mm] gerade:
[mm] $|A_1 \cap \ldots \cap A_r| [/mm] = (5-r)!$,
denn während ja die Elemente [mm] $1,\ldots,r$ [/mm] festbleiben, können die Elemente [mm] $r+1,\ldots,5$ [/mm] (dies sind $5-r$ Stück) beliebig permutieren.
Daraus folgt insgesamt die Behauptung. 
Viele Grüße
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:54 Di 12.07.2005 | | Autor: | umberto |
Ich glaube jetzt hab ich kapiert. Vielen herzlichen Dank für dein Mühe.
Liebe Grüße,
Umberto
|
|
|
|
