Mathematik: Anzahl der Abbildungen $f$ mit $f^p = f^q$
Released by matroid on Fr. 13. Dezember 2019 21:45:02 [Statistics]
Written by Triceratops - 549 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)

Anzahl der Abbildungen $f$ mit $f^p=f^q$

Für feste natürliche Zahlen $n,p,q$ bestimmen wir die Anzahl der Abbildungen $f : \{1,\dotsc,n\} \to \{1,\dotsc,n\}$ mit $f^p = f^q$, wobei $f^p$ die $p$-fache Verkettung von $f$ sei. Wir leiten insbesondere für festes $p \geq 2$ und $q=1$ die erzeugende Funktion $\exp(\sum_{d ~\mid~ p-1} \frac{1}{d} (z \cdot \exp(z))^d)$ für die Anzahlen her. Am Ende zeigen wir eine alternative Herleitung auf, die mit kombinatorischen Spezies arbeitet. Das folgende Bild zeigt zum Beispiel eine Abbildung $f$ mit $f^6=f^2$.

<math>
\newcommand{\rdot}{\textcolor{red}{$\bullet$}}
\newcommand{\bdot}{\textcolor{blue}{$\bullet$}}
\begin{tikzpicture}[inner sep=0pt,>=latex]
\node (W1) at (0,1) {\bdot};
\node (W2) at (1,1.8) {\bdot};
\node (W3) at (2,1) {\bdot};
\node (W4) at (1,0.2) {\bdot};
\node (A1) at (-1.1,1) {\rdot};
\node (A2) at (-2,2) {\rdot};
\node (A3) at (-2,0) {\rdot};
\node (B1) at (3.2,2) {\rdot};
\node (B2) at (3.2,0) {\rdot};
\draw [blue,->] (W1) to (W2);
\draw [blue,->] (W2) to (W3);
\draw [blue,->] (W3) to (W4);
\draw [blue,->] (W4) to (W1);
\draw [red,->] (A1) to (W1);
\draw [red,->,bend right=10] (A2) to (A1);
\draw [red,->,bend left=10] (A3) to (A1);
\draw [red,->,bend left=10] (B1) to (W3);
\draw [red,->,bend right=10] (B2) to (W3);
\end{tikzpicture}</math>



Notation

Wir beschränken uns also zunächst einmal auf den Fall $q=1$. Seien $n,p \geq 0$. Sei $a_{n,p}$ die Anzahl der Abbildungen $f : [n] \to [n]$ mit $f^p = f$, wobei $[n] = \{1,\dotsc,n\}$. Wir werden öfters flexibler sein müssen und anstelle von $[n]$ irgendeine Menge $X$ mit $n$ Elementen verwenden. Definieren wir also die Menge $\mathsf{A}_p(X) := \{f : X \to X : f^p = f\}$, so gilt $a_{n,p} = \# \mathsf{A}_p(X)$.

Wir könnten zwar theoretisch gleich den allgemeinen Fall behandeln, schauen uns aber erst ein paar Beispiele an, um auf gute Ideen zu kommen.

Die Fälle $p=0,1$

Es gilt $\mathsf{A}_0(X) = \{\mathrm{id}_X\}$, also $a_{n,0} = 1$ (OEIS/A000012).

Es gilt $\mathsf{A}_1(X) = \{f :X \to X\}$, also $a_{n,1} = n^n$ (OEIS/A000312).

Der Fall $p=2$

Zur Bestimmung von $\mathsf{A}_2(X)$ betrachten wir eine Abbildung $f : X \to X$ mit $f^2 = f$. Sei $B := \mathrm{Bild}(f)$. Es gilt zugleich $B = \{x \in X : f(x) = x\}$. Die Abbildung ist daher vollständig bestimmt durch die Einschränkung $h : X \setminus B \to B$, $h(x) := f(x)$. Ist umgekehrt $B \subseteq X$ irgendeine Teilmenge und $h : X \setminus B \to B$ irgendeine Abbildung, so können wir $f : X \to X$ definieren durch $f(x) = x$ falls $x \in B$ und $f(x) = h(x)$ falls $x \in X \setminus B$. Dann gilt $\mathrm{Bild}(f) = B$ und $f^2 = f$.

Wir haben damit eine Bijektion zwischen $\mathsf{A}_2(X)$ und der Menge der Tupel $(B,h)$ konstruiert, wobei $B \subseteq X$ eine Teilmenge und $h : X \setminus B \to B$ eine beliebige Abbildung ist. Wenn $k = \# B$, gibt es genau $\binom{n}{k}$ Möglichkeiten für $B$, und genau $k^{n-k}$ Möglichkeiten für $h$. Daraus folgt:

$\displaystyle (1) \qquad a_{n,2} = \sum_{k=0}^{n} \binom{n}{k} \cdot k^{n-k}.$

Weiter vereinfachen lässt sich diese Formel nicht (außer dass man die Summe auch bei $k=1$ starten kann, sofern $n>0$ ist).

Allerdings hat die exponentielle erzeugende Funktion eine besonders schöne Form:

$\begin{align*}
(2) \qquad \sum_{n=0}^{\infty} a_{n,2} \cdot \frac{z^n}{n!} &= \sum_{n=0}^{\infty} \sum_{k=0}^{n} \binom{n}{k} \cdot k^{n-k} \cdot \frac{z^n}{n!} \\
&=\sum_{k=0}^{\infty}\sum_{n=k}^{\infty} k^{n-k} \cdot \frac{z^{n}}{(n-k)! \cdot k!} \\
&=\sum_{k=0}^{\infty}\sum_{m=0}^{\infty} k^m \cdot \frac{z^{m+k}}{m! \cdot k!} \\
&=\sum_{k=0}^{\infty} \frac{z^k}{k!} \cdot \sum_{m=0}^{\infty} \frac{(k z)^m}{m!} \\
&=\sum_{k=0}^{\infty} \frac{z^k}{k!} \cdot \exp(k z) \\
&=\sum_{k=0}^{\infty} \frac{(z \cdot \exp(z))^k}{k!} \\
&=\exp(z \cdot \exp(z))
\end{align*}$

Die Folge $(a_{n,2})$ ist OEIS/A000248.


Der Fall $p=3$

