Permutationsfunktion

 

Es sei $A$ eine endliche (abzählbare) Menge. Jede bijektive Abbildung $f: A \to A$ wird als eine Permutation von $A$ bezeichnet.

Da die Definitionsmenge und die Zielmenge der bijektiven Funktion $f: A \to A$ identisch sind, ist diese Funktion stets surjektiv (und somit bijektiv).

 

Beispiel:

 

Für $A = \{ 1, 2, 3, 4 \}$ sei eine Permutation von $A$ gegeben durch:

\[
f =
\begin{pmatrix}
1 & 2 & 3 & 4 \\
3 & 1 & 2 & 4
\end{pmatrix}
\]

Die Funktion $f: A \to A$ ist bijektiv.

Hierbei gilt:

\[
\begin{array}{c@{\quad}l}
f =
\begin{pmatrix}
1 & 2 & 3 & 4 \\
3 & 1 & 2 & 4
\end{pmatrix}
&
\begin{aligned}
&\rightarrow \text{Definitionsmenge}\\
&\rightarrow \text{Zielmenge (Wertebereich)}
\end{aligned}
\end{array}
\]

Es gilt: $f(1) = 3,\quad f(2) = 1,\quad f(3) = 2,\quad f(4) = 4$.

Da $f$ gegeben ist durch:
\[
f =
\begin{pmatrix}
1 & 2 & 3 & 4 \\
3 & 1 & 2 & 4
\end{pmatrix}
\]

lautet die zugehörige inverse Funktion (Umkehrfunktion):
\[
f^{-1} =
\begin{pmatrix}
1 & 2 & 3 & 4 \\
2 & 3 & 1 & 4
\end{pmatrix}
\]

 

Beispiel:

 

Gegeben sind die folgenden Permutationen auf der Menge $A = \{ 1, 2, 3, 4 \}$:

\[
f =
\begin{pmatrix}
1 & 2 & 3 & 4 \\
2 & 4 & 3 & 1
\end{pmatrix}
\quad\text{und}\quad
g =
\begin{pmatrix}
1 & 2 & 3 & 4 \\
4 & 3 & 1 & 2
\end{pmatrix}
\]

Wir bestimmen die zusammengesetzte Permutation $f \circ g^{-1}$.

Zuerst ermitteln wir die inverse Funktion $g^{-1}$:
\[
g^{-1} =
\begin{pmatrix}
1 & 2 & 3 & 4 \\
3 & 4 & 2 & 1
\end{pmatrix}
\]

Nun berechnen wir die einzelnen Funktionswerte der Verkettung:

\[
(f \circ g^{-1})(1) = f\bigl(g^{-1}(1)\bigr) \quad\text{mit}\quad g^{-1}(1) = 3 \quad\Rightarrow\quad f(3) = 3
\]

\[
(f \circ g^{-1})(2) = f\bigl(g^{-1}(2)\bigr) \quad\text{mit}\quad g^{-1}(2) = 4 \quad\Rightarrow\quad f(4) = 1
\]

\[
(f \circ g^{-1})(3) = f\bigl(g^{-1}(3)\bigr) \quad\text{mit}\quad g^{-1}(3) = 2 \quad\Rightarrow\quad f(2) = 4
\]

\[
(f \circ g^{-1})(4) = f\bigl(g^{-1}(4)\bigr) \quad\text{mit}\quad g^{-1}(4) = 1 \quad\Rightarrow\quad f(1) = 2
\]

Daraus ergibt sich das Gesamtergebnis:
\[
f \circ g^{-1} =
\begin{pmatrix}
1 & 2 & 3 & 4 \\
3 & 1 & 4 & 2
\end{pmatrix}
\]

 

Beispiel:

 

Auf der Menge $A = \{ a, b, c \}$ sind gegeben:

\[
f =
\begin{pmatrix}
a & b & c \\
c & a & b
\end{pmatrix},
\quad
g \circ f =
\begin{pmatrix}
a & b & c \\
b & a & c
\end{pmatrix}
\]

Wir suchen die Permutation $g$.

Aus den Abbildungen folgt schrittweise:
\[
f(a) = c \quad\text{und}\quad g\bigl(f(a)\bigr) = b \quad\Rightarrow\quad g(c) = b
\]

\[
f(b) = a \quad\text{und}\quad g\bigl(f(b)\bigr) = a \quad\Rightarrow\quad g(a) = a
\]

\[
f(c) = b \quad\text{und}\quad g\bigl(f(c)\bigr) = c \quad\Rightarrow\quad g(b) = c
\]

Daraus lässt sich die Funktion $g$ wie folgt aufstellen:
\[
g =
\begin{pmatrix}
a & b & c \\
a & c & b
\end{pmatrix}
\]

 

 

Wenn $s(A) = n$ gilt (die Mächtigkeit der Menge beträgt $n$), dann berechnet sich die Anzahl der möglichen Permutationsfunktionen (bijektiven Funktionen) $f : A \to A$ durch:
\[ P(n, n) = \frac{n!}{(n-n)!} = n! \]

 

AUFGABE 33

 

Wie viele der auf der Menge $A = \{1, 2, 3, 4\}$ definierten Funktionen besitzen **keine** Umkehrfunktion?

\[
\text{A) } 200 \quad
\text{B) } 232 \quad
\text{C) } 256 \quad
\text{D) } 276 \quad
\text{E) } 278
\]

 

Lösung:

 

Die Gesamtzahl aller möglichen Funktionen $f : A \to A$ beträgt: $4^4 = 256$.

Die Anzahl der Funktionen, die eine Umkehrfunktion besitzen – sprich alle bijektiven Permutationsfunktionen – beträgt: $4! = 24$.

Folglich ergibt sich die Anzahl der Funktionen, die keine Umkehrfunktion besitzen, durch die Subtraktion: $256 – 24 = 232$.

 

\(\textbf{Antwort: B} \)