Permutation < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:55 Mo 07.11.2016 | | Autor: | knowhow |
| Aufgabe | Beweise:
Es sei X endliche Menge. Für alle [mm] \pi \in [/mm] S(X) und alle Transpositinen [mm] \tau \in [/mm] S(X) gilt [mm] cyc(\pi \circ \tau)=cyc(\pi)\pm [/mm] 1. |
Hallo,
ich weiß nicht so recht wie ich anfangen soll. Daher hoffe ich, dass Ihr mir da etwas helfen könnt.
[mm] cyc(\pi) [/mm] haben wir definiert als die Anzahl der Zyklen von [mm] \pi [/mm]
z.B. nehme als Beispiel
[mm] \pi [/mm] = (1 6 [mm] 5)\circ [/mm] (2 4) [mm] \circ [/mm] (3) dann ist [mm] cyc(\pi)=3
[/mm]
und wenn ich jetzt [mm] cyc(\pi \circ \tau) [/mm] betrachte dann verknüpfe ich [mm] \pi [/mm] mit [mm] \tau [/mm] also kommt ein weiteres zyklus hinzu (salopp gesagt)
z.B. (1 6 [mm] 5)\circ [/mm] (2 [mm] 4)\circ (3)\circ(3 [/mm] 4) (unabh. ob es stimmt oder nicht)
dann ist es für mich plausibel, dass [mm] cyc(\pi \circ \tau)=cyc(\pi)+1 [/mm] ist.
aber warum gilt auch [mm] cyc(\pi\circ\tau)=cyc(\pi)-1?
[/mm]
Bitte korrigiert mich falls ich etwas falsch verstehe.
Ich bin für jeden Tipp dankbar.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:58 Mo 07.11.2016 | | Autor: | hippias |
Bleiben wir bei Deinem [mm] $\pi$. [/mm] Bestimme der Reihe nach die Zyklenzahl von [mm] $\pi\tau$ [/mm] für [mm] $\tau=(78)$, $\tau=(24)$ [/mm] und [mm] $\tau= [/mm] (16)$.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:06 Di 08.11.2016 | | Autor: | knowhow |
Ich habe es mal "durchgerechnet" und erhalte jeweils immer als zyklenanzahl 4.
Was mache ich falsch?
Ich habe folgendes gemacht:
[mm] \pi\circ \tau=(1 [/mm] 6 [mm] 5)\circ(2 4)\circ(3)\circ [/mm] (7 8)
[mm] \Rightarrow cyc(\pi\circ \tau)=4
[/mm]
[mm] \pi\circ \tau=(1 [/mm] 6 [mm] 5)\circ(2 4)\circ(3)\circ [/mm] (2 4)=(1 6 [mm] 5)\circ(2)\circ(3)\circ [/mm] (4)
[mm] \Rightarrow cyc(\pi\circ\tau)=4
[/mm]
[mm] \pi\circ \tau=(1 [/mm] 6 [mm] 5)\circ(2 4)\circ(3)\circ [/mm] (1 6)=(1 [mm] 5)\circ(2 4)\circ(3)\circ [/mm] (6)
[mm] \Rightarrow cyc(\pi\circ\tau)=4
[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:16 Di 08.11.2016 | | Autor: | hippias |
Du hast Dich verrechnet, es sind aber trotzdem immer $4$ Zyklen, weil ich auch die $1$-Zykeln vergessen habe.
Schliesslich ist aber [mm] $cyc(\pi\circ [/mm] (25))= 2$.
Aus diesen Beispielen lässt sich eine Vermutung anstellen, unter welchen Bedingungen sich die Zyklenzahl erhöht und vermindert; dies beweise dann.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:45 Di 08.11.2016 | | Autor: | knowhow |
Nochmals vielen Dank. Mit einem Beispiel ist vieles mehr verständlicher, aber jetzt kommt das nächste Problem: Wie beweise ich sowas? Beweise bereiten mir immer schwierigkeiten, weil ich nicht so recht weiß wie ich anfangen soll.
ich definiere mal
[mm] \pi:\{1,...,6\}\to\{1,...,6\} [/mm] (mein Beispiel genommen)
dann gilt [mm] cyc(\pi\circ\tau)=cyc(\pi)+1
[/mm]
falls für [mm] \tau=(i,j) [/mm] mit i,j [mm] \not\in\{1,...,6\} [/mm] bzw es ein zyklus in [mm] \pi [/mm] gibt, sodass [mm] \tau=(i,j)=(i,j)\in\pi [/mm] ist?
und wenn für alle zyklus von [mm] \pi [/mm] gilt
[mm] \tau=(i,j)\not=(i,j)\in\pi [/mm] folgt [mm] cyc(\pi\circ\tau)=cyc(\pi)-1.
[/mm]
Ist es soweit richtig?
Ich möchte es wirklich verstehen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:33 Mi 09.11.2016 | | Autor: | hippias |
Ich glaube Dir schon, dass Du es wirklich verstehen möchtest, vielleicht auch, dass Du die Regel richtig vermutest, aber Deine Ausarbeitung ist mir nicht ganz verständlich. Du könntest also einmal Deine Vermutung in Worten formulieren. Richtig ist in jedem Fall, dass wenn die Ziffern der Transposition nicht unter den Zifern der Zyklen von [mm] $\pi$ [/mm] auftauchen, dass sich dann die Zykelzahl um $1$ erhöht.
Ausserdem empfehle ich für den Beweis ersteinmal anzunehmen, dass [mm] $cyc(\pi)=1$ [/mm] ist; eventuell auch [mm] $cyc(\pi)=2$. [/mm] Das wird sich prima verallgemeinern lassen.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:04 Do 10.11.2016 | | Autor: | knowhow |
Nochmals vielen dank für deine Geduld.
ich habe das mal für [mm] cyc(\pi)=1 [/mm] überlegt, aber dann kann ich kein [mm] \tau [/mm] finden, sodass [mm] cyc(\pi\circ\tau)=cyc(\pi)-1, [/mm] den [mm] \pi\circ\tau [/mm] muss mind. die Anzahl der Zyklen von [mm] \pi [/mm] haben.
Wenn es ein [mm] \tau [/mm] ex. sodass durch komposition [mm] \pi [/mm] auf den selben punkt abgebildet wird
z.B [mm] (\pi\circ\tau)(x)=(x) [/mm] (Fixpkt?) dann ist [mm] \cyc(\pi\circ\tau)= cyc(\pi\circ\tau)=cyc(\pi)+1
[/mm]
stimmt das?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:14 Do 10.11.2016 | | Autor: | hippias |
Da es keine Permutation ohne Zykel gibt, gilt im Fall [mm] $cyc(\pi)= [/mm] 1$ stets [mm] $cyc(\pi\circ \tau)= cyc(\pi)+1= [/mm] 2$.
Wie sieht es für [mm] $cyc(\pi)= [/mm] 2$ aus?
|
|
|
|
