Anzahl Permutationen mit mindestens einem Fixpunkt: Denkfehler finden

28.11.2018, 23:35	fehlermacher44	Auf diesen Beitrag antworten »
Anzahl Permutationen mit mindestens einem Fixpunkt: Denkfehler finden Ich habe mir bei dem obigen Problem folgendes gedacht: Man hat eine Menge von $\begin{eqnarray} n \end{eqnarray}$ Elementen. Um sicherzustellen, dass es mindestens einen Fixpunkt gibt, wählt man einfach ein Element aus und weist ihm sich selbst zu. Dafür gibt es $\begin{eqnarray} \binom{n}{1} = n \end{eqnarray}$ Möglichkeiten. Nun bleiben noch $\begin{eqnarray} n-1 \end{eqnarray}$ Elemente übrig. Diese kann man zuordnen wie man will; es ist fast wie eine ganz eigene Permutation, da das eine Element ja komplett fertig ist und keinen Einfluss mehr auf den weiteren Prozess nimmt. Für die Permutation von $\begin{eqnarray} n-1 \end{eqnarray}$ Elementen gibt es $\begin{eqnarray} (n-1)! \end{eqnarray}$ Möglichkeiten. Nach Produktregel macht das insgesamt $\begin{eqnarray} n (n-1)! = n! \end{eqnarray}$ Möglichkeiten. Das kann aber gar nicht sein, denn $\begin{eqnarray} n! \end{eqnarray}$ ist ja schon die Gesamtanzahl an möglichen Permutationen für eine Menge von $\begin{eqnarray} n \end{eqnarray*}$ Elementen. Wo liegt also mein Fehler?
29.11.2018, 08:46	10001000Nick1	Auf diesen Beitrag antworten »
Das Problem ist, dass du alle Permutationen mit mehr als einem Fixpunkt mehrfach zählst. Nehmen wir z.B. die Permutation, die jedes Element auf sich selbst abbildet. Dann ist 1 ein Fixpunkt; und bei der Permutation der restlichen n-1 Elemente ist diese identische Permutation dabei. Dann ist aber auch 2 ein Fixpunkt. Wenn man dann die restlichen n-1 Elemente permutiert, erhält man irgendwann wieder die identische Permutation, die man aber schon gezählt hat. Ich würde die Siebformel auf die Mengen $\begin{eqnarray} A_i := \{ \pi\in S_n \mid \pi(i)=i \}, 1\leq i\leq n, \end{eqnarray}$ anwenden. ( $\begin{eqnarray} A_i \end{eqnarray}$ ist also die Menge aller Permutationen mit Fixpunkt $\begin{eqnarray} i \end{eqnarray}$ .)
29.11.2018, 10:13	HAL 9000	Auf diesen Beitrag antworten »
@fehlermacher44 Genauso ist es, d.h. der von dir ermittelte Wert $\begin{eqnarray} n! \end{eqnarray}$ ist die Gesamtanzahl aller Fixpunkte gezählt über alle Permutationen. Im Laplaceschen Wahrscheinlichkeitsraum aller Permutationen hat damit die Zufallsgröße $\begin{eqnarray} X \end{eqnarray}$ ... Anzahl der Fixpunkte den Erwartungswert $\begin{eqnarray} E(X)=1 \end{eqnarray}$ . Was du suchst ist aber $\begin{eqnarray} P(X>0) \end{eqnarray}$ , bzw. zunächst mal die Anzahl der Permutationen, die zu diesem Ereignis $\begin{eqnarray} X>0 \end{eqnarray}$ gehören. Insgesamt ist diese Situation als "Wichtelproblem" bekannt, und schlägt regelmäßig in der Vorweihnachtszeit auf. Wie man es bewältigen kann, hat 10001000Nick1 ja schon im Grundsatz skizziert.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »