Wahrscheinlichkeit von Surjektionen ?!?!

10.05.2005, 17:58	Asgaroth	Auf diesen Beitrag antworten »
Wahrscheinlichkeit von Surjektionen ?!?! Man bezeichne mit sur(m,n) die Mächtigkeit von Sur(M,N) für \|M\| = m und \|N\| = n. Seien M eine Menge der Grösse m $\begin{eqnarray} n,k \in \mathbb N \end{eqnarray}$ Sei $\begin{eqnarray} \Omega \end{eqnarray}$ = Sur(M,{1,...,n}) , und sei ( $\begin{eqnarray} \Omega \end{eqnarray}$ ,p) der Zufallsraum mit Gleichverteilung. Man berechne die Wahrscheinlichkeit, dass eine Surjektion $\begin{eqnarray} f: M \rightarrow {1,...,n} \end{eqnarray}$ genau k Punkte von M auf 1 abbildet. Hat da irgendjemand ne idee zu? Ich sitz jetzt schon 2h daran und hab aber eigentlich keine Ahnung was ich genau berechnen soll. MfG Asgaroth Vielen Dank schon im voraus für Antworten.
02.06.2005, 10:12	AD	Auf diesen Beitrag antworten »
Spät kommt sie, die Antwort auf deine Anfrage, aber sie kommt: Sei $\begin{eqnarray} \omega\in\Omega \end{eqnarray}$ eine solche Surjektion, dann bezeichne $\begin{eqnarray} X(\omega):=\left\|\omega^{-1}(\{1\})\right\| \end{eqnarray}$ die Anzahl der Punkte aus M, die auf 1 abgebildet werden. X ist eine Zufallsgröße über dem Laplaceschen W-Raum $\begin{eqnarray} (\Omega,\wp(\Omega),P) \end{eqnarray}$ . Zunächst mal muss $\begin{eqnarray} m\geq n \end{eqnarray}$ sein, denn für $\begin{eqnarray} m<n \end{eqnarray}$ gibt es keine solchen surjektiven Abbildungen, d.h. dort ist $\begin{eqnarray} \Omega=\emptyset \end{eqnarray}$ . Ebenfalls aus Gründen der Surjektivität gilt $\begin{eqnarray} P(X>m-n+1)=0 \end{eqnarray}$ , so dass nunmehr nur die Berechnung von $\begin{eqnarray} P(X=k) \end{eqnarray}$ für $\begin{eqnarray} k=1,2,\ldots,m-n+1 \end{eqnarray}$ verbleibt. Für die Mächtigkeit $\begin{eqnarray} \mathrm{sur}(m,n)=\|\Omega\| \end{eqnarray}$ gilt nach Einschluss-Ausschlussformel $\begin{eqnarray} \mathrm{sur}(m,n)= n^m - {n\choose 1}(n-1)^m + {n\choose 2}(n-2)^m - {n\choose 3}(n-3)^m \pm \ldots +(-1)^n {n\choose n}(n-n)^m \end{eqnarray}$ Daraus erhält man dann $\begin{eqnarray} P(X=k)={m \choose k} \frac{\mathrm{sur}(m-k,n-1)}{\mathrm{sur}(m,n)},\qquad k=1,2,\ldots,m-n+1 \end{eqnarray}$ Begründung: Es gibt $\begin{eqnarray} {m \choose k} \end{eqnarray}$ Möglichkeiten für die k-elementige Urbildmenge $\begin{eqnarray} \omega^{-1}(\{1\}) \end{eqnarray}$ . Und die restlichen (m-k) Elemente von M müssen surjektiv auf {2,3,...,n} abgebildet werden.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »