Gleich viele ungerade wie gerade Permutationen

28.12.2024, 20:35

KonverDiv

Gleich viele ungerade wie gerade Permutationen

Hallo,

in einem alten Beitrag zum Thema "Gleich viele ungerade wie gerade Permutationen" hatte @Elvis die Idee gehabt, zu zeigen, dass mit $\begin{eqnarray*} \sigma \mapsto (12)\sigma \end{eqnarray*}$ eine Bijektion vorliegt. Ich bin darüber gestolpert und wollte das etwas allgemeiner formulieren.

Wir wollen zeigen: Die Anzahl an geraden Permutationen entspricht der Anzahl an ungeraden Permutationen.

Mein Ansatz: Sei $\begin{eqnarray*} A_n \end{eqnarray*}$ die Menge der geraden Permutationen von $\begin{eqnarray*} S_n \end{eqnarray*}$ und sei $\begin{eqnarray*} B_n \in S_n \setminus A_n \end{eqnarray*}$ die Menge der ungeraden Permutationen, sei weiter $\begin{eqnarray*} \pi \in B_n \end{eqnarray*}$ eine Transposition, dann zeigen wir $\begin{eqnarray*} f: A_n \rightarrow B_n \end{eqnarray*}$ definiert durch $\begin{eqnarray*} f(a) = \pi a \end{eqnarray*}$ mit $\begin{eqnarray*} a \mapsto \pi a \end{eqnarray*}$ ist eine Bijektion.

