Bahnen < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:28 Do 26.04.2007 | | Autor: | Moe007 |
| Aufgabe | Sei [mm] S_{n} [/mm] die symmetrische Gruppe und [mm] T_{n} [/mm] = P({1,...n}) die Menge der Untermengen von {1,...n}. Die Gruppe [mm] S_{n} [/mm] operiert auf [mm] T_{n}:
[/mm]
[mm] S_{n} \times T_{n} \to T_{n}, (\sigma,P) \mapsto \sigma(P)
[/mm]
Bestimme die Anzahl und Kardinalität der Bahnen sowie die Klassengleichung dieser Operation. |
Hallo,
ich habe bei dieser Aufgabe ein paar Probleme. Ich hoffe, dass mir jemand etwas weiter helfen kann.
Ich weiß, dass Bahnen so def. sind: G*x = {gx | g [mm] \in [/mm] G Gruppe} =: [mm] O_{x}
[/mm]
Ich habe zuerst versucht, die Bahnen aller Elemente zu bestimmen:
[mm] S_{n} [/mm] * k = m, wobei k,m [mm] \in T_{n} [/mm] sind.
Ich weiß nicht genau, ob das so stimmt.
Wie kann ich denn nun die Anzahl und Kardinalität der Bahnen bestimmen?
Als Klassengleichung habe ich [mm] |T_{n}| [/mm] = [mm] \summe_{r \in R} [S_{n} [/mm] : [mm] T_{n} [/mm] ] = [mm] \summe_{r \in R} |O_{r}| [/mm]
Da ich nicht weiß, wie ich die Kardinalität der Bahnen bestimmen soll, komm ich hier auch nicht weiter.
Ich hoffe, dass mir jemand helfen kann.
Das wäre super!! 
Viele Grüße,
Moe
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:01 Fr 27.04.2007 | | Autor: | statler |
Guten Morgen Moe!
Das ist ganz leicht, wenn man erstmal dieses ganze abstrakte Gestrüpp durchschaut hat.
[mm] T_{n} [/mm] ist doch die Potenzmenge einer endlichen Menge, ihre Mächtigkeit kann man ausrechnen.Wenn man es nicht weiß, kann man es auch für kleine Mengen mit 1, 2, 3 Elementen probieren und dann die Formel raten.
Jetzt die Bahnen: Welche Teilmenge kann ich durch eine Permutation auf eine andere abbilden? Da Permutationen bijektiv sind, müssen beide Mengen die gleiche Mächtigkeit haben. Aber man sieht sofort, daß das auch hinreicht. Ich nehme einfach eine Permutation, die auf den vorgegebenen Elementen das tut, was sie soll, und die anderen in Ruhe läßt. Also bilden für jedes k die k-elementigen Teilmengen eine Bahn. In der Kombinatorik lernt man, wie viele es davon gibt.
Und wenn man jetzt die Bahnengleichung hinschreibt, was du mal tun solltest, erhält man eine Formel, die eng mit dem Pascalschen Dreieck zusammenhängt.
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:20 Fr 27.04.2007 | | Autor: | Moe007 |
hallo statler,
danke für deine Hilfe! Ich habe versucht mit deiner Hilfe, die Aufgabe zu lösen. Hab aber leider noch nicht alles verstanden. Ich hoffe, du erklärst es mir.
Also die Mächtigkeit von [mm] T_{n} [/mm] ist [mm] 2^{n}. [/mm] Stimmt das so?
> Jetzt die Bahnen: Welche Teilmenge kann ich durch eine
> Permutation auf eine andere abbilden? Da Permutationen
> bijektiv sind, müssen beide Mengen die gleiche Mächtigkeit
> haben. Aber man sieht sofort, daß das auch hinreicht. Ich
> nehme einfach eine Permutation, die auf den vorgegebenen
> Elementen das tut, was sie soll, und die anderen in Ruhe
> läßt. Also bilden für jedes k die k-elementigen Teilmengen
> eine Bahn. In der Kombinatorik lernt man, wie viele es
> davon gibt.
Als Bahn habe ich [mm] S_{n} \times [/mm] {1,...k} = {1,...., k} für 1 [mm] \le [/mm] k [mm] \le [/mm] n
Ich bin mir unsicher, ob das stimmt. Dann wäre die Anzahl der Bahnen = k oder? Als Kardinalität habe ich [mm] \vektor{2^{n} \\ k}
[/mm]
> Und wenn man jetzt die Bahnengleichung hinschreibt, was du
> mal tun solltest, erhält man eine Formel, die eng mit dem
> Pascalschen Dreieck zusammenhängt.
Als Bahnengleichung habe ich: [mm] |T_{n}| [/mm] = [mm] 2^{n} [/mm] = [mm] \vektor{2^{n} \\ k} [/mm] * k
Ich hoffe, du hilfst mir weiter.
Danke schonmal
Viele Grüße,
Moe
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:34 Fr 27.04.2007 | | Autor: | statler |
Mahlzeit!
> Also die Mächtigkeit von [mm]T_{n}[/mm] ist [mm]2^{n}.[/mm] Stimmt das so?
![[ok]](/images/smileys/ok.gif "[ok]")
> > Jetzt die Bahnen: Welche Teilmenge kann ich durch eine
> > Permutation auf eine andere abbilden? Da Permutationen
> > bijektiv sind, müssen beide Mengen die gleiche Mächtigkeit
> > haben. Aber man sieht sofort, daß das auch hinreicht. Ich
> > nehme einfach eine Permutation, die auf den vorgegebenen
> > Elementen das tut, was sie soll, und die anderen in Ruhe
> > läßt. Also bilden für jedes k die k-elementigen Teilmengen
> > eine Bahn. In der Kombinatorik lernt man, wie viele es
> > davon gibt.
>
> Als Bahn habe ich [mm]S_{n} \times[/mm] {1,...k} = {1,...., k} für
> 1 [mm]\le[/mm] k [mm]\le[/mm] n
>
> Ich bin mir unsicher, ob das stimmt.
Tut es auch nicht! Nimm mal für 1 < k < n als Permutation die Vertauschung (k k+1). Dann ist (k k+1)({1,...,k}) = {1,...,k-1, k+1}. Die Bahn besteht aus allen k-elementigen Teilmengen! Der ganze Rest ist jetzt ein 'Folgefehler'.
> Dann wäre die Anzahl
> der Bahnen = k oder? Als Kardinalität habe ich
> [mm]\vektor{2^{n} \\ k}[/mm]
>
> > Und wenn man jetzt die Bahnengleichung hinschreibt, was du
> > mal tun solltest, erhält man eine Formel, die eng mit dem
> > Pascalschen Dreieck zusammenhängt.
>
> Als Bahnengleichung habe ich: [mm]|T_{n}|[/mm] = [mm]2^{n}[/mm] =
> [mm]\vektor{2^{n} \\ k}[/mm] * k
Mach einen neuen Anlauf!
Dieter
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:39 Fr 27.04.2007 | | Autor: | Moe007 |
Hallo statler,
vielen Dank für deine Hilfe!
>> > > Jetzt die Bahnen: Welche Teilmenge kann ich durch eine
> > > Permutation auf eine andere abbilden? Da Permutationen
> > > bijektiv sind, müssen beide Mengen die gleiche Mächtigkeit
> > > haben. Aber man sieht sofort, daß das auch hinreicht. Ich
> > > nehme einfach eine Permutation, die auf den vorgegebenen
> > > Elementen das tut, was sie soll, und die anderen in Ruhe
> > > läßt. Also bilden für jedes k die k-elementigen Teilmengen
> > > eine Bahn.
Was meinst du damit genau? Die vorgegebenen Elemente sind die k-elementigen Teilmengen von {1,...,n} für jedes k oder?
> > Als Bahn habe ich [mm]S_{n} \times[/mm] {1,...k} = {1,...., k} für
> > 1 [mm]\le[/mm] k [mm]\le[/mm] n
> >
> > Ich bin mir unsicher, ob das stimmt.
>
> Tut es auch nicht! Nimm mal für 1 < k < n als Permutation
> die Vertauschung (k k+1). Dann ist (k k+1)({1,...,k}) =
> {1,...,k-1, k+1}. Die Bahn besteht aus allen k-elementigen
> Teilmengen!
Ist [mm] S_{n} [/mm] * k = {1,...n} die Bahn?
Ich weiß nicht genau, wie ich die Bahn genau angeben muss, damit die Bahn alle k-elementigen Teilmengen umfasst.
Ich hoffe, du kannst es mir näher erläutern.
Danke,
Moe
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:54 Fr 27.04.2007 | | Autor: | statler |
Hi!
> > Also bilden für jedes k die k-elementigen Teilmengen
> > eine Bahn.
> Was meinst du damit genau? Die vorgegebenen Elemente sind
> die k-elementigen Teilmengen von {1,...,n} für jedes k
> oder?
Wie schreibe ich eine k-elementige Teilmenge von {1, ... , n} hin?
So z. B.: [mm] \{ r_{1}, ... , r_{k} \}
[/mm]
Eine andere wäre [mm] \{ s_{1}, ... , s_{k} \}
[/mm]
Warum liegen die in derselben Bahn?
Ich nehme als Permutation
[mm] \pmat{ r_{1} & ... & r_{k} \\ s_{1} & ... & s_{k} }
[/mm]
und hoffe, daß dir die Schreibweise geläufig ist.
Diese Permutation bildet die Menge mit den r's auf die Menge mit den s'en ab.
Wenn dir das noch zu abstrakt ist, nimm n = 4 und schreib mal alles hin.
Bis dann
Dieter
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:09 Fr 27.04.2007 | | Autor: | Moe007 |
Hallo Statler,
> > > Also bilden für jedes k die k-elementigen Teilmengen
> > > eine Bahn.
> > Was meinst du damit genau? Die vorgegebenen Elemente sind
> > die k-elementigen Teilmengen von {1,...,n} für jedes k
> > oder?
>
> Wie schreibe ich eine k-elementige Teilmenge von {1, ... ,
> n} hin?
> So z. B.: [mm]\{ r_{1}, ... , r_{k} \}[/mm]
> Eine andere wäre [mm]\{ s_{1}, ... , s_{k} \}[/mm]
>
> Warum liegen die in derselben Bahn?
> Ich nehme als Permutation
> [mm]\pmat{ r_{1} & ... & r_{k} \\ s_{1} & ... & s_{k} }[/mm]
> und
> hoffe, daß dir die Schreibweise geläufig ist.
> Diese Permutation bildet die Menge mit den r's auf die
> Menge mit den s'en ab.
> Wenn dir das noch zu abstrakt ist, nimm n = 4 und schreib
> mal alles hin.
ich hoffe, ich versteh das jetzt richtig.
Ich habe als Bahn nun: [mm] S_{n} [/mm] * { [mm] r_{1},....,r_{n} [/mm] } = { [mm] \sigma( [/mm] { [mm] r_{1},....,r_{n} [/mm] } ) | [mm] \sigma \in S_{n} [/mm] } = { [mm] s_{1},...,s_{n} [/mm] }
Stimmts so?
Dann ist die Kardinalität der Bahnen = k und die Anzahl der Bahnen [mm] \vektor{n \\ k} [/mm] oder?
Die Bahngleichung lautet bei mir: [mm] 2^{n} [/mm] = [mm] \vektor{n \\ k} [/mm] * k
Tut mir echt leid, dass ich bei der Aufgabe so auf dem Schlauch stehe....
Aber ich hoffe, dass das jetzt nicht wieder ganz falsch ist.
Viele Grüße,
Moe
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:47 So 29.04.2007 | | Autor: | statler |
Guten Tag Moe!
> > Wenn dir das noch zu abstrakt ist, nimm n = 4 und schreib
> > mal alles hin.
Es würde dir sehr helfen, wenn du auf diesen Vorschlag eingehst. Meinetwegen nimm n= 3, dann hat [mm] S_{3} [/mm] nur 6 Elemente, und ein DIN-A4-Blatt reicht dicke, um das alles hinzuschreiben.
> ich hoffe, ich versteh das jetzt richtig.
> Ich habe als Bahn nun: [mm]S_{n}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
* { [mm]r_{1},....,r_{n}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
} = {
> [mm]\sigma([/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
{ [mm]r_{1},....,r_{n}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
} ) | [mm]\sigma \in S_{n}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
} = {
> [mm]s_{1},...,s_{n}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
}
Hier hast du doch eine n-elementige Teilmenge genommen, und die wird durch jede Permutation aus S_{n} auf sich abgebildet. Das gibt eine Bahn mit einem Element.
> Stimmts so?
Nee, nicht für den allgemeinen Fall einer k-elementigen Teilmenge mit k < n.
> Dann ist die Kardinalität der Bahnen = k und die Anzahl der
> Bahnen [mm]\vektor{n \\ k}[/mm] oder?
Die Anzahl der Bahnen darf doch von k nicht abhängen, sondern muß eine Funktion von n sein. Und die Kardinalität der Bahnen stimmt so nicht.
> Die Bahngleichung lautet bei mir: [mm]2^{n}[/mm] = [mm]\vektor{n \\ k}[/mm] *
> k
Wenn du einfach mal Zahlen eingesetzt hättest (n=10, k=1), hättest du gemerkt, daß das Käse ist.
Ich wiederhole meinen Rat: Wenn es dir so zu abstrakt ist, und das ist offenbar der Fall, dann untersuch ein konkretes kleines Beispiel. Dann wird dir hier auch weiterhin geholfen.
Einen schönen Sonntag
Dieter
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:03 So 29.04.2007 | | Autor: | Moe007 |
Hallo statler
ich hab das gemacht, was du mir empfohlen hast.
Ich hab mal alle 6 Elemente von [mm] S_{3} [/mm] hingeschrieben:
[mm] S_{3} [/mm] = {(123), (213), (132), (321), (312), (231)}
und [mm] T_{3} [/mm] ist dann { {}, {1,2,3}, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}}, [mm] T_{3} [/mm] hat 8 Elemente.
Aber jetzt ist mir gar nicht mehr klar, was ich nun genau damit anfangen soll. Wie kann ich nun die Bahn angeben, und dann die Anzahl und Kardinalität bestimmen?
Ist die Bahn: [mm] S_{3} [/mm] * x = y, mit x,y [mm] \in T_{3}
[/mm]
Ich hoffe, du hilfst mir weiter.
Viele Grüße,
Moe007
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:26 So 29.04.2007 | | Autor: | Moe007 |
Hallo statler,
ich hab mir die [mm] S_{3} [/mm] Gruppe näher angeschaut, und hab folgendes gemacht:
Ich habe als Bahn [mm] S_{3} [/mm] * x = y , wobei x,y k-elementige Mengen sind [mm] \in T_{3}
[/mm]
Da Permutationen bijektiv sind, bilden {1}, {2}, {3} eine Bahn.
Alle 2-elementigen Mengen {1,2}, {2,3} {1,3} eine Bahn, alle 3-elementigen Mengen, hier nur {1,2,3} eine Bahn, und die leere menge eine Bahn.
Also habe ich insgesamt 4 Bahnen.
Kardinalität: Die 1-elementige Bahn hat Kard. 3, und 2-elementige Bahn hat die Kardinalität 3, die 3-elem. Bahn hat kard. 1, und die 0-elementige Bahn hat Kard. 1.
Dann erhalte für die Bahnengleichung: [mm] |T_{3}| [/mm] = [mm] 2^{3} [/mm] = 8 = 3 + 3+ 1 + 1
Stimmt das so?
Für allegemeines n habe ich das so gemacht:
[mm] |S_{n}| [/mm] = n!, [mm] |T_{n}| [/mm] = [mm] 2^{n}
[/mm]
Dann hat die 1-elementige Bahn hat Kard. n.
Die 2-elementige Bahn hat Kard [mm] \vektor{n \\ 2}
[/mm]
....
Die n-elementige Bahn hat Kard. 1.
Und die 0-elementige Bahn hat auch kard. 1.
Insgesamt hat man n+1 Bahnen.
Und die Bahnengleichung habe ich so: [mm] |T_{n}| [/mm] = [mm] 2^{n} [/mm] = [mm] \summe_{k=0}^{n} \vektor{n \\ k}
[/mm]
Stimmt das so?
Viele Grüße,
Moe
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 07:22 Mo 30.04.2007 | | Autor: | statler |
Guten Morgen Moe!
Dein Lösungsversuch ist perfekt, war das nicht ein schönes Erfolgserlebnis für den Sonntagnachmittag?
Die Bahnformel ist übrigens genau die binomische Formel für (1 + [mm] 1)^{n}.
[/mm]
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:21 Mo 30.04.2007 | | Autor: | Moe007 |
Hallo statler,
ja war ein tolles Gefühl. Wenn mans mal verstanden hat, ist es ganz einfach
Danke dir.
|
|
|
|
