Zeige #Aut{1,....,n} = n! < Abbildungen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:52 Mo 08.11.2010 | | Autor: | void. |
| Aufgabe | Sei [mm] S_n [/mm] = Aut{1,....,n} die Gruppe der Permutationen der Ziffern von 1 bis n.
Zeige #Aut{1,....,n} = n! . |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
hallo,
ich versuch die Aufgabe zu lösen, komme aber nicht sehr weit..
Da es sich um die Anzahl der Elemente, der Permutation, einer Automorphismusgruppe handelt sind die Abbildungen alle bijektiv,
also gilt, dass
o(1) [mm] \not= o(2)\not= [/mm] ..... [mm] \not= [/mm] o(n)
mit o: {1,....,n} [mm] \to [/mm] {1,....,n}
aber dann hab ich keine Ahnung wie ich jetzt zeigen soll das die Behauptung gilt :/
wäre für jeden tipp dankbar
|
|
| |
|
Guten Abend,
ich werf mal den Begriff "Vollständige Induktion" in den Raum!
Überleg dir, wie du einen Automorphismus aus [mm]\{ 1,...,n-1 \}[/mm] auf einen aus [mm]\{ 1,...,n \}[/mm] forsetzen kannst!
Dann macht die Induktion den Rest!
lg Kai
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:42 Mo 08.11.2010 | | Autor: | void. |
:s oh man ich hab grad gar keinen durchblick..
hab mir jetz einiges zu Automorphismengruppen un permutationen durchgelesen und versteh jetz erst recht net wie man der gruppe einfach ein Element hinzufügen kann
bzw wie ich das dann für die Induktion aufschreiben muss und was für die andere seite gilt ~~
|
|
|
| |
|
Hallo void,
wenn Du eine vollständige Liste aller Permutationen von n Elementen vorliegen hast (egal, wie geordnet), dann kannst Du eine Liste für n+1 Elemente erzeugen, indem Du jedem bisherigen Element (der n-Liste) n+1 neue zuordnest, in den das zusätzliche Element erst ganz vorne, dann zwischen dem bisherigen ersten und zweiten, ..., zwischen dem bisher vorletzten und letzten, und schließlich nach dem bisher letzten Element steht.
Jetzt übersetz Dir diese Vorgehensweise mal in Gruppen. Aber eigentlich suchst Du doch gerade nur deren Mächtigkeit, oder? 
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:42 Mo 08.11.2010 | | Autor: | void. |
Hallo,
danke für die schnelle antwort aber bei mir dauert das etw länger :s
> Jetzt übersetz Dir diese Vorgehensweise mal in Gruppen.
> Aber eigentlich suchst Du doch gerade nur deren
> Mächtigkeit, oder?
>
> Grüße
> reverend
>
hoffe du hast mengen gemeint, sonst hab ich wieder keine ahnung wie das gemeint is^^
aber bzgl der menge würde aus
n*(n-1)*(n-2)*...*(n-(n-1))=n!
(n+1)*n*(n-1)*(n-2)*...*(n-(n-1))=n!*(n+1) als induktionsschritt
wobei mir gerade auffällt, dass das schwachsinn ist, da ich damit gar nix beweise :/.
Ich versteh irgendwie einfach net wie ich #Aut{1,....,n} in was umformen kann auf das ich n+1 anwenden kann...
|
|
|
| |
|
Hallo nochmal,
> > Jetzt übersetz Dir diese Vorgehensweise mal in Gruppen.
> > Aber eigentlich suchst Du doch gerade nur deren
> > Mächtigkeit, oder?
>
> hoffe du hast mengen gemeint, sonst hab ich wieder keine
> ahnung wie das gemeint is^^
Öh, jaja... Aber ging es nicht um Homomorphismen?
> aber bzgl der menge würde aus
>
> n*(n-1)*(n-2)*...*(n-(n-1))=n!
> (n+1)*n*(n-1)*(n-2)*...*(n-(n-1))=n!*(n+1) als
> induktionsschritt
>
> wobei mir gerade auffällt, dass das schwachsinn ist, da
> ich damit gar nix beweise :/.
Wieso nicht? Ist das nicht genau das, was Du suchst? $ (n+1)*n!=(n+1)! $
> Ich versteh irgendwie einfach net wie ich #Aut{1,....,n} in
> was umformen kann auf das ich n+1 anwenden kann...
Woran liegts denn? An der Notation #Aut ?
Grüße
reverend
|
|
|
| |
|
Hi,
> > Öh, jaja... Aber ging es nicht um Homomorphismen?
>
> Meinst du damit den Gruppenhomomorphismus? soweit ich weiß
> impliziert doch der Automorphismus den ?! die Mächtigkeit
> von Gruppen ist doch die gleiche wie die der Menge der
> Elemente die in der liegen?
Jawoll.
> Spielt die Eigenschaft Homomorphismus für die Aufgabe
> eigentlich eine Rolle?
Gute Frage. Sie ist jedenfalls ohne diese Eigenschaft zu lösen, so dass ich denke, es sollte eine elegantere Lösung geben, die sich die Eigenschaft zunutze macht. Ich sehe aber nicht, wie.
> > Wieso nicht? Ist das nicht genau das, was Du suchst?
> > [mm](n+1)*n!=(n+1)![/mm]
>
> Ja aber ich hab das quasi rückwärts angenommen...
Nein, das ist vorwärts konstruierbar, wie ich vorhin beschrieben habe.
> muss ich nicht erst zeigen das aus der
> Automorphismusgruppe diese Gleichung folgt? .... das is das
> was ich net versteh wie es geht :<
Tja... Ich lasse die Frage mal halboffen. Da sehe ich auch keinen Weg, aber in meiner Zeitzone ist es auch schon Mitternacht.
> > Woran liegts denn? An der Notation #Aut ?
>
> was die Symbole bedeuten bzw für was sie stehn weiß ich
> aber welche Eigenschaft ich mir daraus greifen muss um auf
> die richtige Notation für die Induktion zu kommen ist mir
> schleierhaft
Ja, vielleicht ist es nur eine Notationsfrage, ohne dass der eigentliche Weg sich ändert.
Ich geh mal voll Spannung schlafen. Muss nur noch eben was für morgen vorbereiten... :-(
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 12:25 Di 09.11.2010 | | Autor: | void. |
Neuer Tag neue ideen? :>
> > > Wieso nicht? Ist das nicht genau das, was Du suchst?
> > > [mm](n+1)*n!=(n+1)![/mm]
> >
> > Ja aber ich hab das quasi rückwärts angenommen...
>
> Nein, das ist vorwärts konstruierbar, wie ich vorhin
> beschrieben habe.
>
> > muss ich nicht erst zeigen das aus der
> > Automorphismusgruppe diese Gleichung folgt? .... das is das
> > was ich net versteh wie es geht :<
>
> Tja... Ich lasse die Frage mal halboffen. Da sehe ich auch
> keinen Weg, aber in meiner Zeitzone ist es auch schon
> Mitternacht.
das es vorwärts konstruierbar ist, ist mir klar :D ich meinte, dass ich keine Ahnung hab wie ich auf die gleichung kommen soll.
Darauf gekommen bin ich nur weil ich weiß wie n! ausgeschrieben aussieht (un hab das dann auf die andere seite gestellt ......)
Also dummerweise völlig unabhängig von der Aut.Gruppe
passt halt hier weil das ja die Bedingung war :/
..Ich versuchs mal konkret darzustellen
Ich muss doch erstma beweisen dass für die Automorphismusgruppe das folgende gilt:
n*(n-1)*(n-2)*...*(n-(n-1))
um dann über die Induktion zeigen zu können dass
n*(n-1)*(n-2)*...*(n-(n-1)) = n!
gilt
wodurch dann die Behauptung bewiesen ist
>
> > > Woran liegts denn? An der Notation #Aut ?
> >
> > was die Symbole bedeuten bzw für was sie stehn weiß ich
> > aber welche Eigenschaft ich mir daraus greifen muss um auf
> > die richtige Notation für die Induktion zu kommen ist mir
> > schleierhaft
>
> Ja, vielleicht ist es nur eine Notationsfrage, ohne dass
> der eigentliche Weg sich ändert.
> Ich geh mal voll Spannung schlafen. Muss nur noch eben was
> für morgen vorbereiten... :-(
>
> Grüße
> reverend
>
Grüße
void
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:40 Di 09.11.2010 | | Autor: | wieschoo |
> ..Ich versuchs mal konkret darzustellen
> Ich muss doch erstma beweisen dass für die
> Automorphismusgruppe das folgende gilt:
> n*(n-1)*(n-2)*...*(n-(n-1))
Das wäre ja die zu beweisende Annahme. Eigentlich musst du nur den Schritt von aut{1...n-1} zu aut{1...n} basteln.
>
> um dann über die Induktion zeigen zu können dass
> n*(n-1)*(n-2)*...*(n-(n-1)) = n!
Da gibts nichts zu beweisen
n*(n-1)*(n-2)*...*(n-(n-1))=n*(n-1)*(n-2)*...*(1) =: n!
> gilt
>
> wodurch dann die Behauptung bewiesen ist
Damit bin ich nicht ganz einverstanden, falls ich dich richtig verstehe. Für den speziellen (tivialen) Fall zeigst du #Aut{1}=1.
Dann nimmst du an, dass #Aut{1,...,n-1} = (n-1)! gilt und konstruierst den Aut{1,...,n} aus dem Aut{1,...,n-1} und musst dann bei #Aut{1,...,n} auf n! kommen.
Das wäre dann die Induktion. Ich bin nicht der Meinung, dass du erst
> n*(n-1)*(n-2)*...*(n-(n-1))
zeigen musst. Dann würde Induktion keinen Sinn mehr machen.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:15 Mi 10.11.2010 | | Autor: | void. |
> Damit bin ich nicht ganz einverstanden, falls ich dich
> richtig verstehe. Für den speziellen (tivialen) Fall
> zeigst du #Aut{1}=1.
> Dann nimmst du an, dass #Aut{1,...,n-1} = (n-1)! gilt und
> konstruierst den Aut{1,...,n} aus dem Aut{1,...,n-1} und
> musst dann bei #Aut{1,...,n} auf n! kommen.
> Das wäre dann die Induktion. Ich bin nicht der Meinung,
> dass du erst
> > n*(n-1)*(n-2)*...*(n-(n-1))
> zeigen musst. Dann würde Induktion keinen Sinn mehr
> machen.
>
Ich glaub jetz hab ich verstanden was mein fehler ist....
also ich nehm einfach an das
#Aut{1,...,n}=n!
dann schreib ich n! um in
n! = n*(n-1)*(n-2)*...*(n-(n-1)) = #Aut{1,...,n}
und muss jetzt den Induktionsschritt machen ..
wo ich bei meinem Problem bin, wie man das für mengen macht
wenn ich ne einfachere Menge M:={1,.....,n} nehm
dann is ja # M = [mm] \summe_{i=1}^{n} 1_i
[/mm]
aber wie kann ich jetz zb M:= {1,.....,n, n+1} [mm] \Rightarrow [/mm] # [mm] M=\summe_{i=1}^{n} 1_i [/mm] +1 = # [mm] M=\summe_{i=1}^{n+1} 1_i
[/mm]
Oder wie ginge das? :o
Gruss
|
|
|
| |
|
Damit das nicht ins Leere geht, kommt ein Vorschlag (ohne Gewähr!)
Allgemein
Sei M eine Menge mit [mm]|M|=n\,[/mm]
Induktion über n
IA: n=1 trivial es gibt nur die Identität als Permutation [mm]x\mapsto x[/mm] mit [mm]x\in\{x\}[/mm]
IS:
I-Vor: Sei Aussage für n=k bewiesen
I-Beh: Aussage gilt für n=k+1
I-Schritt: Sei [mm]|M|=k+1[/mm]. Also [mm]M=M'\cup \{y\}[/mm] mit [mm]y\in M[/mm] beliebig aber fest. Dann kann man die I-Vor auf M' anwenden und es gibt dort k! mögliche Permutationen. Jetzt ist aber das y beliebig aus der Menge M gewählt. Somit gilt es das [mm]y \in {1,\ldots,k+1}[/mm] an k+1 Stellen sitzen kann. Also insgesamt (k+1)k!=(k+1)! mögliche Permutationen.
speziell zur Aufgabe
Übertragen auf Automorphismen würde ich dann so ähnlich machen. Nur das #Aut{1,...,n+1} Permutationen [mm]\varrho_1,\ldots\varrho_n[/mm] und eine Permutation [mm]\sigma (x)=x[/mm] enthält, das ein Element festhält, beinhaltet. Die [mm]\varrho_1,\ldots\varrho_n[/mm] permutieren nach Induktionsvoraussetzung. Da man mit dem [mm]\sigma[/mm] ein beliebiges [mm]x\in\{1,...,n+1\}[/mm] festhalten kann, gibt es da nun (n+1) Möglichkeiten. Das macht wiederum (n+1)n!=(n+1)!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:16 Mi 10.11.2010 | | Autor: | void. |
danke für die Hilfe.
Gruß
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:20 Do 11.11.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:21 Do 11.11.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
Hallo zusammen,
ich habe diesen recht langwierigen Thread zu einer im
Grunde fast trivialen Frage einmal durchgesehen (nicht
bis in die Details) und denke, dass die Hauptschwierigkeit
wohl einfach darin liegt, einen ziemlich einfachen Induk-
tionsbeweis (den man locker hinschreiben könnte ohne
das ganze Brimborium von Automorphismengruppen etc.)
in einer ungewohnt formalistischen Weise darzustellen.
Gut, zu einem Studium der höheren Mathematik gehört
es natürlich auch, zu üben, sich in einer solchen Umgebung
zurechtzufinden. Wenn dabei aber der ursprünglich recht
einfache Inhalt einer Überlegung komplett unterzugehen
droht, dann halte ich das, was dabei geschieht, nicht mehr
für wirklich "gute" Mathematik ...
Was meint ihr dazu ?
Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:53 Mi 10.11.2010 | | Autor: | felixf |
Moin Al,
> ich habe diesen recht langwierigen Thread zu einer im
> Grunde fast trivialen Frage einmal durchgesehen (nicht
> bis in die Details) und denke, dass die
> Hauptschwierigkeit
> wohl einfach darin liegt, einen ziemlich einfachen Induk-
> tionsbeweis (den man locker hinschreiben könnte ohne
> das ganze Brimborium von Automorphismengruppen etc.)
> in einer ungewohnt formalistischen Weise darzustellen.
da hast du wohl Recht. Ich denke, das Hauptproblem ist das, was man eigentlich per Induktion zeigen will. Hier kann man wesentlich einfacher eine allgemeinere Aussage zeigen, aus der dann die Behauptung folgt.
Naemlich: sind $A$ und $B$ zwei Mengen mit $n$ Elementen, so gibt es genau $n!$ bijektive Abbildungen $A [mm] \to [/mm] B$.
Mit $B = A = [mm] \{ 1, \dots, n \}$ [/mm] folgt sofort die Behauptung, die man eigentlich zeigen soll.
Diese verallgemeinerte Aussage hat den grossen Vorteil, dass die Induktionsvoraussetzung viel flexibler ist. Sobald man ein Element $x [mm] \in [/mm] A$ und ein Element $y [mm] \in [/mm] B$ fixiert, kann man $A' := A [mm] \setminus \{ x \}$ [/mm] und $B' := B [mm] \setminus \{ y \}$ [/mm] betrachten, beides Mengen mit $n - 1 = [mm] \abs{A} [/mm] - 1 = [mm] \abs{B} [/mm] - 1$ Elementen, und erhaelt, dass es $(n - 1)!$ bijektive Abbildungen $X' [mm] \to [/mm] Y'$ gibt.
Nun gibt es zu jeder Wahl von $y$ (bei festem $x$) genau $(n - 1)!$ bijektive Abbildungen $A [mm] \to [/mm] B$, die $x$ auf $y$ abbilden. Da $y$ beliebig ist und man $n$ Moeglichkeiten hat, gibt es also $n! = n [mm] \cdot [/mm] (n - 1)!$ bijektive Abbildungen $A [mm] \to [/mm] B$.
Das etwas formaler aufzuschreiben ist auch kein grosser Aufwand. Dafuer hat man nicht das Problem, dass aus $A = B = [mm] \{ 1, \dots, n \}$ [/mm] und $x = 1$ nicht $A' = B' = [mm] \{ 1, \dots, n - 1 \}$ [/mm] folgt, man also nicht die Induktionsvoraussetzung einfach so anwenden kann.
> Gut, zu einem Studium der höheren Mathematik gehört
> es natürlich auch, zu üben, sich in einer solchen
> Umgebung
> zurechtzufinden. Wenn dabei aber der ursprünglich recht
> einfache Inhalt einer Überlegung komplett unterzugehen
> droht, dann halte ich das, was dabei geschieht, nicht
> mehr
> für wirklich "gute" Mathematik ...
Wenn man keinen schoenen Beweis findet, hat man oft
(a) das Problem zu speziell formuliert (wie hier), oder
(b) das Problem zu allgemein formuliert.
Oder man hat noch nicht die richtigen Hilfsmittel erstellt, um das Problem "schoen" loesen zu koennen
Ansonsten ist das ein ziemlich philosophisches Problem, sozusagen der "ewige Kampf" zwischen Schoenheit und Formalismus. Beides ist notwendig (Formalismus damit man auch wahre Aussagen zeigt, und Schoenheit damit man nicht die Lust verliert), teilweise widersprechen sie sich (uebertriebener Formalismus ist meistens nicht schoen), man muss also die richtige Balance finden...
LG Felix
|
|
|
|