Wir zeigen $\begin{eqnarray*} f \end{eqnarray*}$ ist injektiv. Sei $\begin{eqnarray*} f(a) = f(a') \end{eqnarray*}$ dann folgt $\begin{eqnarray*} \pi a = \pi a' \end{eqnarray*}$ wir multiplizieren mit $\begin{eqnarray*} \pi \end{eqnarray*}$ und erhalten so $\begin{eqnarray*} a = a' \end{eqnarray*}$ , weil die Transposition selbstinvers ist, wodurch die Injektivität gezeigt ist.

Wir zeigen $\begin{eqnarray*} f \end{eqnarray*}$ ist surjektiv. Sei $\begin{eqnarray*} b \in B_n \end{eqnarray*}$ (ungerade Permutation), wir zeigen, dass es ein $\begin{eqnarray*} a \in A_n \end{eqnarray*}$ gibt, so dass $\begin{eqnarray*} f(a) = b \end{eqnarray*}$ gilt. Wir setzen $\begin{eqnarray*} a = \pi b \in A_n \end{eqnarray*}$ (ist eine gerade Permutation), dann ist $\begin{eqnarray*} f(a) = f(\pi b) = \pi \pi b = b \in B_n \end{eqnarray*}$ , was zu zeigen war.

Die Bijektion zwischen $\begin{eqnarray*} A_n \end{eqnarray*}$ und $\begin{eqnarray*} B_n \end{eqnarray*}$ impliziert nun, dass für die Kardinalität gilt $\begin{eqnarray*} |A_n| = |B_n| \end{eqnarray*}$ .

Geht das so? verwirrt

Ich wünsche ALLEN Helfern hier, ein schönes Weihnachten gehabt zu haben und einen guten Rutsch!

28.12.2024, 21:49

Elvis

Auf diesen Beitrag antworten »

Das geht so. Für die Injektivitaet musst du auch von links mit $\begin{eqnarray*} \pi \end{eqnarray*}$ multiplizieren. Damit hast du $\begin{eqnarray*} \frac {n\cdot(n+1)}2 \end{eqnarray*}$ Bijektionen. Die eine mit $\begin{eqnarray*} \pi=(12) \end{eqnarray*}$ genügt, weil zwei Mengen genau dann bijektiv sind, wenn eine bijektive Abbildung zwischen ihnen existiert.
Guten Rutsch und ein gutes neues Jahr. Bleib gesund und fleißig.

Nachtrag. Offensichtlich ist die Aussage für $\begin{eqnarray*} S_1 \end{eqnarray*}$ falsch.

04.01.2025, 12:46

KonverDiv

Auf diesen Beitrag antworten »

Hallo Elvis, vielen lieben Dank für deine Hilfe und deine lieben Worte! Blumen

Vielleicht sollten wir festhalten $\begin{eqnarray*} n \geq 2 \end{eqnarray*}$ . Eine weitere Frage ist, warum sind es $\begin{eqnarray*} \frac{n(n+1)}{2} \end{eqnarray*}$ Bijektionen? In $\begin{eqnarray*} S_n \end{eqnarray*}$ sind doch $\begin{eqnarray*} n! \end{eqnarray*}$ Permutationen vorhanden, also haben wir $\begin{eqnarray*} |A_n| = \frac{n!}{2} \end{eqnarray*}$ gerade und $\begin{eqnarray*} |B_n| = \frac{n!}{2} \end{eqnarray*}$ ungerade. Diese Bijektion, die wir oben allgemein definiert hatten, funktioniert ja für ein beliebiges ungerades Element aus $\begin{eqnarray*} B_n \end{eqnarray*}$ , es war ja $\begin{eqnarray*} \pi \in B_n \end{eqnarray*}$ , ich würde daher sagen, dass es $\begin{eqnarray*} \frac{n!}{2} \end{eqnarray*}$ Bijektionen oder Bijektive Abbildungen gibt?

04.01.2025, 14:20

Elvis

Auf diesen Beitrag antworten »

Ich hatte nur an Linksmultiplikation mit Transpositionen gedacht. Man könnte auch von rechts multiplizieren. Nun weiß ich nicht, ob alle Bijektionen, die die Menge der geraden und der ungeraden Permutationen vertauschen, paarweise verschieden sind. Ich habe auf die Schnelle nicht mal eine Idee, wie man das untersuchen könnte ... interessante Frage.
Nachtrag: Ich schätze, es gibt $\begin{eqnarray*} (\frac {n!}2)! \end{eqnarray*}$ solche Bijektionen.

04.01.2025, 15:44

IfindU

Auf diesen Beitrag antworten »

@Elvis Zwei Fakultäten wirken einen Hauch zu viel Augenzwinkern

Zur Links- vs. Rechtsmultiplikation:

Seien $\begin{eqnarray*} \tau, \tau' \end{eqnarray*}$ zwei Transitionen und $\begin{eqnarray*} f(a) = \tau a \end{eqnarray*}$ und $\begin{eqnarray*} f'(a) = a \tau' \end{eqnarray*}$ für alle $\begin{eqnarray*} a \in S_n \end{eqnarray*}$ . Um $\begin{eqnarray*} f= f' \end{eqnarray*}$ zu widerlegen, reicht es geeignete $\begin{eqnarray*} a \end{eqnarray*}$ mit $\begin{eqnarray*} f(a) \neq f'(a) \end{eqnarray*}$ zu finden.

Nehmen wir $\begin{eqnarray*} a = \tau \end{eqnarray*}$ , so ist $\begin{eqnarray*} f(a)= \tau \tau =1 \end{eqnarray*}$ und $\begin{eqnarray*} f'(a) = \tau \tau' \end{eqnarray*}$ . D.h. $\begin{eqnarray*} \tau = \tau' \end{eqnarray*}$ ist schon einmal gesetzt. Jetzt brauchen wir ein paar Elemente mehr. OBdA ist $\begin{eqnarray*} \tau = (12) \end{eqnarray*}$ . Nehmen wir jetzt $\begin{eqnarray*} a = (123) \end{eqnarray*}$ ist $\begin{eqnarray*} f(a) = (12)(123) = (132) \end{eqnarray*}$ während $\begin{eqnarray*} f'(a) = (123)(12) = (321) \end{eqnarray*}$ wenn ich mich nicht vertue.

Da es wie Elvis sagte $\begin{eqnarray*} \frac {n(n-1)}2 \end{eqnarray*}$ Transitionen gibt, und links sowie rechts andere Bijektionen liefern, gäbe es $\begin{eqnarray*} n(n-1) \end{eqnarray*}$ Bijektionen der Form $\begin{eqnarray*} f \end{eqnarray*}$ oder $\begin{eqnarray*} f' \end{eqnarray*}$ , falls $\begin{eqnarray*} n \geq 3 \end{eqnarray*}$ .

04.01.2025, 16:30

Elvis

Auf diesen Beitrag antworten »

Die $\begin{eqnarray*} S_n \end{eqnarray*}$ hat $\begin{eqnarray*} n! \end{eqnarray*}$ Elemente. Die Hälfte davon soll bijektiv auf die andere Hälfte abgebildet werden. Da dachte ich mir, ich halte das Urbild fest und permutiere ganz einfach die Bildhälfte. Das gibt die zweite Fakultät, und das Ergebnis ist die Anzahl der Bijektionen von $\begin{eqnarray*} A_n \end{eqnarray*}$ auf $\begin{eqnarray*} S_n\backslash A_n \end{eqnarray*}$ . Ziemlich viele, aber KonverDiv wollte ja gerne mehr als eine, und das ist dann nicht mehr zu überbieten. smile

04.01.2025, 16:48

IfindU

Auf diesen Beitrag antworten »

Ah, da war ich verwirrt. Ziehe Einwand zurück smile

04.01.2025, 19:44

KonverDiv

Auf diesen Beitrag antworten »

Zitat:

Original von Elvis
Die $\begin{eqnarray*} S_n \end{eqnarray*}$ hat $\begin{eqnarray*} n! \end{eqnarray*}$ Elemente. Die Hälfte davon soll bijektiv auf die andere Hälfte abgebildet werden. Da dachte ich mir, ich halte das Urbild fest und permutiere ganz einfach die Bildhälfte. Das gibt die zweite Fakultät, und das Ergebnis ist die Anzahl der Bijektionen von $\begin{eqnarray*} A_n \end{eqnarray*}$ auf $\begin{eqnarray*} S_n\backslash A_n \end{eqnarray*}$ . Ziemlich viele, aber KonverDiv wollte ja gerne mehr als eine, und das ist dann nicht mehr zu überbieten. smile

Ah, okay! danke für die Erklärung!

04.01.2025, 19:55

Elvis

Auf diesen Beitrag antworten »

Gern geschehen. Kurz nachdenken war leichter und ging schneller als am Beispiel $\begin{eqnarray*} S_7 \end{eqnarray*}$ die Bijektionen aufzuschreiben. Augenzwinkern

Natürlich muss man vorher wissen, dass es eine Bijektion gibt, sonst muss man sich gar nicht die Mühe machen, alle Bijektionen zu suchen oder auch nur zu zählen. Das zeigt beispielhaft, wie stark der Begriff Bijektion ist.

Neue Frage »

Antworten »

Gleich viele ungerade wie gerade Permutationen

Verwandte Themen