(n-1)! Permutation < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 14:51 So 07.12.2008 | | Autor: | matmat |
| Aufgabe | Beweisen Sie, dass es in der Gruppe [mm] S_n [/mm] genau (n − 1)! verschiedene Permutationen
vom Typ [mm] (a_1 a_2 [/mm] . . . [mm] a_n) [/mm] gibt, die also alle n Objekte zyklisch vertauschen.
|
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo,
ich habe bei dieser Aufgabe einige Probleme.
Ich weiß zum Beispiel nicht, wie ich (n-1)! verstehen soll.
In anderen Fächern habe ich diese Schreibweise auch schon gesehen, aber ich weiß nicht viel damit anzufangen. n+1 bedeutet ja für jedes weitere n, also wenn n=1 ist, dann folgt 2,3,4,5. Und bei n-1 wird es dann rückwärts betrachtet?
n! bedeutet doch bei n=3 zum Beispiel 1*2*3=6 , und das bedeutet auch, dass es 6 Möglichkeiten der Anordnung von 123 gibt=
(123),(132),(231),(213),(321),(312).
also ist das Ergebnis der Fakultät einer Zahl auch gleich die maximale anzahl der Permutationen (wenn ich hierbei den Begriff der Permutation=Kombinationsmöglichkeiten richtig verstehe)
weiter kann ich mir vorstellen, das hier ein Induktionsbeweis benutzt werden könne.
also wenn ich für n=1 nehme wäre dann (1-1)!=0 was dann 1 Permutation wäre.
Kleine Nebenfrage : bei n=0 wäre es aber -1 und dadurch keine Permutation. Für mich würde es heissen dass Permutationen nur für [mm] n\not= [/mm] 0 gehen.
jedenfalls wäre n=1 der Induktionsanfang.
dann wäre die Induktionsvoraussetzung (n-1)!
und der Induktionsschritt für n+1 zu zeigen.
mit den Induktionsbeweisen habe ich aber ein paar probleme, müsste ich jetzt (n-1)!+n+1 nehmen, oder ((n-1)+(n+1))! ?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:20 So 07.12.2008 | | Autor: | pelzig |
[mm] $n!=1\cdot 2\cdot...\cdot [/mm] n$ und [mm] $(n+1)!=1\cdot 2\cdot ...\cdot n\cdot(n+1)$. [/mm] Außerdem ist $0!$ definiert als 1.
Gruß, Robert
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:35 So 07.12.2008 | | Autor: | matmat |
ich weiß schon was n Fakultät ist und das 0!=1 ist,aber wie es mit n-1 ist nicht so ganz.
Aber jetzt nach den Antworten würde ich sagen, dass n-1 also eine Teilmenge
des ganzen ist.
Die Aufgabenstellung ist wirklich so, habe mich dabei nicht verschrieben.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:38 So 07.12.2008 | | Autor: | pelzig |
[mm] $(n-1)!=1\cdot2\cdot [/mm] ... [mm] \cdot [/mm] (n-1)$. Schau dir die Antwort von Felix an.
Gruß, Robert
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:11 So 07.12.2008 | | Autor: | matmat |
achso,
also ist das so zu verstehen:
1,2,...,(n-1)!,...n!,...,(n+1)!
Wie haben noch diese Aussage als Tipp bekommen:
"Wieviel Möglichkeiten gibt es, die Einträge in den n-Tupel (1,2,...,n) zu permutieren? Wann beschreiben diese n-Tupel die gleiche Permutation?
-also es gibt doch n! Möglichkeiten für n,, was auch heisst dass die Gruppe die Ordnung n! hat.
kann ich es vielleicht so zeigen, dass (n-1) alle Elemente zwischen 1 und n sind, und n+1 alle Elemente nach n sind.
Alle gehören aber zu einer Menge M.Also wären die Element (n-1)! und (n+1)! zu einer Zusammensetzung
und M [mm] \to(f) \to [/mm] M [mm] \to [/mm] (g) [mm] \to [/mm] M
wobei f:= (n-1)! und g := (n+1)! wäre.
|
|
|
| |
|
Zu den Tipps schau mal hier.
Die Sache mit den Ordnungen brauchst du eigentlich nicht für diese Aufgabe. Und pass auf, dass du da nicht etwas durcheinanderschmeißt: [mm] S_{n} [/mm] enthält n! Abbildungen von {1..n} nach {1..n} (sprich Permutationen), aber n! ist nicht selbst Element dieser Gruppe.
lieben Gruß, tut-self
|
|
|
| |
|
Bist du sicher, dass die Aufgabe richtig gestellt ist?
[mm] S_{n} [/mm] ist soweit ich weiß die symmetrische Gruppe, die alle Permutationen über n enthält:
n [mm] \in \IN: S_{n}=\{\sigma:[n] \to [n] | \sigma ist Permutiation\}
[/mm]
Diese Menge enthält n! Elemente. Dies kannst du entweder über vollständige Induktion oder kombinatorisch beweisen: z.B. für erste Stelle gibt es n Möglichkeiten, für die zweite (n-1) ..... für die letzte nur noch eine
[mm] \Rightarrow [/mm] es gibt insgesamt n*(n-1)*...*1 = n! Möglichkeiten und damit n! verschiedene Permutationen in [mm] S_{n}.
[/mm]
Du sollst allerdings zeigen, dass es (n-1)! verschiedene Permutationen gibt...
also entweder ihr habt die Gruppe [mm] S_{n} [/mm] anders definiert, oder die Aufgabe ist doch anders gemeint.
Hoffe ich konnte dir damit ein bisschen weiterhelfen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:51 So 07.12.2008 | | Autor: | pelzig |
Es geht hier um die Teilmenge der zyklischen Permutationen...
Gruß, Robert
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:45 So 07.12.2008 | | Autor: | matmat |
Wir haben die Gruppe so definiert:
Eine Gruppe ist eine Menge G mit einer inneren Verknüpfung. [mm] GxG\toG:(a,b)\mapstoa*a [/mm] welche folgende Axiome erfüllt:
1 Assoziativgesetz
2neutrales Element
3 inverses Element
dann noch eine kleine Ergänzung zur ableschen Gruppe, wenn a [mm] \circ [/mm] b = b [mm] \circ [/mm] a ist
ist. für alle [mm] a,b\inG
[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:37 So 07.12.2008 | | Autor: | felixf |
Hallo
> Beweisen Sie, dass es in der Gruppe [mm]S_n[/mm] genau (n −
> 1)! verschiedene Permutationen
> vom Typ [mm](a_1 a_2[/mm] . . . [mm]a_n)[/mm] gibt, die also alle n Objekte
> zyklisch vertauschen.
>
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>
> Hallo,
>
> ich habe bei dieser Aufgabe einige Probleme.
> Ich weiß zum Beispiel nicht, wie ich (n-1)! verstehen
> soll.
Das sollte ja jetzt geklaert sein.
> weiter kann ich mir vorstellen, das hier ein
> Induktionsbeweis benutzt werden könne.
Das denke ich nicht.
Ueberlege dir doch mal, dass du jede solche zyklische Permutation eindeutig darstellen kannst als $(1, [mm] a_2, a_3, \dots, a_n)$ [/mm] mit [mm] $a_2, \dots, a_n \in \{ 2, \dots, n \}$ [/mm] und [mm] $a_i \neq a_j$ [/mm] fuer $i [mm] \neq [/mm] j$.
Wenn du das hast, ist's ganz einfach.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:37 So 07.12.2008 | | Autor: | matmat |
ist eine zyklische Permutation deswegen eindeutig zu bestimmen, weil Sie eine Teilmenge der ganzen Permutation hat, also endlich ist?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:34 So 07.12.2008 | | Autor: | felixf |
Hallo
> ist eine zyklische Permutation deswegen eindeutig zu
> bestimmen, weil Sie eine Teilmenge der ganzen Permutation
> hat, also endlich ist?
Nein.
Beachte doch mal folgendes: $(1, 2, 3, 4, 5, 6)$ und $(3, 4, 5, 6, 1, 2)$ definieren die gleiche zyklische Permutation, $(1, 3, 2, 4, 5, 6)$ definiert dagegen eine andere.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:22 So 07.12.2008 | | Autor: | matmat |
ich glaube ich habe es verstanden.
man kann jede zyklische Permutation als eine Matrix darstellen,
oben in die Zeile die Urbilder und unten die Bilder?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:28 So 07.12.2008 | | Autor: | matmat |
achso , wenn ich dein Beispiel nehme wäre das vielleicht so:
[mm] \delta:= \vektor{1,2,3,4,5,6 \\ 3,4,5,6,1,2}
[/mm]
zum Beispiel wäre hier ein Zyklus [mm] 1\to3\to5\to1[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 05:19 Mo 08.12.2008 | | Autor: | felixf |
Hallo
> achso , wenn ich dein Beispiel nehme wäre das vielleicht
> so:
>
>
> [mm]\delta:= \vektor{1,2,3,4,5,6 \\ 3,4,5,6,1,2}[/mm]
>
> zum Beispiel wäre hier ein Zyklus [mm]1\to3\to5\to1[/mm]
Nein! Genau so is das nicht gemeint!
Schau mal in eurem Skript nach, was die Schreibweise [mm] $(a_1, a_2, \dots, a_n)$ [/mm] bedeutet!
In diesem Fall: $3$ wird auf $4$ abgebildet, $4$ auf $5$, $5$ auf $6$, $6$ auf $1$, [mm] $\dots$
[/mm]
LG Felix
|
|
|
| |
|
Diese Aussage stimmt an sich, nur hat deine Beispielmatrix keine zyklische Permutation dargestellt. So wie ich es aus den Beiträgen herausgelesen hab (und dann macht die Aufgabe auch Sinn *g*), ist eine zyklische Permutation, eine Permutation, die nur einen Zyklus enthält.
Die Schreibsweise [mm] (a_{1},a_{2},...,a_{n}) [/mm] bedeutet also, dass [mm] a_{1} [/mm] auf [mm] a_{2} [/mm] abgebildet wird, [mm] a_{2} [/mm] auf [mm] a_{3} [/mm] .... [mm] a_{n-1} [/mm] auf [mm] a_{n} [/mm] und [mm] a_{n} [/mm] wieder auf [mm] a_{1} [/mm] und damit ist der Zyklus geschlossen.
Deine Besipielmatrix enthält, wie du selbst festgestellt hast, zwar einen Zyklus, aber dieser Zyklus enthält nicht alle n Elemente, deshalb ist es keine zyklische Permutation.
Das bedeutet natürlich, dass (1,2,3,4,5) und (2,3,4,5,1) die gleiche Permutation darstellen, nämlich die Abbildung
[mm] $\delta:= \vektor{1,2,3,4,5,6 \\ 2,3,4,5,6,1}$, [/mm] um es mit einer Matrix zu schreiben.
Jetzt zu den beiden Tipps, die ihr bekommen habt:
Wie viele Möglichkeiten gibt es denn insgesamt die Einträge in den n-Tupeln ( also [mm] (a_{1},a_{2},...,a_{n}) [/mm] ) anzuordnen, sprich zu permutieren?
Und dann musst du dir überlegen, wann diese Tupel, die gleiche Permutation beschreiben. Nimm also an, du hast ein festes Tupel, z.B. (1,2,3,4,5). Wie viele andere Tupel gibt es denn noch, die die gleiche Permutation beschreiben? (hier z.B. (2,3,4,5,1), (3,4,5,1,2) u.s.w.).
Hast du diese beiden Fragen beantwortet, ist die Lösung einfach:
Nennen wir mal die Anzahl aller möglichen Anordnungen der n-Tupel a und die Anzahl der Tupel, die jeweils die gleiche Permutation beschreiben b.
Dann gibt es [mm] \bruch{a}{b} [/mm] Permutationen in [mm] S_{n}, [/mm] die alle Enträge zyklisch vertauschen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:28 So 07.12.2008 | | Autor: | matmat |
Morgen werde ich die Aufgabe weiterbearbeiten,denn ich möchte noch zwei weitere Aufgaben aus dem Thema Permutation hier reinsetzen und mit euch zusammen durchgehen.
Vielen Dank jetzt schonmal für die ganzen Tipps und Hilfen.
Viele Grüße
|
|
|
|
