Bahnen/Orbits.. < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:13 So 13.05.2007 | | Autor: | Maren88 |
| Aufgabe | Es sei k und n natürliche Zahlen; wir kürzen ab:
K = {1, 2, ..., k} und N = {1,2,...,n}
sowie
Inj(n,k) = { f:K -> N | f ist injektive Abbildung}.
Die Gruppe [mm] Sym_{k} [/mm] operiert auf Inj(n,k) vermöge [mm] \sigma [/mm] f := f [mm] \circ \sigma^{-1}. [/mm] Bestimmen sie die Anzahl der Bahnen. |
Hallo,
also ich muss sagen, dass ich mir da grad gar nix zu vorstellen kann zu der Aufgabe.
könnte ich das [mm] \sigma [/mm] f so "umschreiben" :
(1 ... k)*[f(1,...,n)] ? (bringt mir das überhaupt etwas?)
um die Bahnen zu bestimmen muss ich doch das hier "berechnen":
G * m = {g * m | g [mm] \in [/mm] G}
aber was ist denn in diesem Fall mein G? [mm] Sym_{k}?
[/mm]
wär lieb, wenn mir jemand die Aufgabe bissel erklären könnte und mir ein paar Tipps geben könnte..
Lieber Gruß
Maren
Ich habe die Frage auf keiner anderen Internetseite in einem Forum gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:46 So 13.05.2007 | | Autor: | Maren88 |
hat denn keiner ne Idee?
bin echt ratlos... :-?
|
|
|
| |
|
Hallo Maren!
> könnte ich das [mm] \sigma [/mm] f so "umschreiben" :
Also ich interpretiere das mal so: [mm]\sigma \in Sym_k[/mm] liefert Dir eine Permutation eines k-Tupels [mm](r_1, r_2, ..., r_k) \in K[/mm], und es ist [mm]\sigma(r_i) = r_j[/mm], wenn [mm] \sigma [/mm] das Element [mm]r_i[/mm] auf [mm]r_j[/mm] abbildet. Für [mm]x \in K[/mm] ist [mm](\sigma f)(x) = f(\sigma^{-1}(x))[/mm].
> um die Bahnen zu bestimmen muss ich doch das hier
> "berechnen":
> [mm]G * m = \{g * m | g \in G\}[/mm]
>
> aber was ist denn in diesem Fall mein G? [mm]Sym_{k}?[/mm]
Ja. Allgemein ist die Bahn folgendermaßen definiert:
Sei G eine Gruppe, X eine nichtleere Menge, [mm]\tau:G \times X \to X, (a,x) \mapsto a(x)[/mm] eine Operation und [mm]x \in X[/mm], so heißt die Menge
[mm]G(x) = \{a(x)|a \in G\}[/mm]
die Bahn (Transitivitätsbereich/Orbit) von x unter [mm] \tau.
[/mm]
In Deiner Aufgabe entspricht [mm]G = Sym_k[/mm] und [mm]X = Inj(n,k)[/mm]. Zur Berechnung der Anzahl der Bahnen fällt mir die Bahnengleichung ein. Die (und eigentlich auch die Def. der Operation) müßtet ihr doch in der Vorlesung gehabt haben? Oder stellen die Euch Aufgaben zu Stoff, den ihr noch nicht gehabt habt?
Grüße
Karsten
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:05 So 13.05.2007 | | Autor: | Maren88 |
erstmal vielen Dank.
>
> In Deiner Aufgabe entspricht [mm]G = Sym_k[/mm] und [mm]X = Inj(n,k)[/mm].
> Zur Berechnung der Anzahl der Bahnen fällt mir die
> Bahnengleichung ein. Die (und eigentlich auch die Def. der
> Operation) müßtet ihr doch in der Vorlesung gehabt haben?
> Oder stellen die Euch Aufgaben zu Stoff, den ihr noch nicht
> gehabt habt?
>
leider hatten wir bis jetzt weder die Bahnengleichung noch die Def. der Operation.
jedoch steht in der Aufgabenstellung, dass wir das in der nächsten Vorlesung (also morgen) besprechen werden.. ich hoff, dass ich dann morgen in der Lage bin, die Anzahl der Bahnen auszurechnen.. falls nicht, sag ich nochmal bescheid 
Lieber Gruß Maren
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 15:54 Mo 14.05.2007 | | Autor: | Maren88 |
Hallo,
also wir hatten heute nochmal Vorlesung in Algebraische Strukturen. jedoch haben wir nur die Definition von Bahnen (Orbit) aufgeschrieben und dazu ein paar Beispiele genannt. eine Bahnengleichung wurde nicht erwähnt.
Danach ging es auch gleich weiter mit Restklassen..
die Definition der Operation (wir nennen diese auch Aktion) hatten wir jedoch schon, aber wie soll ich damit die Anzahl der Bahnen bestimmen?
stimmt denn der "Ansatz":
[mm] Sym_{k} \times [/mm] Inj(n,k) [mm] \to [/mm] Inj(n,k)
[mm] (\sigma,f) \mapsto \sigma [/mm] f := f [mm] \circ \sigma_{-1}
[/mm]
und [mm] Sym_{k}(Inj(x)) [/mm] = { [mm] \sigma(f(x)) [/mm] := (f [mm] \circ \sigma_{-1})(x) [/mm] | x [mm] \in Sym_{k} [/mm] }
?
aber irgendwie weiß ich garn nich wie ich da was ausrechnen soll..
als Tipp stand bei der Aufgabe noch dabei: "Es ist ganz anschaulich, sich die Abb. f: K -> N als das "Wort" f(1)f(2)..f(k) vorzustellen, dessen Buchstaben also der Reihe nach die Werte von f sind."
jedoch find ich diesen "tollen Tip" nich wirklich so anschaulich...
Lieber Gruß Maren
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:53 Di 15.05.2007 | | Autor: | Maren88 |
Hallo nochmal..
also ich weiß jetzt was als Lösung bei der Aufgabe rauskommen soll, nur hab ich noch ein paar kleine Schwierigkeiten wie man drauf kommt.
also: k [mm] \le [/mm] n, da zu jeder Abbildung ja min. ein Urbild geben muss (ist die Begründung richtig?)
dann gilt | Inj(n,k) | = [mm] \bruch{n!}{(n-k)!}
[/mm]
(kann mir jemand sagen wie man darauf kommt? )
und | [mm] Sym_{k} [/mm] | = k!
weiterhin hab ich mir überlegt:
k! * f = [mm] \bruch{n!}{(n-k)!} [/mm] * [mm] (k!)^{-1} [/mm]
=>
k! * f = [mm] \bruch{n!}{(n-k)!} [/mm] * [mm] \bruch{1}{(k)!}
[/mm]
=>
k! * f = [mm] \bruch{n!}{k!(n-k)!} [/mm] = [mm] \vektor{n \\ k}
[/mm]
=> f= [mm] \bruch{1}{\bruch{n!}{k!(n-k)!}} [/mm] = [mm] (\bruch{n!}{k!(n-k)!})^-1
[/mm]
ist jetzt f meine Anzahl an Bahnen? mir wurde das so in etwa erklärt, bin mir aber nich sicher. ??
Lieber Gruß Maren
|
|
|
| |
|
> also: k [mm]\le[/mm] n, da zu jeder Abbildung ja min. ein Urbild
> geben muss (ist die Begründung richtig?)
Stimmt. Es muß k [mm] \le [/mm] n sein. Eine injektive Abbildung f liefert zu paarweise verschiedenen a,b immer voneinander verschiedene f(a) und f(b). Wäre k > n, so gäbe es zwei Elemente x,y [mm] \in [/mm] K mit f(x)=f(y). Es stehen dann nämlich zuwenig Werte aus N zur Verfügung, um die Abbildung wiederholungsfrei zu halten.
> dann gilt | Inj(n,k) | = [mm]\bruch{n!}{(n-k)!}[/mm]
> (kann mir jemand sagen wie man darauf kommt? )
Man macht das auf kombinatorische Weise (deshalb auch der Verweis auf "Worte" über dem Alphabet {1, ..., n}). Um 1 [mm] \in [/mm] K auf n Plätzen (für "Buchstaben") unterzubringen, gibt es n Möglichkeiten. Für die 2 [mm] \in [/mm] K gibt es (n-1) Möglichkeiten, usw. Für k [mm] \in [/mm] K hat man zum Schluß nur noch (n-k+1) Möglichkeiten. Es darf sich wg. Injektivität keiner der Buchstaben wiederholen. Das macht zusammen
[mm] n * (n-1) * ... * (n-k+1) = \bruch{n!}{(n-k)!}[/mm]
Möglichkeiten.
> und | [mm]Sym_{k}[/mm] | = k!
Auch das ist richtig. Jede Bijektion zwischen zwei endlichen, gleichmächtigen Mengen (die durch {1, ..., m} repäsentiert werden können), stellt eine Permutation dar. Es gibt m! solcher Permutationen. Das kannst Du Dir auch anhand von Worten über {1, ..., m} überlegen: Für den ersten vom m Plätzen hat man m Möglichkeiten, für den zweiten (m-1) usw. Und für den letzten bleibt noch 1 Möglichkeit übrig. Insgesamt also [mm] m * (m-1) * ... * 2 * 1 = m![/mm].
> weiterhin hab ich mir überlegt:
>
> k! * f = [mm]\bruch{n!}{(n-k)!}[/mm] * [mm](k!)^{-1}[/mm]
> =>
> k! * f = [mm]\bruch{n!}{(n-k)!}[/mm] * [mm]\bruch{1}{(k)!}[/mm]
> =>
> k! * f = [mm]\bruch{n!}{k!(n-k)!}[/mm] = [mm]\vektor{n \\ k}[/mm]
>
> => f= [mm]\bruch{1}{\bruch{n!}{k!(n-k)!}}[/mm] =
> [mm](\bruch{n!}{k!(n-k)!})^-1[/mm]
Hmm. Bist Du denn sicher, daß hierbei ganze Zahlen rauskommen als Anzahl der Bahnen?
LG
Karsten
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:15 Di 15.05.2007 | | Autor: | Maren88 |
Hey,
schön, dass wenigstens der Anfang stimmt
>
> > weiterhin hab ich mir überlegt:
> >
> > k! * f = [mm]\bruch{n!}{(n-k)!}[/mm] * [mm](k!)^{-1}[/mm]
> > =>
> > k! * f = [mm]\bruch{n!}{(n-k)!}[/mm] * [mm]\bruch{1}{(k)!}[/mm]
> > =>
> > k! * f = [mm]\bruch{n!}{k!(n-k)!}[/mm] = [mm]\vektor{n \\ k}[/mm]
> >
> > => f= [mm]\bruch{1}{\bruch{n!}{k!(n-k)!}}[/mm] =
> > [mm](\bruch{n!}{k!(n-k)!})^-1[/mm]
>
> Hmm. Bist Du denn sicher, daß hierbei ganze Zahlen
> rauskommen als Anzahl der Bahnen?
ui, stimmt, das geht ja gar nich, da kommt ja für jeden Nenner, der größer als 1 ist, eine Zahl aus [mm] \IQ [/mm] raus.. 1/2 Bahnen wär ja voll der Schwachsinn ^^
also ist doch das [mm] \vektor{n \\ k} [/mm] die Anzahl der Bahnen. aber dann muss ich f doch gar nich ausrechnen.. oder doch?
schonmal Danke!!
Gruß Maren
|
|
|
| |
|
Schau mal auf meine zweite Antwort auf Deine Frage.
Gruß
Karsten
|
|
|
| |
|
Ich möchte mal folgenden Ansatz zur Diskussion stellen. Er ist Deinem sehr ähnlich, Maren.
Seien f,g [mm] \in [/mm] Inj(n,k) und [mm]\sigma \in Sym_k[/mm]. Dann gilt:
[mm]\sigma f = \sigma g \gdw f \circ \sigma^{-1} = g \circ \sigma^{-1} \gdw f \circ \sigma^{-1} \circ \sigma = g \circ \sigma^{-1} \circ \sigma \gdw f=g[/mm]
Also müßte [mm]Sym_k \* f =Sym_k \* g \gdw f=g[/mm] gelten. Für verschiedene f,g sind deren Bahnen also auch verschieden. die Bahnen bilden die gesuchten Äquivalenzklassen. Es gibt dann
[mm]|Sym_k \* Inj(n,k)| = |Sym_k| * |Inj(n,k)| = k! \bruch {n!}{(n-k)!}[/mm]
Bahnen bzw. Äquivalenzklassen.
LG
Karsten
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:59 Di 15.05.2007 | | Autor: | Maren88 |
> Ich möchte mal folgenden Ansatz zur Diskussion stellen. Er
> ist Deinem sehr ähnlich, Maren.
>
> Seien f,g [mm]\in[/mm] Inj(n,k) und [mm]\sigma \in Sym_k[/mm]. Dann gilt:
>
> [mm]\sigma f = \sigma g \gdw f \circ \sigma^{-1} = g \circ \sigma^{-1} \gdw f \circ \sigma^{-1} \circ \sigma = g \circ \sigma^{-1} \circ \sigma \gdw f=g[/mm]
>
> Also müßte [mm]Sym_k \* f =Sym_k \* g \gdw f=g[/mm] gelten. Für
> verschiedene f,g sind deren Bahnen also auch verschieden.
> die Bahnen bilden die gesuchten Äquivalenzklassen.
ok, das hab ich soweit verstanden. danke!
Es gibt
> dann
>
> [mm]|Sym_k * Inj(n,k)| = |Sym_k| \* |Inj(n,k)| = k! \bruch {n!}{(n-k)!}[/mm]
>
> Bahnen bzw. Äquivalenzklassen.
>
wenn das stimmt, wozu wird dann in der Aufgabenstellung gesagt, dass [mm] \sigma [/mm] f = f [mm] \circ \sigma^{-1} [/mm] ?
müsste es denn nicht eigentlich:
|Inj(n,k) [mm] Sym_k| [/mm] = [mm] |(Sym_k)^{-1}| [/mm] * |(Inj(n,k))| = [mm] \bruch{1}{k!} \bruch [/mm] {n!}{(n-k)!}
heißen?
Gruß Maren
|
|
|
| |
|
> wenn das stimmt, wozu wird dann in der Aufgabenstellung
> gesagt, dass [mm]\sigma[/mm] f = f [mm]\circ \sigma^{-1}[/mm] ?
>
> müsste es denn nicht eigentlich:
> |Inj(n,k) [mm]Sym_k|[/mm] = [mm]|(Sym_k)^{-1}|[/mm] * |(Inj(n,k))| =
> [mm]\bruch{1}{k!} \bruch[/mm] {n!}{(n-k)!}
>
> heißen?
Was ist denn [mm]Sym_k^{-1}[/mm]? Ist das gleich [mm]\{\sigma^{-1} | \sigma \in Sym_k\}[/mm]? Das wäre aber gleich [mm]Sym_k[/mm].
Grüße
Karsten
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:32 Di 15.05.2007 | | Autor: | Maren88 |
vielleicht müsste man auch [mm] (|Sym_k|)^{-1} [/mm] schreiben.. ich dachte das ergibt dann [mm] \bruch{1}{k!} [/mm] ..
und dann wäre
[mm] \bruch{1}{k!} [/mm] * [mm] \bruch [/mm] {n!}{(n-k)!} = [mm] \bruch [/mm] {n!}{k!*(n-k)!} = [mm] \vektor{n \\ k}
[/mm]
die Anzahl der Bahnen..
|
|
|
| |
|
So, Maren, ich versuch's nochmal. Meine Formel scheint nicht ganz richtig gewesen zu sein.
Überlegen wir mal zunächst, was [mm] \sigma [/mm] f bedeutet. [mm] \sigma [/mm] soll wie ein Operator auf f wirken, ganz ähnlich wie man [mm] \integral [/mm] f schreibt. Da wäre das Integral der Operator auf f. Es ist [mm](\sigma f)(x) = (f \circ \sigma^{-1})(x) = f(\sigma^{-1}(x))[/mm] für alle x [mm] \in [/mm] K.
Was macht dieses [mm]\sigma^{-1}[/mm]? Es liefert zu einer gegebenen Funktion [mm]f:K \to N[/mm] eine Permutation der Argumente aus {1, ... k} und damit eine Permutation der Funktionswerte aus {1, ... n}. Ist z.B. [mm]f:\{1,2,3\} \to \{1,2,3,4\}[/mm] mit f(1) = 1, f(2) = 3 und f(3) = 4 und ist z.B.
[mm]\sigma = \pmat{ 1 & 2 & 3 \\ 2 & 1 & 3} \Rightarrow \sigma^{-1} = \pmat{ 1 & 2 & 3 \\ 2 & 1 & 3}[/mm]
dann haben wir
[mm](\sigma f)(1) = (f \circ \sigma^{-1})(1) = f(2) = 3[/mm]
[mm](\sigma f)(2) = (f \circ \sigma^{-1})(2) = f(1) = 1[/mm]
[mm](\sigma f)(3) = (f \circ \sigma^{-1})(3) = f(3) = 4[/mm]
Wir bekommen damit eine andere Funktion [mm] g=(\sigma [/mm] f) mit g(1) = 3, g(2) = 1 und g(3) = 4, die ebenfalls injektiv ist. Die Menge
[mm]Sym_k \* f = \{ \sigma f | \sigma \in Sym_k\}[/mm]
enthält alle zu einer vorgegebenen Funktion f möglichen "Permutationsfunktionen", also solche wie g. Und das sind genau k!, denn die k Argumente von f lassen sich auf genau k! Arten permutieren.
Die [mm]Sym_k \* f [/mm], also die Bahnen, sind Äquivalenzklassen und bilden eine Partition von Inj(n,k). Jede Bahn enthält k! Elemente von insgesamt |Inj(n,k)| Elementen. D.h. wir haben
[mm]\bruch {|Inj(n,k)|} {k!} = \bruch {n!} {k!(n-k)!} = \vektor{n \\ k}[/mm]
Äquivalenzklassen.
Jetzt haben wir's! Und auch mit 'ner richtig guten Erklärung.
Liebe Grüße
Karsten
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:34 Di 15.05.2007 | | Autor: | Maren88 |
Hey,
super, vielen Dank für die ausführliche Erklärung!
Lieber Gruß
Maren
|
|
|
|
