Wahrscheinlichkeit Fixpunkt < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:16 Di 06.11.2007 | | Autor: | trixi86 |
| Aufgabe | | Wie groß ist die Wahrscheinlichkeit, dass eine zufällige Permutation der Menge {1,....,n} mindestens einen Fixpunkt besitzt? |
Also ich hab die Aufgaben folgendermaßen angegangen.
betrachtet man den Grundraum [mm] \Omega=[1,...,n]^{n} [/mm] als die menge aller Permutationen so ist [mm] |\Omega|=n!. [/mm]
Sei [mm] A_{i}={(\omega_{1},....,\omega_{n})\in \Omega :\omega_{i}=i} [/mm] die teilmenge aller Permutationen mit Fixpunkt i.
[mm] \Rightarrow [/mm] das gesuchte Ereignis A (alle Permutationen mit mind einem Fixpunkt) ist die Vereinigung aller [mm] A_{i}
[/mm]
Laut Siebformel kann man doch folgenden Ansatz wählen:
[mm] \mathcal{P}(A) =\summe_{k=1}^{n}(-1)^{k-1} S_{k}
[/mm]
wobei [mm] S_{k}:=\summe_{1\le i_{1}< ...
aber was ich jetzt damit anfangen soll weiß ich nicht genau. steh irgendwie voll auf dem schlauch.
wär lieb wenn mir jemand helfen könnte. danke
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:40 Mi 07.11.2007 | | Autor: | statler |
Guten Morgen!
> Wie groß ist die Wahrscheinlichkeit, dass eine zufällige
> Permutation der Menge {1,....,n} mindestens einen Fixpunkt
> besitzt?
Ist es nicht einfacher, sich Gedanken zur Gegenwahrscheinlichkeit zu machen? Also konkret: Wie viele Permutationen haben keinen Fixpunkt?
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 20:12 Mi 07.11.2007 | | Autor: | trixi86 |
Also erst mal danke für den Tipp, ich glaube jetzt auch dass es einfacher ist mit dem Komplement zu rechnen.Hab jetzt auch einen Ansatz. Bin mir aber nicht sicher ob das schon alles ist oder ob da schon ein Grundlegender Fehler beinhaltet ist.Also
Sei [mm] \Omega= Per_{k}^{n} [/mm] (k-Permutationen aus {1,...,n} mit Wiederholung)
Dann ist das Ereigniss [mm] A=(a_{1},...,a_{n}) \in \Omega [/mm] : es gibt i,j [mm] \in [/mm] {1,...,n} mit [mm] a_{j}=a_{i} [/mm] und i [mm] \not= [/mm] j
Es gilt für die gesuchte Wahrscheinlichkeit
[mm] \mathcal{P}(A)=\bruch{|A|}{| \Omega|}
[/mm]
Außerdem:
[mm] \mathcal{P}(A)= [/mm] 1- [mm] \mathcal{P}(A^{c}) [/mm] =1- [mm] \mathcal{P}( \Omega \backslash [/mm] A) =1- [mm] \mathcal{P}(Per_{k, \not=}^{n}) [/mm] (mit [mm] Per_{k, \not=}^{n}= [/mm] k-Permutationen aus{1,..,n} ohne Wiederholung)
= 1- [mm] \bruch{|Per_{k, \not=}^{n}|}{| \Omega|} [/mm]
Aber jetzt komm ich nicht mehr weiter. was ist denn [mm] |Per_{k, \not=}^{n}|= [/mm] ????
dass | [mm] \Omega [/mm] |= [mm] n^{k} [/mm] weiß ich (oder???)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Fr 09.11.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