Wir überlegen uns, dass es eine Bijektion zwischen $\mathsf{A}_3(X) = \{f : X \to X : f^3=f\}$ und der Menge der Tripel $(B,g,h)$ gibt, wobei $B \subseteq X$ eine Teilmenge, $g : B \to B$ eine Involution (also $g^2=\mathrm{id}_B$) und $h : X \setminus B \to B$ irgendeine Abbildung ist: Wenn $f : X \to X$ eine Abbildung mit $f^3=f$ ist, setzen wir $B := \mathrm{Bild}(f)$, und die Einschränkung $g : B \to B$ von $f$ erfüllt $g^2=\mathrm{id}_B$, weil ja $f^2 \circ f = \mathrm{id}_X \circ f$ gilt. Außerdem können wir $f$ zu einer Abbildung $h : X \setminus B \to B$ einschränken. Umgekehrt: Wenn ein Tripel $(B,g,h)$ gegeben ist, definieren wir $f : X \to X$ durch $f(x) = g(x)$ für $x \in B$ und $f(x) = h(x)$ sonst. Dann ist leicht $\mathrm{Bild}(f) = B$ und $f^3 = f$ zu sehen.

Wenn daher $i_k$ die Anzahl der Involutionen einer $k$-elementigen Menge bezeichnet, folgt

$\displaystyle (3) \qquad a_{n,3} = \sum_{k=0}^{n} \binom{n}{k} \cdot k^{n-k} \cdot i_k.$

Bei $i_n$ handelt es sich um eine bekannte Folge (siehe Wikipedia und OEIS/A000085) und es gibt mehrere Möglichkeiten der Berechnung. Die schnellste ist die Rekursionsformel

$(4) \qquad i_n = i_{n-1} + (n-1) \cdot i_{n-2}$

mit den Anfangswerten $i_0=i_1=1$, die man sich leicht überlegen kann (Tipp: man fixiere ein Element und mache eine Fallunterscheidung, ob es ein Fixpunkt der Involution ist oder nicht). Es gibt auch eine Summenformel: Eine Involution besteht aus disjunkten $2$-Zykeln, etwa $k$ Stück, sodass also $2k \leq n$ (zum Beispiel ist $(1 ~ 5) (2 ~ 3)$ eine Involution auf $[6]$). Es gibt $\binom{n}{2k}$ Möglichkeiten, die $2k$ beteiligten Elemente auszuwählen. Wählen wir irgendeine der $k!$ Anordnungen der $k$ Zykel, so gibt es $\binom{2k}{2}$ Möglichkeiten, den ersten Zykel zu bilden, und dann $\binom{2k-2}{2}$ Möglichkeiten, den zweiten Zykel zu bilden, usw. Es gibt dann insgesamt $\binom{2k}{2} \cdot \binom{2k-2}{2} \cdots \binom{2}{2} = \frac{(2k)!}{2^k}$ Möglichkeiten für die Zykel, wobei wir aber noch durch $k!$ teilen müssen, weil ihre Anordnung in der Permutation egal ist. So gelangt man zur Formel

$\displaystyle (5) \qquad i_n = \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n}{2k} \frac{(2k)!}{k! 2^k}.$

Diese kann man jetzt wiederum oben einsetzen und damit eine Formel für $a_{n,3}$ finden, die allerdings nicht sonderlich kompakt ist. Viel schöner und praktischer ist die exponentielle erzeugende Funktion der Folge $(a_{n,3})$. Wir werden sie gleich allgemeiner bestimmen und verraten schon einmal das Ergebnis:

$\displaystyle (6) \qquad \sum_{n=0}^{\infty} a_{n,3} \cdot \frac{z^n}{n!} = \exp(z \cdot \exp(z) + \tfrac{1}{2} \cdot z^2 \cdot \exp(z)^2)$.

