Diskrete Wahrscheinlichkeitsrä < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:08 Sa 26.10.2013 | | Autor: | Nadia.. |
| Aufgabe | Sei $ [mm] \Omega= \Omega^{n,n}_{II}$ [/mm] die Menge aller Permutation der Zahlen $1,.....,n.$ Für $1 [mm] \le [/mm] i < j [mm] \le [/mm] n $ sagen wir $ [mm] \omega \in \Omega$ [/mm] weist eine $i-j$ - Transposition auf, wenn gilt [mm] $\omega_i [/mm] = j$ und [mm] $\omega_j= [/mm] i$ und bezeichnen [mm] $A_{(i,j)}$ [/mm] die Menge der Permutationen, die eine solche Transpositionen aufweisen.
a)
Sei $I = [mm] \{ {(i,j) :1 \le i< j \le n} \}$ [/mm] und $J [mm] \subset [/mm] I$ mit Card $J = l [mm] \in \{1,.... \bruch{n(n-1)}{2} \}$
[/mm]
Definiere [mm] $A_J [/mm] = [mm] \bigcap_{i,j \in J}^{n} A_{i,j} [/mm] $
Beschreiben sie die Teilmengen $J$, für die gilt [mm] $A_J \not= \emptyset [/mm] $ Bestimmen Sie für solche Indexmengen [mm] $cardA_J$ [/mm] in Abhängigkeit von $l$
b.
Wie viele Teilmengen $ J [mm] \subset [/mm] I $ gibt es mit $card J = l$ und [mm] $A_J \not= \emptyset$ [/mm] ?
c.Bestimmen Sie die Wahrscheinlichkeit dafür, dass eine zufällig gewählte Permutation [mm] $\omega \in \Omega$
[/mm]
,
wobei alle Permutationen als gleich wahrscheinlich angenommen werden, mindestens eine Transposition
aufweist. Wie verhält sich diese Wahrscheinlichkeit für $n [mm] \to \infty [/mm] $
Danke und viele Grüße im voraus |
Hallo zusammen.
Zu a.
Die Teilmenge $J$ habe ich wie folgt beschrieben:
$ J = [mm] \{(i,j) : 1 \le i< j \le \bruch{n(n-1)}{2} \} [/mm] $. Ich weiß aber nicht, ob das stimmt.
Ich kann den Bezug [mm] $A_J \not= \emptyset$ [/mm] keinem Zusammenhang ordnen.
Wie bestimme ich [mm] $cardA_J$ [/mm] ?
Zu b)
Ist die Anzahl der Teilmengen $ cardI $ ?
Zu c)
Es fällt mir keine Idee ein.
|
|
| |
|
> Sei [mm]\Omega= \Omega^{n,n}_{II}[/mm] die Menge aller Permutation
> der Zahlen [mm]1,.....,n.[/mm] Für [mm]1 \le i < j \le n[/mm] sagen wir
> [mm]\Omega[/mm] weist eine [mm]i-j[/mm] - Transposition auf, wenn gilt
> [mm]\omega_i = j[/mm] und [mm]\omega_j= i[/mm] und bezeichnen [mm]A_{i,j}[/mm] die
> Menge der Permutationen, die eine solche Transpositionen
> aufweisen.
>
> a)
>
> Sei [mm]I = \{ {(i,j) :1 \le i< J \le n} \}[/mm] und [mm]J \subset I[/mm] mit
> Card [mm]J = I \in \{1,....n (n-1)/2 \}[/mm]
> Definiere [mm]A_J = \bigcap_{i,j \in J}^{n} A_{i,j}[/mm]
>
> Beschreiben sie die Teilmenge [mm]J[/mm], für die gilt [mm]A_J \not= \emptyset[/mm]
> Bestimmen Sie für solche Indexmengen [mm]cardA_J[/mm] in
> Abhängigkeit von [mm]l[/mm]
Guten Abend Nadia..
ich sehe da vor allem ein ziemlich schlimmes
Bezeichnungs-Durcheinander, vor allem in Bezug
auf klein und groß geschriebene i, I, j, J .
In der hier vorliegenden Version wird kaum
jemand daraus klug werden.
Schau dir also bitte das Ganze exakt durch und
verwende allenfalls Bezeichnungen, die auch unab-
hängig von Groß- und Kleinschreibung deutlicher
voneinander zu unterscheiden sind !
LG , Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:50 So 27.10.2013 | | Autor: | Nadia.. |
Hallo, das waren genau zwei Fehler die mir unterlaufen sind.
Ich habe es verändert und hoffe, dass jemand bald Antwortet.
Viele Grüße
Nadia..
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:13 So 27.10.2013 | | Autor: | tobit09 |
> Hallo, das waren genau zwei Fehler die mir unterlaufen
> sind.
Nein, es gibt weitere Fehler, die du noch nicht korrigiert hast. Siehe dazu meine Antwort.
> Ich habe es verändert und hoffe, dass jemand bald
> Antwortet.
Ich habe doch schon geantwortet. Was hast du zu meinen Fragen überlegt?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 06:10 So 27.10.2013 | | Autor: | tobit09 |
Hallo zusammen!
Ich versuche mal, das Bezeichnungschaos aufzulösen.
Eigentlich finde ich es aber nicht zu viel verlangt von dir, Nadia, eine Aufgabenstellung weitestgehend korrekt abzutippen. Am korrekten Abtippen haperte es auch schon im anderen Thread von dir...
> Sei [mm]\Omega= \Omega^{n,n}_{II}[/mm] die Menge aller Permutation
> der Zahlen [mm]1,.....,n.[/mm] Für [mm]1 \le i < j \le n[/mm] sagen wir
> [mm]\Omega[/mm] weist eine [mm]i-j[/mm] - Transposition auf, wenn gilt
> [mm]\omega_i = j[/mm] und [mm]\omega_j= i[/mm] und bezeichnen [mm]A_{i,j}[/mm] die
> Menge der Permutationen, die eine solche Transpositionen
> aufweisen.
>
> a)
>
> Sei [mm]I = \{ {(i,j) :1 \le i< J \le n} \}[/mm] und [mm]J \subset I[/mm] mit
> Card [mm]J = I \in \{1,....n (n-1)/2 \}[/mm]
Es muss heißen:
Sei [mm]I=\{(i,j):1\le i
> Definiere [mm]A_J = \bigcap_{i,j \in J}^{n} A_{i,j}[/mm]
Es muss heißen:
Definiere [mm]A_J=\bigcap_{(i,j)\in J}A_{i,j}[/mm].
> Beschreiben sie die Teilmenge [mm]J[/mm], für die gilt [mm]A_J \not= \emptyset[/mm]
Es muss "TeilmengeN [mm]J[/mm]" statt "Teilmenge [mm]J[/mm]" heißen.
> Bestimmen Sie für solche Indexmengen [mm]cardA_J[/mm] in
> Abhängigkeit von [mm]l[/mm]
>
> b.
> Wie viele Teilmengen [mm]J \subset I[/mm] gibt es mit [mm]card J = l[/mm]
> und [mm]A_J \not= \emptyset[/mm] ?
>
> c.Bestimmen Sie die Wahrscheinlichkeit dafür, dass eine
> zufällig gewählte Permutation [mm]\omega \in \Omega[/mm]
> ,
> wobei alle Permutationen als gleich wahrscheinlich
> angenommen werden, mindestens eine Transposition
> aufweist. Wie verhält sich diese Wahrscheinlichkeit für
> [mm]n \to \infty [/mm]
> Zu a.
> Die Teilmenge [mm]J[/mm] habe ich wie folgt beschrieben:
> [mm]J = \{ 1,2 ..... n(n-1)/2 \} [/mm].
Quatsch. [mm]J[/mm] ist eine Teilmenge von [mm]I[/mm] und somit eine Menge von Paaren.
Die Aufgabe erscheint mir durchaus sehr anspruchsvoll und ich möchte dir nicht versprechen, dir bis zu einer vollständigen Lösung zu verhelfen.
Vorschlag: Betrachte erst einmal den Fall [mm]n=3[/mm], um überhaupt die beteiligten Objekte zu verstehen.
Wie sieht dann die Menge [mm]I[/mm] aus?
Welche Teilmengen [mm]\emptyset\not=J\subset I[/mm] gibt es also?
Wie sieht [mm]A_J[/mm] für jede dieser Teilmengen [mm]\emptyset\not=J\subset I[/mm] jeweils aus?
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:47 Do 31.10.2013 | | Autor: | Nadia.. |
Hallo,
ich habe für n = 3 folgendes raus bekommen:
$I = [mm] \{ (1,2),(1,3),(2,3) \}$
[/mm]
für
$ [mm] \# [/mm] J = l [mm] \in \{ 1,2,3 \}$ [/mm]
Nun zu den Teilmengen $J [mm] \subset [/mm] I $
Es gibt insgesamt 6 Teilmengen.
[mm] $J_1 [/mm] = [mm] \{ (1,2) \} [/mm]
[mm] J_2 [/mm] = [mm] \{ (1,3) \} [/mm]
[mm] J_3 [/mm] = [mm] \{ (2,3) \} [/mm]
[mm] J_4 [/mm] = [mm] \{ (1,2),(1,3) \} [/mm]
[mm] J_5 [/mm] = [mm] \{ (1,2),(2,3) \} [/mm]
[mm] J_6 [/mm] = [mm] \{ (1,3),(2,3) \} [/mm] $
$ [mm] A_J [/mm] $ für jede dieser Teilmengen $ [mm] \emptyset\not=J\subset [/mm] I $ kann ich irgendwie nicht bestimmen.
Ich kann keine Transpirationen in den Mengen [mm] $J_1.. j_6$ [/mm] erkennen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 01:50 Fr 01.11.2013 | | Autor: | tobit09 |
> ich habe für n = 3 folgendes raus bekommen:
>
> [mm]I = \{ (1,2),(1,3),(2,3) \}[/mm]
![[ok]](/images/smileys/ok.gif "[ok]")
> für
> [mm]\# J = l \in \{ 1,2,3 \}[/mm]
> Nun zu den Teilmengen [mm]J \subset I[/mm]
> Es gibt insgesamt 6 Teilmengen.
>
> [mm]$J_1[/mm] = [mm]\{ (1,2) \}[/mm]
> [mm]J_2[/mm] = [mm]\{ (1,3) \}[/mm]
> [mm]J_3[/mm] = [mm]\{ (2,3) \}[/mm]
> [mm]J_4[/mm] = [mm]\{ (1,2),(1,3) \}[/mm]
> [mm]J_5[/mm] = [mm]\{ (1,2),(2,3) \}[/mm]
> [mm]J_6[/mm] = [mm]\{ (1,3),(2,3) \}[/mm] $
Da fehlt noch [mm] $J_7:=I$ [/mm] als weitere nichtleere Teilmenge von $I$.
Ansonsten:
> [mm]A_J[/mm] für jede dieser Teilmengen [mm]\emptyset\not=J\subset I[/mm]
> kann ich irgendwie nicht bestimmen.
> Ich kann keine Transpirationen in den Mengen [mm]J_1.. j_6[/mm]
> erkennen.
Was meinst du mit "Transpirationen"? Transpositionen?
Es geht gar nicht um "Transpositionen in den Mengen [mm] $J_1$ [/mm] bis [mm] $J_7$".
[/mm]
Bestimme zunächst (weiter im Fall $n=3$) die Menge [mm] $\Omega$ [/mm] und dann [mm] $A_{i,j}$ [/mm] für jedes [mm] $(i,j)\in [/mm] I$.
Dann kannst du [mm] $A_{J_1}$ [/mm] bis [mm] $A_{J_7}$ [/mm] bestimmen.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 02:29 Fr 01.11.2013 | | Autor: | Nadia.. |
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Hallo,
Die Menge Omega muss lauten: $\Omega = \{(1,2,3),(1,3,2),(2,3,1),(2,1,3),(3,1,2),(3,2,1)\}$
Dann muss für $A_{1,2} = \{ (2,1,3)\}, A_{1,3} = \{ (3,2,1)\} , A_{2,3} = \{ (1,3,2)\}}$.
Also erhält man für
$ A_{J_1} = \{ (2,1,3)\}, A_{J_2} = \{ (3,2,1)\},A_{J_3} = \{ (1,3,2)\}, A_{J_4} = \{ (2,1,3),(3,2,1)\}, A_{J_5} = \{ (2,1,3),(1,3,2) \}, A_{J_6} = \{ (3,2,1),(1,3,2) \}, A_{J_7} = \{ (3,2,1),(1,3,2),(2,1,3) \}$
Was mach ich nun ?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:13 Fr 01.11.2013 | | Autor: | tobit09 |
> Die Menge Omega muss lauten: [mm]\Omega = \{(1,2,3),(1,3,2),(2,3,1),(2,1,3),(3,1,2),(3,2,1)\}[/mm]
> Dann muss für [mm]A_{1,2} = \{ (2,1,3)\}, A_{1,3} = \{ (3,2,1)\} , A_{2,3} = \{ (1,3,2)\}}[/mm].
Es war
[mm] $J_1 [/mm] = [mm] \{ (1,2) \} [/mm]
[mm] J_2 [/mm] = [mm] \{ (1,3) \} [/mm]
[mm] J_3 [/mm] = [mm] \{ (2,3) \} [/mm]
[mm] J_4 [/mm] = [mm] \{ (1,2),(1,3) \} [/mm]
[mm] J_5 [/mm] = [mm] \{ (1,2),(2,3) \} [/mm]
[mm] J_6 [/mm] = [mm] \{ (1,3),(2,3) \}
[/mm]
[mm] J_7=\{(1,2),(1,3),(2,3)\}$.
[/mm]
> Also erhält man für
> [mm]A_{J_1} = \{ (2,1,3)\}, A_{J_2} = \{ (3,2,1)\},A_{J_3} = \{ (1,3,2)\},[/mm]
> [mm]A_{J_4} = \{ (2,1,3),(3,2,1)\}, A_{J_5} = \{ (2,1,3),(1,3,2) \}, A_{J_6} = \{ (3,2,1),(1,3,2) \}, A_{J_7} = \{ (3,2,1),(1,3,2),(2,1,3) \}[/mm]
![[notok]](/images/smileys/notok.gif "[notok]")
Beachte, dass in der Definition von [mm] $A_J$ [/mm] ein Schnitt und keine Vereinigung steht.
> Was mach ich nun ?
Wenn du [mm] $A_{J_4}$ [/mm] bis [mm] $A_{J_7}$ [/mm] korrigiert hast, können wir a) versuchen.
Wie gesagt, ist die Aufgabe alles andere als einfach.
Wenn man nicht sowieso schon eine gute Intuition hat, verlangt eine Herleitung der Aussagen viele Einzelschritte.
Ich möchte eine Menge [mm] $\emptyset\not=J\subseteq [/mm] I$ "gutartig" nennen, wenn für alle [mm] $(i_1,j_1),(i_2,j_2)\in [/mm] J$ mit [mm] $(i_1,j_1)\not=(i_2,j_2)$ [/mm] gilt: [mm] $\{i_1,j_1\}\cap\{i_2,j_2\}=\emptyset$.
[/mm]
(Welche der Mengen [mm] $J_1$ [/mm] bis [mm] $J_7$ [/mm] in unserem Beispiel $n=3$ sind also gutartig?)
Wir werden zeigen:
(*) Die Teilmengen [mm] $\emptyset\not=J\subseteq [/mm] I$ mit [mm] $A_J\not=\emptyset$ [/mm] sind genau die gutartigen.
1. Zeige: Sei [mm] $\emptyset\not=J\subseteq [/mm] I$ nicht gutartig (Was bedeutet das?). Dann gilt [mm] $A_J=\emptyset$.
[/mm]
(Nimm dazu an, es gäbe ein [mm] $\omega\in A_J$ [/mm] und leite einen Widerspruch her.)
Damit ist die Untersuchung von nicht gutartigen $J$ schon abgeschlossen.
Sei ab jetzt $J$ gutartig.
Sei [mm] $V_J:=\bigcup_{(i,j)\in J}\{i,j\}\subseteq\{1,\ldots,n\}$.
[/mm]
(Wie lautet also [mm] $V_{J_1}$ [/mm] bis [mm] $V_{J_3}$ [/mm] für unser Beispiel $n=3$?)
Wegen der Gutartigkeit von $J$ ist die Vereinigung aus der Definition von [mm] $V_J$ [/mm] eine Vereinigung paarweise disjunkter Mengen.
Also gilt
[mm] $\operatorname{card}V_J=\summe_{(i,j)\in J}\operatorname{card}\{i,j\}=\summe_{(i,j)\in J}2=(\operatorname{card}J)*2=2l$.
[/mm]
(Insbesondere [mm] $l=\bruch{\operatorname{card}V_J}2\le \bruch{n}2$.)
[/mm]
Für Teilmengen [mm] $T\subseteq\{1,\ldots,n\}$ [/mm] bezeichne $S(T)$ die Menge der Bijektionen [mm] $\sigma\colon T\to [/mm] T$.
Sei [mm] $T_J:=\{1,\ldots,n\}\setminus V_J\subseteq\{1,\ldots,n\}$.
[/mm]
(Wie lautet also [mm] $T_{J_1}$ [/mm] bis [mm] $T_{J_3}$ [/mm] für unser Beispiel $n=3$?)
2. Wie lautet [mm] $\operatorname{card}T_J$ [/mm] in Abhängigkeit von $l$?
(Benutze [mm] $\operatorname{card}V_J=2l$.)
[/mm]
3. Wie lautet [mm] $\operatorname{card}S(T_J)$ [/mm] also?
4. Zeige unter Verwendung der Gutartigkeit von $J$: Für jedes [mm] $\sigma\in S(T_J)$ [/mm] ist
[mm] $\omega_\sigma\colon\{1,\ldots,n\}\to\{1,\ldots,n\},\quad i\mapsto\begin{cases}j,&\text{ falls }(i,j)\in J\text{ oder }(j,i)\in J\\\sigma(i),&\text{ falls }i\in T_J\end{cases}$
[/mm]
eine i) wohldefinierte ii) bijektive Abbildung mit iii) [mm] $\omega_\sigma\in A_J$.
[/mm]
5. Zeige: Jedes [mm] $\omega\in A_J$ [/mm] hat die Form [mm] $\omega=\omega_\sigma$ [/mm] für ein eindeutig bestimmtes [mm] $\sigma\in S(T_J)$.
[/mm]
(Nämlich [mm] $\sigma\colon T_J\to T_J,\quad i\mapsto \omega(i)$.
[/mm]
Vergiss nicht zu zeigen, dass dieses [mm] $\sigma$ [/mm] wohldefiniert und bijektiv ist.)
Somit ist
[mm] $S(T_J)\to A_J,\quad \sigma\mapsto\omega_\sigma$
[/mm]
eine Bijektion.
Also [mm] $\operatorname{card} A_J=\operatorname{card}S(T_J)=\ldots$
[/mm]
(diese Kardinalität solltest du ja unter 3. überlegen).
Insbesondere gilt [mm] $\operatorname{card}A_J>0$ [/mm] und damit [mm] $A_J\not=\emptyset$.
[/mm]
Zusammen mit 1. folgt daraus (*).
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:48 Fr 01.11.2013 | | Autor: | Nadia.. |
Ich korrigiere $ [mm] A_{J_4} [/mm] $ bis $ [mm] A_{J_7} [/mm] $
und erhalte
$ [mm] A_{J_4} [/mm] = [mm] \bigcap_{i,j}^{} A_{i,j} [/mm] = [mm] A_{(1,2)} \cap A_{(1,3)} [/mm] = [mm] \emptyset [/mm] $
Analog erhalte ich für $ [mm] A_{J_5}=A_{J_6}=A_{J_7} [/mm] = [mm] \emptyset$
[/mm]
Die Mengen $ [mm] J_1 [/mm] $ bis $ [mm] J_3$ [/mm] bestehen aus einem Element, wie soll ich $ [mm] (i_1,j_1),(i_2,j_2)\in [/mm] J$ , mit $ [mm] (i_1,j_1)\not=(i_2,j_2) [/mm] $ wählen ?
Das geht doch nicht.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:19 Fr 01.11.2013 | | Autor: | tobit09 |
> Ich korrigiere [mm]A_{J_4}[/mm] bis [mm]A_{J_7}[/mm]
> und erhalte
> [mm]A_{J_4} = \bigcap_{i,j}^{} A_{i,j} = A_{(1,2)} \cap A_{(1,3)} = \emptyset[/mm]
> Analog erhalte ich für [mm]A_{J_5}=A_{J_6}=A_{J_7} = \emptyset[/mm]
> Die Mengen [mm]J_1[/mm] bis [mm]J_3[/mm] bestehen aus einem Element, wie soll
> ich [mm](i_1,j_1),(i_2,j_2)\in J[/mm] , mit [mm](i_1,j_1)\not=(i_2,j_2)[/mm]
> wählen ?
> Das geht doch nicht.
Genau. Also sind [mm] $J_1$ [/mm] bis [mm] $J_3$ [/mm] aus trivialen Gründen gutartig:
Angenommen etwa [mm] $J_1$ [/mm] wäre nicht gutartig.
Dann gäbe es [mm] $(i_1,j_1),(i_2,j_2)\in J_1$ [/mm] mit [mm] $(i_1,j_1)\not=(i_2,j_2)$, [/mm] so dass [mm] $\{i_1,j_1\}\cap\{i_2,j_2\}\not=\emptyset$.
[/mm]
Das kann aber, wie du richtig festgestellt hast, nicht sein, weil [mm] $J_1$ [/mm] einelementig ist.
|
|
|
|