Die Folge $(a_{n,3})$ ist OEIS/A060905. Zum Beispiel ist $a_{3,3}=19$, und die $19$ Abbildungen $f : \{1,2,3\} \to \{1,2,3\}$ (die wir als $3$-Tupel schreiben dürfen) mit $f^3=f$ lauten (geordnet nach aufsteigendem $\# \mathrm{Bild}(f)$)

$(1,1,1),(2,2,2),(3,3,3),(1,2,1),(1,2,2),(2,1,1),(2,1,2),(1,3,1),(1,3,3),(3,1,1),$
$(3,1,3),(2,3,2),(2,3,3),(3,2,2),(3,2,3),(1,2,3),(2,1,3),(1,3,2),(3,2,1).$


Der allgemeine Fall für $p$

Es gibt für allgemeines $p \geq 1$ eine Bijektion zwischen $\mathsf{A}_p(X) = \{f : X \to X : f^p=f\}$ und der Menge der Tripel $(B,g,h)$, wobei $B \subseteq X$ eine Teilmenge, $g : B \to B$ eine Abbildung mit $g^{p-1} = \mathrm{id}_B$ (die also für $p \geq 2$ eine Permutation ist) und $h : X \setminus B \to B$ irgendeine Abbildung ist. Das sieht man genauso wie im Spezialfall $p=3$. Ist daher $i_{n,p}$ die Anzahl der Permutationen $g : X \to X$ mit $g^p = \mathrm{id}_X$ (den Fall $p=2$ hatten wir oben), so folgt

$\displaystyle (7) \qquad a_{n,p} = \sum_{k=0}^{n} \binom{n}{k} \cdot k^{n-k} \cdot i_{k,p-1}.$

Wir müssen nun $i_{n,p}$ bestimmen. Wir nehmen $p \geq 1$ an. Schauen wir uns dazu eine Permutation $g : X \to X$ mit $g^p=\mathrm{id}_X$ an. Sie zerlegt sich in disjunkte Zykel, etwa $k$ Stück, deren Längen Teiler von $p$ sind. Seien $D_1,\dotsc,D_k \subseteq X$ die Mengen der Elemente von $X$, die bei diesen Zykeln beteiligt sind, und $d_i := \# D_i$. Es gilt also $d_1 + \cdots + d_k = n$ (wegen $D_1 \sqcup \cdots \sqcup D_k = X$) und $d_i \mid p$. Es gibt genau $\binom{n}{d_1,\dotsc,d_k} = \frac{n!}{d_1! \cdots d_k!}$ (Multinomialkoeffizient) Möglichkeiten, solche Teilmengen auszuwählen. Weiter gibt es für jede Menge $D_i$ genau $(d_i - 1)!$ Möglichkeiten, sie zu einem Zykel zu machen: Wenn zum Beispiel $D_i = \{1,\dotsc,d_i\}$ ist, so haben die Zykel die Form $(\pi(1) ~ \pi(2) ~ \cdots ~ \pi(d_i-1) ~ d_i)$ für irgendeine Permutation $\pi$ von $\{1,\dotsc,d_i-1\}$. Es gibt daher insgesamt

$\displaystyle \frac{n!}{d_1! \cdots d_k!} \cdot (d_1-1)! \cdots (d_k-1)! = \frac{n!}{d_1 \cdots d_k}$

Möglichkeiten für die $k$ Zykel. Weil ihre Reihenfolge in der Permutation allerdings keine Rolle spielt, müssen wir noch durch $k!$ teilen. Es folgt:

$\displaystyle (8) \qquad i_{n,p} = \sum_{\large d_1+\cdots+d_k=n ,~ d_i ~ \mid ~ p,~ k \geq 0} ~ \frac{n!}{k! d_1 \cdots d_k}$

Wir haben damit eine theoretische Berechnungsmöglichkeit für $i_{n,p}$ und damit für $a_{n,p}$ gefunden. Die Doppelfolge $(i_{n,p})$ ist OEIS/A008307. Die Doppelfolge $(a_{n,p})$ ist OEIS/A245501.

Zur Herleitung der exponentiellen erzeugenden Funktionen (für festes $p \geq 1$):

$\displaystyle\begin{align*}
(9) \qquad \sum_{n=0}^{\infty} i_{n,p} \cdot \frac{z^n}{n!} &= \sum_{n=0}^{\infty} ~ \sum_{\large d_1+\cdots+d_k=n ,~ d_i ~ \mid ~ p,~ k \geq 0} ~ \frac{1}{k! d_1 \cdots d_k} \cdot z^n\\
&= \sum_{k=0}^{\infty} \frac{1}{k!} ~ \sum_{\large d_i ~ \mid ~ p} ~ \frac{1}{d_1 \cdots d_k} \cdot z^{d_1+\cdots+d_k}\\
&= \sum_{k=0}^{\infty} \frac{1}{k!} \cdot \left(\sum_{d ~ \mid ~ p} \frac{z^d}{d}\right)^k \\
&= \exp\left(\sum_{d ~ \mid ~ p} \frac{z^d}{d}\right)
\end{align*}$

Es folgt (für festes $p \geq 2$):

$\displaystyle\begin{align*}
(10) \qquad \sum_{n=0}^{\infty} a_{n,p} \cdot \frac{z^n}{n!}
&= \sum_{n=0}^{\infty} \sum_{k=0}^{n} \binom{n}{k} \cdot k^{n-k} \cdot i_{k,p-1} \cdot \frac{z^n}{n!} \\
&= \sum_{k=0}^{\infty} i_{k,p-1} \cdot \sum_{n=k}^{\infty} k^{n-k} \cdot\frac{z^n}{k!(n-k)!} \\
&= \sum_{k=0}^{\infty} i_{k,p-1} \cdot \sum_{m=0}^{\infty} k^m \cdot \frac{z^{m+k}}{k!m!} \\
&= \sum_{k=0}^{\infty} i_{k,p-1} \cdot \sum_{m=0}^{\infty} \frac{(kz)^m}{m!} \cdot \frac{z^{k}}{k!} \\
&= \sum_{k=0}^{\infty} i_{k,p-1} \cdot \exp(kz) \cdot \frac{z^{k}}{k!} \\
&= \sum_{k=0}^{\infty} i_{k,p-1} \cdot \frac{(z \cdot \exp(z))^{k}}{k!} \\
&= \exp\left(\sum_{d ~ \mid ~ p-1} \frac{(z \cdot \exp(z))^d}{d}\right).
\end{align*}$


Rekursionsformel

Wir wollen hier noch (für festes $p \geq 1$) eine Rekursionsformel der Folge $(i_{n,p})_{n \geq 0}$ herleiten; den Spezialfall $p=2$ hatten wir bereits gesehen.

Betrachten wir eine Permutation $g : [n+1] \to [n+1]$ mit $g^p = \mathrm{id}$ und darin den Zyklus, der $n+1$ enthält. Er hat eine Länge $d$ mit $d \mid p$ und $d \leq n+1$. Es gibt $n \cdot (n-1) \cdot \dotsc (n-d+2) = (n)^{\underline{d-1}}$ Möglichkeiten (Fallende Faktorielle), diesen Zyklus festzulegen (man denke einfach an die Zykelschreibweise). Die restlichen Zykel bilden zusammen eine Permutation $h$ einer Menge von $n+1-d$ Elementen, die ebenfalls $h^p = \mathrm{id}$ erfüllt. Es folgt:

$\displaystyle (11) \qquad i_{n+1,p} = \sum_{\large d ~ \mid ~ p,~ d \leq n+1} (n)^{\underline{d-1}} \cdot i_{n+1-d,p}.$

Die Anfangswerte sind $i_{0,p}=i_{1,p}=1$. Interessant ist, dass man aus dieser Rekursionsformel erneut die erzeugende Funktion herleiten kann. Bezeichnen wir diese einmal mit $F(z) = \sum_{n \geq 0} i_{n,p} \cdot \frac{z^n}{n!}$, so erhalten wir durch Ableiten:

$\begin{align*}
F'(z) &= \sum_{n \geq 0} i_{n+1,p} \cdot \frac{z^n}{n!} \\
&= \sum_{n \geq 0} ~ \sum_{d ~ \mid ~ p,~ d \leq n+1} (n)^{\underline{d-1}} \cdot i_{n+1-d,p} \cdot \frac{z^n}{n!} \\
&= \sum_{d ~ \mid ~ p} ~ \sum_{n \geq d-1} i_{n+1-d,p} \cdot \frac{z^n}{(n+1-d)!} \\
&= \sum_{d ~ \mid ~ p} ~ \sum_{k \geq 0} i_{k,p} \cdot \frac{z^{k+d-1}}{k!} \\
&= \sum_{d ~ \mid ~ p} z^{d-1} \cdot F(z).
\end{align*}$

Es ist $F(z) = 1 + z + \dotsc$ invertierbar in $\IQ[[z]]$, daher können wir das umschreiben zu

$\displaystyle \frac{F'(z)}{F(z)} = \sum_{d ~ \mid ~ p} z^{d-1}.$

Formales Integrieren liefert nun das gewünschte Resultat

$\displaystyle (12) \qquad \log(F(z)) = \sum_{d ~ \mid ~ p} \frac{z^d}{d}.$


Kombinatorische Spezies

Es gibt eine elegante Herleitung der (hier stets exponentiellen) erzeugenden Funktionen von $(i_{n,p})$ und $(a_{n,p})$, die mit André Joyals Theorie der kombinatorischen Spezies arbeitet (siehe Wikipedia).

Eine kombinatorische Spezies ist ein Funktor $F : \mathcal{B} \to \mathcal{B}$, wobei $\mathcal{B}$ die Kategorie der endlichen Mengen und Bijektionen ist. Das bedeutet, dass jeder endlichen Menge $X$ eine endliche Menge $F(X)$ zugeordnet wird, deren Elemente wir als Strukturen auf $X$ der Spezies $F$ interpretieren. Außerdem wird jeder Bijektion $\sigma : X \to X'$ eine Bijektion $F(\sigma) : F(X) \to F(X')$ zugeordnet, die wir als Strukturtransport entlang von $\sigma$ interpretieren. Diese Bijektionen werden wir aber in den Beispielen niemals hinschreiben, weil sie offensichtlich sind. Ein (Iso-)Morphismus kombinatorischer Spezies $F \to F'$ ist eine Familie von (bijektiven) Abbildungen $F(X) \to F'(X)$, die mit den Strukturtransporten kompatibel sind.

Die erzeugende Funktion einer kombinatorischen Spezies $F$ ist definiert durch die formale Potenzreihe

$\displaystyle (13) \qquad F(z) := \sum_{n=0}^{\infty} \# F([n]) \cdot \frac{z^n}{n!}.$

Das einfachste Beispiel ist $\mathsf{E}$, die kombinatorische Spezies mit $\mathsf{E}(X) = \{X\}$. Die erzeugende Funktion ist $\mathsf{E}(z) = \exp(z)$. Ein anderes Beispiel ist $\mathsf{S}$, die kombinatorische Spezies der Permutationen mit $\mathsf{S}(X) := \{f : X \to X : f \text{ bijektiv}\}$. Die erzeugende Funktion ist $\mathsf{S}(z) = \sum_{n=0}^{\infty} z^n = \frac{1}{1-z}$.

Sei $p \geq 1$ fest. Wir betrachten die kombinatorische Spezies $\mathsf{C}_p$ (eine Unterspezies von $\mathsf{S}$), die einer endlichen Menge $X$ die Menge der Zykel der Länge $p$ auf $X$ zuordnet, also der Permutationen $\pi : X \to X$, für die es ein $x \in X$ gibt mit $X = \{\pi^k(x): k \in \IZ\}$, und außerdem $X$ genau $p$ Elemente hat. Für $\# X \neq p$ ist also $\mathsf{C}_p(X) = \emptyset$, und für $\# X = p$ ist $\# \mathsf{C}_p(X)=(p-1)!$, wie wir bereits oben gesehen haben. Die erzeugende Funktion ist daher

$\displaystyle (14) \qquad \mathsf{C}_p(z) = (p-1)! \frac{z^p}{p!} = \frac{z^p}{p}$.

Sei nun $\mathsf{I}_p$ die kombinatorische Unterspezies von $\mathsf{S}$, die einer endlichen Menge $X$ die Menge der Permutationen $g : X \to X$ mit $g^p=\mathrm{id}_X$ zuordnet. Es gibt dann einen Isomorphismus von kombinatorischen Spezies

$\displaystyle (15) \qquad \mathsf{I}_p \cong \mathsf{E} \circ \sum_{d ~ \mid ~ p} \mathsf{C}_d.$

Der Isomorphismus ist nichts weiter als die Zerlegung der Permutation in disjunkte Zykel. Denn die Komposition von kombinatorischen Spezies $F \circ G$ ist dadurch definiert, dass man die Grundmenge partitioniert, die Partitionsmenge mit einer $F$-Struktur versieht (wovon es für $F=\mathsf{E}$ aber nur eine gibt) und die Mengen in der Partition mit $G$-Strukturen versieht, in unserem Fall also mit Zykeln geeigneter Längen; die Summe von kombinatorischen Spezies ist außerdem über disjunkte Vereinigungen definiert. Diese Operationen vertragen sich gut mit erzeugenden Funktionen (das muss man sich einmal allgemein überlegen, und wir haben das oben im Prinzip nur in einem Spezialfall nachgerechnet), sodass wir aus dem obigen Isomorphismus die Gleichung

$\displaystyle (16) \qquad \mathsf{I}_p(z) = \mathsf{E}\left(\sum_{d ~ \mid ~ p} \mathsf{C}_p(z)\right) = \exp\left(\sum_{d ~ \mid ~ p} \frac{z^d}{d}\right)$

erhalten. Das ist die erzeugende Funktion der Folge $(i_{n,p})_{n \geq 0}$.

Kommen wir nun zur kombinatorischen Spezies $\mathsf{A}_p$ mit $\mathsf{A}_p(X) := \{f : X \to X : f^p=f\}$. Wir verwenden die kombinatorische Spezies $\mathsf{E}^{\bullet}$, die einer endlichen Menge $X$ einfach $X$ zuordnet. Eine $\mathsf{E}^{\bullet}$-Struktur auf $X$ ist also einfach die Wahl eines Elementes von $X$. Die erzeugende Funktion lautet

$\displaystyle (17) \qquad \mathsf{E}^{\bullet}(z) = \sum_{n=0}^{\infty} n \cdot \frac{z^n}{n!} = \sum_{n=1}^{\infty} \frac{z^n}{(n-1)!} = z \cdot \exp(z).$

Wir behaupten, dass es für $p \geq 2$ einen Isomorphismus von kombinatorischen Spezies gibt:

$(18) \qquad \mathsf{A}_p \cong \mathsf{I}_{p-1} \circ \mathsf{E}^{\bullet}.$

Sei dazu $f : X \to X$ mit $f^p = f$ gegeben. Dann ist $\mathcal{P} := \{f^*(x) : x \in \mathrm{Bild}(f)\}$ eine Partition von $X$, wobei $f^*(x) = \{u \in X : f(u) = x\}$ die Faser von $x$ sei. Wegen $f^p = f$ gilt für die Einschränkung $g' : \mathrm{Bild}(f) \to \mathrm{Bild}(f)$ von $f$ die Gleichung $g'^{p-1}=\mathrm{id}$. Die induzierte Permutation $g : \mathcal{P} \to \mathcal{P}$ mit $g(f^*(x)) := f^*(f(x))$ erfüllt dann ebenfalls $g^{p-1}=\mathrm{id}$. In jeder der Mengen $A=f^*(x)$ in $\mathcal{P}$ können wir ein Element auszeichnen, nämlich $e_A := f^{p-2}(x)$, weil für $x \in \mathrm{Bild}(f)$ ja $f^{p-1}(x)=x$ gilt. Wir haben damit eine Struktur der Spezies $\mathsf{I}_{p-1} \circ \mathsf{E}^{\bullet}$ auf $X$ beschrieben.

Sei umgekehrt eine Struktur der Spezies $\mathsf{I}_{p-1} \circ \mathsf{E}^{\bullet}$ auf $X$ gegeben. Das ist eine Partition $\mathcal{P}$ von $X$ zusammen mit einer Permutation $g : \mathcal{P} \to \mathcal{P}$, die $g^{p-1}=\mathrm{id}$ erfüllt, sowie ausgezeichneten Elementen $e_A \in A$ für alle $A \in \mathcal{P}$. Definiere nun die Abbildung $f : X \to X$ durch $f(x) := e_{g(A)}$, wenn $x \in A \in \mathcal{P}$ (die Menge $A$ ist eindeutig durch $x$ bestimmt, weil $\mathcal{P}$ eine Partition ist). Es gilt $e_{g(A)} \in g(A) \in \mathcal{P}$ und daher $f(f(x)) = e_{g(g(A))}$, usw. bis $f^p(x) = e_{g^p(A)} = e_{g(A)} = f(x)$. Dies zeigt $f^p=f$.

Die Konstruktionen sind zueinander invers: Starten wir mit $f$, konstruieren wie oben das Tripel $(\mathcal{P},g,e)$, so ist die daraus konstruierte Abbildung $f' : X \to X$ gegeben durch $f'(x) = e_{g(A)}$, wenn $x \in A \in \mathcal{P}$. Wenn etwa $A = f^*(y)$, folgt $f'(x)=e_{g(A)} = e_{f^*(f(y))} = f^{p-2}(f(y)) = f^{p-1}(y) = y = f(x)$. Dies zeigt $f'=f$. Starten wir umgekehrt mit einem Tripel $(\mathcal{P},g,e)$ und konstruieren daraus die Abbildung $ f : X \to X$ wie oben, so ist $\mathrm{Bild}(f) = \{e_A : A \in \mathcal{P}\}$, und die Mengen in der aus $f$ konstruierten Partition sind die Fasern $f^*(e_A) = g^{-1}(A)$ mit $A \in \mathcal{P}$. Die Partition ist also wieder $\mathcal{P}$. Die Permutation darauf ist gegeben durch $f^*(e_A) \mapsto f^*(f(e_A)) = f^*(e_{g(A)})$, also $g^{-1}(A) \mapsto A$, also $g$. Das ausgezeichnete Element in der Faser $f^*(e_A)$ ist $f^{p-2}(e_A) = e_{g^{p-2}(A)} = e_{g^{-1}(A)} = e_{f^*(e_A)}$, das passt ebenfalls.

Aus dem Isomorphismus $\mathsf{A}_p \cong \mathsf{I}_{p-1} \circ \mathsf{E}^{\bullet}$ folgt nun für die erzeugende Funktion

$\displaystyle (19) \qquad \mathsf{A}_p(z) = \mathsf{I}_{p-1}(\mathsf{E}^{\bullet}(z)) = \exp\left(\sum_{d ~ \mid ~ p-1} \frac{(z \cdot \exp(z))^d}{d}\right).$

Das ist die erzeugende Funktion der Folge $(a_{n,p})_{n \geq 0}$.


Der allgemeine Fall für $q$

Noch allgemeiner kann man sich fragen, wieviele Abbildungen $f : X \to X$ es mit $f^p=f^q$ gibt, wobei $p > q$ zwei feste natürliche Zahlen sind und $\#X = n$. Sei $a_{n,p,q}$ ihre Anzahl. Wir haben oben die Fälle $q=0$ (es gilt $a_{n,p,0} = i_{n,p}$) und $q=1$ (es gilt $a_{n,p,1} = a_{n,p}$) betrachtet.

Wir arbeiten wieder mit kombinatorischen Spezies, um die erzeugende Funktion möglichst effizient auszurechnen. Wir lassen zunächst die Bedingung $f^p=f^q$ außer Acht und betrachten irgendeine Abbildung $f : X \to X$. Sie liefert einen gerichteten Graphen mit Knotenmenge $X$ und Kanten $x \to f(x)$ für $x \in X$. Diese Graphen zeichnen sich dadurch aus, dass von jedem Knoten genau eine Kante abgeht.

Hier ein Beispiel (mit $n=22$):

<math>
\begin{tikzpicture}[inner sep=0pt,>=latex]
u
\node (A1) at (0,1) {$\bullet$};
\node (A2) at (0,2) {$\bullet$};
\node (A3) at (0,3) {$\bullet$};
\node (B) at (1,2) {$\bullet$};
\node (C) at (2,2) {$\bullet$};
\node (D) at (3,3) {$\bullet$};
\node (E) at (4,2) {$\bullet$};
\node (F) at (3,1) {$\bullet$};
\node (G) at (5,1) {$\bullet$};
\draw [->] (A1) to (B);
\draw [->] (A2) to (B);
\draw [->] (A3) to (B);
\draw [->] (B) to (C);
\draw [->] (C) to (D);
\draw [->] (D) to (E);
\draw [->] (E) to (F);
\draw [->] (F) to (C);
\draw [->] (G) to (E);

\node (H) at (6,2) {$\bullet$};
\node (I) at (7,2) {$\bullet$};
\node (J) at (9,2) {$\bullet$};
\draw [->] (H) to (I);
\draw [->, bend left] (I) to (J);
\draw [->, bend left] (J) to (I);

\node (K) at (11,1) {$\bullet$};
\node (L) at (13,1) {$\bullet$};
\node (M) at (12,2) {$\bullet$};
\node (N) at (10,2) {$\bullet$};
\node (O) at (10,3) {$\bullet$};
\node (P) at (14,2) {$\bullet$};
\node (Q) at (15,3) {$\bullet$};
\node (R) at (14,3) {$\bullet$};
\node (S) at (14,1) {$\bullet$};
\node (T) at (15,2) {$\bullet$};
\draw [->] (K) to (L);
\draw [->] (L) to (M);
\draw [->] (M) to (K);
\draw [->] (N) to (K);
\draw [->] (O) to (N);
\draw [->] (P) to (L);
\draw [->] (Q) to (P);
\draw [->] (R) to (P);
\draw [->] (S) to (L);
\draw [->] (T) to (S);

\end{tikzpicture}
</math>

In diesem Beispiel gibt es drei Kreise (mit den Längen $4,2,3$), und jeder Knoten außerhalb der Kreise hat genau einen Weg zu einem dieser Kreise. Markieren wir einmal den ersten Kreisknoten, auf dem sie treffen, und ignorieren die Kanten in den Kreisen. Wir berücksichtigen dabei auch die Kreisknoten, bei denen keine Knoten außerhalb der Kreise antreffen:

<math>
\begin{tikzpicture}[inner sep=0pt,>=latex]

\node (A1) at (0,1) {$\bullet$};
\node (A2) at (0,2) {$\bullet$};
\node (A3) at (0,3) {$\bullet$};
\node (B) at (1,2) {$\bullet$};
\node (C) at (2,2) {$\bullet$};
\draw (2,2) circle (1ex);
\node (D) at (3,3) {$\bullet$};
\draw (3,3) circle (1ex);
\node (E) at (4,2) {$\bullet$};
\draw (4,2) circle (1ex);
\node (F) at (3,1) {$\bullet$};
\draw (3,1) circle (1ex);
\node (G) at (5,1) {$\bullet$};
\draw [->] (A1) to (B);
\draw [->] (A2) to (B);
\draw [->] (A3) to (B);
\draw [->] (B) to (C);
\draw [->, color=lightgray] (C) to (D);
\draw [->, color=lightgray] (D) to (E);
\draw [->, color=lightgray] (E) to (F);
\draw [->, color=lightgray] (F) to (C);
\draw [->] (G) to (E);

\node (H) at (6,2) {$\bullet$};
\node (I) at (7,2) {$\bullet$};
\draw (7,2) circle (1ex);
\node (J) at (9,2) {$\bullet$};
\draw (9,2) circle (1ex);
\draw [->] (H) to (I);
\draw [->, bend left, color=lightgray] (I) to (J);
\draw [->, bend left, color=lightgray] (J) to (I);

\node (K) at (11,1) {$\bullet$};
\draw (11,1) circle (1ex);
\node (L) at (13,1) {$\bullet$};
\draw (13,1) circle (1ex);
\node (M) at (12,2) {$\bullet$};
\draw (12,2) circle (1ex);
\node (N) at (10,2) {$\bullet$};
\node (O) at (10,3) {$\bullet$};
\node (P) at (14,2) {$\bullet$};
\node (Q) at (15,3) {$\bullet$};
\node (R) at (14,3) {$\bullet$};
\node (S) at (14,1) {$\bullet$};
\node (T) at (15,2) {$\bullet$};
\draw [->, color=lightgray] (K) to (L);
\draw [->, color=lightgray] (L) to (M);
\draw [->, color=lightgray] (M) to (K);
\draw [->] (N) to (K);
\draw [->] (O) to (N);
\draw [->] (P) to (L);
\draw [->] (Q) to (P);
\draw [->] (R) to (P);
\draw [->] (S) to (L);
\draw [->] (T) to (S);

\end{tikzpicture}
</math>

Hierbei handelt es sich offenbar um eine Menge von gewurzelten Bäumen; die Wurzeln sind die markierten Knoten. Die Kanten sind dabei in Richtung der Wurzel ausgerichtet.

Wenn wir andererseits nur die Kreise berücksichtigen, haben wir es offenbar mit einer Permutation der Wurzeln zu tun:

<math>
\begin{tikzpicture}[inner sep=0pt,>=latex]

\node (A1) at (0,1) {\textcolor{lightgray}{$\bullet$}};
\node (A2) at (0,2) {\textcolor{lightgray}{$\bullet$}};
\node (A3) at (0,3) {\textcolor{lightgray}{$\bullet$}};
\node (B) at (1,2) {\textcolor{lightgray}{$\bullet$}};
\node (C) at (2,2) {$\bullet$};
\node (D) at (3,3) {$\bullet$};
\node (E) at (4,2) {$\bullet$};
\node (F) at (3,1) {$\bullet$};
\node (G) at (5,1) {\textcolor{lightgray}{$\bullet$}};
\draw [->, color=lightgray] (A1) to (B);
\draw [->, color=lightgray] (A2) to (B);
\draw [->, color=lightgray] (A3) to (B);
\draw [->, color=lightgray] (B) to (C);
\draw [->] (C) to (D);
\draw [->] (D) to (E);
\draw [->] (E) to (F);
\draw [->] (F) to (C);
\draw [->, color=lightgray] (G) to (E);

\node (H) at (6,2) {\textcolor{lightgray}{$\bullet$}};
\node (I) at (7,2) {$\bullet$};
\node (J) at (9,2) {$\bullet$};
\draw [->, color=lightgray] (H) to (I);
\draw [->, bend left] (I) to (J);
\draw [->, bend left] (J) to (I);

\node (K) at (11,1) {$\bullet$};
\node (L) at (13,1) {$\bullet$};
\node (M) at (12,2) {$\bullet$};
\node (N) at (10,2) {\textcolor{lightgray}{$\bullet$}};
\node (O) at (10,3) {\textcolor{lightgray}{$\bullet$}};
\node (P) at (14,2) {\textcolor{lightgray}{$\bullet$}};
\node (Q) at (15,3) {\textcolor{lightgray}{$\bullet$}};
\node (R) at (14,3) {\textcolor{lightgray}{$\bullet$}};
\node (S) at (14,1) {\textcolor{lightgray}{$\bullet$}};
\node (T) at (15,2) {\textcolor{lightgray}{$\bullet$}};
\draw [->] (K) to (L);
\draw [->] (L) to (M);
\draw [->] (M) to (K);
\draw [->, color=lightgray] (N) to (K);
\draw [->, color=lightgray] (O) to (N);
\draw [->, color=lightgray] (P) to (L);
\draw [->, color=lightgray] (Q) to (P);
\draw [->, color=lightgray] (R) to (P);
\draw [->, color=lightgray] (S) to (L);
\draw [->, color=lightgray] (T) to (S);

\end{tikzpicture}
</math>

Was wir hier anhand des Beispiels gesehen haben, ist dass es für jede Abbildung $f : X \to X$ eine Partition $\mathcal{P}$ von $X$ gibt, wobei jede Menge $T \in \mathcal{P}$ die Knotenmenge eines gewurzelten Baumes ist, etwa mit Wurzel $w_T$, und sich außerdem $f$ zu einer Permutation der Wurzelmenge $W:=\{w_T : T \in \mathcal{P}\}$ einschränkt. Beweisen wir das allgemein:

Sei $X$ eine endliche Menge und $f : X \to X$ eine Abbildung. Wir nennen $w \in X$ zyklisch, wenn es ein $k>0$ gibt mit $f^k(w)=w$. Es sei $W$ die Menge der zyklischen Elemente. Offenbar beschränkt sich $f$ zu einer Abbildung $g : W \to W$. Wenn $w \in W$, etwa $f^k(w)=w$, dann ist $f^{k-1}(w) \in W$ ein Urbild unter $g$. Daher ist $g$ surjektiv und und damit bijektiv, also eine Permutation.

Für $w \in W$ sei $T_w \subseteq X$ die Menge der $x \in X$, für die entweder $x=w$ gilt, oder aber es ein $k>0$ gibt, sodass $f^k(x)=w$ gilt und $f^{k-1}(x)$ nicht zyklisch ist (insbesondere ist dann $x$ nicht zyklisch). Wir machen $T_w$ zur Knotenmenge eines gerichteten Graphen (den wir einfach ebenfalls mit $T_w$ bezeichnen): Die Kanten seien $x \to f(x)$ für $x \in T_w \setminus \{w\}$. Ist $x \in T_w \setminus \{w\}$, so gibt es genau einen Weg nach $x$, nämlich $x \to f(x) \to \cdots \to f^k(x)=w$, wenn $k$ minimal mit $f^k(x)=w$ gewählt ist. Also ist $T_w$ ein Baum. Wir legen $w$ als seine Wurzel fest.

Prüfen wir, dass $\mathcal{P} := \{T_w : w \in W\}$ eine Partition von $X$ ist: Ist $x \in X$, so gibt es zwei natürliche Zahlen $m>k$ mit $f^m(x)=f^k(x)$, weil $X$ endlich ist. Es ist also $f^k(m)$ zykisch. Wähle das kleinste $k$, für das $f^k(x)$ zyklisch ist. Wenn $k=0$, ist $x$ zyklisch und damit $x \in T_x$. Wenn $k>0$, dann ist $w := f^k(x)$ zyklisch, aber $f^{k-1}(x)$ ist es nicht, womit $x \in T_w$ gilt. Dies zeigt $X = \bigcup_{w \in W} T_w$. Die Zerlegung ist disjunkt, denn aus $x \in T_w$ folgt, dass $w = f^k(x)$, wobei $k$ die kleinste natürliche Zahl ist, sodass $f^k(x)$ zyklisch ist.

Die Permutation $g : W \to W$ können wir auch zu einer Permutation $g' : \mathcal{P} \to \mathcal{P}$ machen, indem wir die Bäume mit ihren Wurzeln identifizieren, also $g'(T_w) = T_{g(w)}$ setzen.

Wir können diese Konstruktion auch umkehren: Angenommen, es ist $\mathcal{P}$ eine Partition von $X$, deren Mengen $T \in \mathcal{P}$ jeweils die Knotenmengen von gewurzelten Bäumen sind, etwa mit Wurzel $w_T$, und es sei $g : W \to W$ eine Permutation der Wurzelmenge $W := \{w_T : T \in \mathcal{P}\}$. Wir können jeden gewurzelten Baum in Richtung der Wurzel ausrichten und damit als gerichteten Graphen sehen. Wir definieren nun eine Abbildung $f : X \to X$ wie folgt: Sei $x \in X$. Wähle den Baum $T \in \mathcal{P}$ mit $x \in T$. Wenn $x=w_T$ die Wurzel ist, sei $f(x) := g(x)$. Andernfalls sei $f(x)$ der Nachfolgerknoten von $x$ auf dem Weg von $x$ zur Wurzel $w_T$ im Baum $T$.

Man kann sich überlegen, dass diese beiden Konstruktionen zueinander invers sind; den Beweis lassen wir hier einmal weg, weil er "straight forward" ist.

Wir können diese Korrespondenz von oben sehr gut mit kombinatorischen Spezies einfangen: Es sei $\mathsf{END}$ die kombinatorische Spezies mit $\mathsf{END}(X) = \{f : X \to X\}$. Es sei $\mathsf{S} \subseteq \mathsf{END}$ die Unterspezies der Permutationen. Und schließlich sei $\mathsf{T}$ die kombinatorische Spezies der (beschrifteten) gewurzelten Bäume. Das heißt, $\mathsf{T}(X)$ ist die Menge der $(x,E)$ mit $x \in X$ und $E \subseteq P_2(X)$, für die der Graph $(X,E)$ ein Baum ist. Dann haben wir oben einen Isomorphismus kombinatorischer Spezies

$(20) \qquad \mathsf{END} \cong \mathsf{S} \circ \mathsf{T}$

beschrieben. (Aus diesem lässt sich übrigens wunderbar Cayleys Formel für die Anzahl der beschrifteten Bäume herleiten, aber das nur am Rande.)

Wir sind nun eigentlich an der Unterspezies $\mathsf{A}_{p,q} \subseteq \mathsf{END}$ interessiert, die aus den Abbildungen $f : X \to X$ besteht, für die $ f^p=f^q$ gilt, wobei $p>q$ feste natürliche Zahlen sind. Beschreiben wir also das Bild von $\mathsf{A}_{p,q}$ unter dem Isomorphismus $\mathsf{END} \cong \mathsf{S} \circ \mathsf{T}$:

Ist $f : X \to X$ mit $f^p=f^q$, so erfüllt die Permutation $g : W \to W$ der Wurzeln ebenfalls $g^p = g^q$, also $g^{p-q}=\mathrm{id}$. Außerdem hat jeder der Bäume $T_w$ eine Höhe $\leq q$, denn für $x \in X$ ist spätestens $f^q(x)$ zyklisch. Die Umkehrung gilt auch: Ist $f : X \to X$ eine Abbildung, erfüllt die Permutation $g : W \to W$ die Gleichung $g^{p-q}=\mathrm{id}$ und haben alle Bäume $T_w$ die Höhe $\leq q$, so gilt $f^p(x)=f^q(x)$. Denn für $x \in W$ folgt das aus $g^p(x)=g^q(x)$, und ansonsten ist wegen der Höhenbedingung $f^q(x)$ bereits die Wurzel des Baumes um $x$ oder ein Kreisknoten, also in jedem Fall $g^{p-q}(f^q(x)) = f^q(x)$ bzw. $f^p(x)=f^q(x)$.

Definieren wir daher die Unterspezies $\mathsf{T}_q \subseteq \mathsf{T}$ der gewurzelten Bäume der Höhe $\leq q$ und erinnern an die Notation $\mathsf{I}_k$ für die Spezies der Permutationen $g$ mit $g^k=\mathrm{id}$, so folgt

$(21) \qquad \mathsf{A}_{p,q} \cong \mathsf{I}_{p-q} \circ \mathsf{T}_q.$

Die Spezies $\mathsf{T}_q$ können wir rekursiv aufbauen: Es gilt $\mathsf{T}_0 \cong \mathsf{X}$ (das ist die Spezies, die nur Strukturen (und dann auch nur eine) auf einelementigen Mengen zulässt) sowie

$(22) \qquad \mathsf{T}_{q+1} \cong \mathsf{X} \cdot (\mathsf{E} \circ \mathsf{T}_q).$

Denn ein gewurzelter Baum der Höhe $\leq q+1$ besteht aus einer Wurzel und einer Partition der restlichen Knoten in gewurzelte Bäume der Höhe $\leq q$. Für die erzeugenden Funktionen gilt daher die Rekursionsformel

$\displaystyle (23) \qquad \mathsf{T}_0(z) = z,\quad \mathsf{T}_{q+1}(z) = z \cdot \exp(\mathsf{T}_q(z)).$

Man kann sie also für jedes feste $q$ konkret hinschreiben. Die OEIS-Einträge für $q=2,3,4$ lauten OEIS/A052512, OEIS/A052513, OEIS/A052514.

Der Isomorphismus $\mathsf{A}_{p,q} \cong \mathsf{I}_{p-q} \circ \mathsf{T}_q$ liefert nun endlich die gesuchte erzeugende Funktion:

$\displaystyle (24) \qquad \sum_{n=0}^{\infty} a_{n,p,q} \cdot \frac{z^n}{n!} = \mathsf{A}_{p,q}(z) = \exp\left(\sum_{d ~ \mid ~ (p-q)} \frac{\mathsf{T}_q(z)^d}{d}\right).$

Zum Beispiel ist

$(25) \qquad \mathsf{A}_{3,2}(z) = \exp(z \cdot \exp(z \cdot \exp(z))).$

Hier sind ein paar OEIS-Einträge:

$(a_{n,3,2})$: OEIS/A000949
$(a_{n,4,2})$: OEIS/A060908
$(a_{n,4,3})$: OEIS/A000950
$(a_{n,5,2})$: OEIS/A060909
$(a_{n,5,3})$: OEIS/A060911
$(a_{n,5,4})$: OEIS/A000951

Danke an tactac für das Korrekturlesen!

\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist nicht im Verzeichnis der Arbeitsgruppe Alexandria eingetragen.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 549
 
Aufrufstatistik des Artikels
Insgesamt 6 externe Seitenaufrufe zwischen 2020.05 und 2021.01 [Anzeigen]
DomainAnzahlProz
https://google.com466.7%66.7 %
https://www.bing.com116.7%16.7 %
https://google.de116.7%16.7 %

Häufige Aufrufer in früheren Monaten
Insgesamt 4 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
202005-12 (4x)https://google.com/

[Top of page]

"Mathematik: Anzahl der Abbildungen $f$ mit $f^p = f^q$" | 1 Comment
The authors of the comments are responsible for the content.

Re: Anzahl der Abbildungen $f$ mit $f^p = f^q$
von: Ex_Mitglied_52143 am: Sa. 14. Dezember 2019 16:26:26
\(\begingroup\)
<math>
\usetikzlibrary{matrix}

\begin{tikzpicture}[every path/.style={->, >=latex}]
\matrix (m) [matrix of math nodes, nodes in empty cells,
nodes={
text=red,
inner sep=0pt,
},
column sep=7mm, row sep=6mm,
Color/.style={column #1/.style={nodes={text=blue}}},
Color/.list={3,4,5}
]{
\bullet  &              &             &   \bullet  &              & \bullet  \\
&  \bullet  &   \bullet  &               &   \bullet &            \\
\bullet   &             &              &   \bullet  &            & \bullet \\
%1          &  2  &   3  &   4  &   5  & 6 \\
};

\draw [blue] (m-3-4) to (m-2-3);
\draw [blue] (m-2-2) to (m-2-3);
\draw [blue] (m-2-3) to (m-1-4);
\draw [blue] (m-1-4) to (m-2-5);
\draw [blue] (m-2-5) to (m-3-4);

\draw [red,bend right=10] (m-1-1) to (m-2-2);
\draw [red,bend left=10] (m-3-1) to (m-2-2);
\draw [red,bend left=10] (m-1-6) to (m-2-5);
\draw [red,bend right=10] (m-3-6) to (m-2-5);
\end{tikzpicture}

</math>\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]