\documentclass[12pt,a4paper]{article}

\usepackage{amssymb}
\usepackage{german}

\addtolength{\topmargin}{-34pt}
\addtolength{\textheight}{68pt}
\hoffset=.25in
\voffset=.5in
%\sloppy

\newtheorem{theorem}{Satz}
\newtheorem{corollary}{Korollar:}
\newtheorem{lemma}{Lemma}

\newcommand{\spunkt}{\mbox{$\bigcirc \kern-.75em s\kern.25em$}}
\newcommand{\upunkt}{\mbox{$\bigcirc \kern-.80em u\kern.21em$}}
\newcommand{\scirc}{\raisebox{1pt}{$\,\scriptstyle\circ\,$}}
\newcommand{\Bu}{\mbox{$\widehat{\Omega}$}}
\newcommand{\bu}{\mbox{$\Omega$}}
\newcommand{\N}{\mbox{\bf N}}
\newcommand{\Nu}{\mbox{${\bf N}_{\infty}$}}
\newcommand{\No}{\mbox{${\bf N}_0$}}
\newcommand{\Z}{\mbox{\bf Z}}
\newcommand{\Q}{\mbox{\bf Q}}
\newcommand{\C}{\mbox{\bf C}}
\newcommand{\W}{\mbox{\bf W}}
\newcommand{\FI}{\mbox{$\widehat{\varphi}$}}

\begin{document} 
\vspace*{2.4cm}
\begin{center}
{\bf Zur Kombinatorik von Permutationen}\\[3mm]
{\scriptsize \sc VON}\\[3mm]
{\sc Torsten} SILLKE
\footnote{\noindent
Universit\"at Bielefeld, Fakult\"at f\"ur Mathematik, Postfach 8640,
D 4800 Bielefeld 1. \mbox{e--mail: UMATF071 @ DBIUNI11 (EARN).}}
\end{center}

\footnotesize\noindent
{\sc Abstract.} --- A bijection between the set of subgroups of index~$n$
in the free group on 2~generators ${\cal F}_{2}$ and the set of connex
permutations $\sigma$ of $[ n+1 ] = \{ 1, 2, ..., n+1\}$ has been 
constructed by {\sc A.W.M.~Dress} and {\sc R.~Franz} \cite{DrF85},
where $\sigma$ 
is connex iff $\sigma [k] \neq [k]$ for $k \in [n]$. {\sc Dumont}  and
{\sc Kreweras} 
introduced the record-antirecord statistics for connex permutations of
$[n+1]$,
which are the same as the orbit statistics of the Cayley coset diagram of
the
subgroups of index~$n$ in the free group. {\sc J.~Zeng} \cite{Zen87}
asked for a bijection between 
these sets. As the bijection of {\sc Dress} and {\sc Franz}  is not
applicable, a new one 
is presented. The construction uses a correspondence between the cycles
and the basic components of permutations \cite[Ch I.3]{FoS70} 
\cite[1.3.3]{Knu68}, which {\sc Goulden} and {\sc Jackson} 
\cite[{[3.3.17]}]{GoJ83} call the 
Foata~Sch\"utzenberger correspondence. {\sc Dress} and {\sc Franz}
\cite{DrF87}  
generalised their construction to a bijection between subgroups of
finite index in ${\cal F}_{k}$ and  connex systems of $k-1$ permutations.
The bijection presented in this paper can also be extended to this more
general case.

\normalsize
\medskip
\begin{center}
{\bf Einleitung}
\end{center}

\noindent
Wir betrachten die {\em hypergeometrische Reihe} und deren 
{\em logarithmische Ableitung}
\begin{eqnarray*}
F &=&  \raisebox{-3pt}{${}_{2}\mbox{\Large \it F}_{0}$} 
\left[\stackrel{\displaystyle\alpha,\beta}{\mbox{\rule[-4pt]{15pt}{.4pt}}}
		\mbox{\rule[-8pt]{.2pt}{20pt}} \:x \right ] 
	:= \sum_{n=0}^{\infty}\frac{(\alpha)_{n}(\beta)_{n}}{n\,!}
				\cdot x^{n}\\[12pt]
C & =& x \cdot \frac{d}{dx} \log  F  =  x\cdot \frac{F^{\prime}}{F} = 
       \sum_{n=1}^{\infty} C_{n}(\alpha,\beta) \cdot x^{n}.
\end{eqnarray*}
Die Koeffizienten der hypergeometrischen Reihe sind die aufsteigenden
Faktoriellen. Sie sind definiert durch
\[
(\alpha)_{0} := 1, \quad (\alpha)_{n+1} := (\alpha + n)(\alpha)_{n}.
\]

\pagebreak\noindent
Die Koeffizienten $C_{n}(1,1)$ z\"ahlen
\begin{itemize}
\item	
zum einen die Anzahl der Untergruppen von Index $n$ in der
freien, von zwei Elementen erzeugten Gruppe ${\cal F}_{2}$
\cite[Thm 7.2.9]{Hal59} \cite[Ex 6.10]{Sta78},
\item	
zum anderen die Anzahl der konnexen Permutationen auf der Menge  
$[n+1]:=\{1,2,\dots,n+1\}$. Hierbei hei{\ss}t  eine
Permutation $\sigma$ auf 
$[n+1]$ konnex , wenn kein  echtes Teilintervall 
$[k] \subset [n+1]$ durch die Permutation 
$ \sigma$ in sich \"uberf\"uhrt wird
\cite[p261 Ex 14]{Com74} \cite[{[2.4.19]}]{GoJ83}.
%
\end{itemize}
%
Eine Bijektion zwischen diesen beiden Mengen haben 
{\sc A.~Dress} und {\sc R.~Franz} in \cite{DrF85} angegeben.
Sie studieren dabei die Operation der beiden Erzeugenden $s$ und $u$
der freien Gruppe auf der Menge ${\cal F}_{2}/U$ der Nebenklassen der freien
Gruppe modulo der Untergruppe $U$. 

\noindent
Der Koeffizient von $\alpha^{k} \beta^{l} $ des Polynomes $C_{n}( \alpha,
\beta)$ z\"ahlt 
\begin{itemize}
\item 	
zum einen die Anzahl derjenigen Untergruppen $U$ vom Index $n$ in
freien von 
$s$ und $u$ erzeugeten Gruppe ${\cal F}_{2}$, bei denen die Nebenklassen
${\cal F}_{2} / U$ unter der Operation von $s$ in $k\;$ Zyklen und unter der
Operation $u$ in $l\;$ Zyklen zerfallen,
\item	
zum anderen die Anzahl der konnexen Permutationen $\sigma$ auf
$[n+1]$, die genau
$k$ links--rechts Maxima und $l$ rechts--links Minima haben
(hierbei hei{\ss}t der Punkt 
$(i,\sigma(i)) \in [n+1]\times [n+1]$ ein links--rechts Maximum der
Permutation $\sigma$, falls f\"ur alle $j < i$ gilt:
$\sigma (j) < \sigma (i)$, und  rechts--links
Minima sind entsprechend definiert)
(cf. {\sc Dumont} und {\sc Kreweras} in \cite{DuK86}).
%
\end{itemize}
%
In \cite{Zen87} fragt {\sc J. Zeng} nach einer Bijektion zwischen den
jeweiligen relevanten Mengen. (Un)gl\"ucklicherweise leistet die in
\cite{DrF85} angegebene Bijektion nicht das Gew\"unschte.

Im folgenden soll eine Bijektion angegeben werden, die auch mit
der durch die Parameter definierten feineren Statistik vertr\"aglich
ist. Hierf\"ur ist es n\"utzlich, anstelle der Operation  der
freien Gruppe auf der Menge der Nebenklassen ${\cal F}_{2}/U$ (bei der die
Nebenklasse $U$ ein ausgezeichnetes Element ist),  transitive Operationen
von ${\cal F}_{2}$ auf Mengen zu betrachten, bei denen es zwei
ausgezeichnete
Elemente gibt. Genauer betrachten wir endliche Mengen $E$ zusammen mit
zwei Permutationen $s$ und $u$, die den folgenden Bedingungen
gen\"ugen:
\begin{itemize}
\item
$E$ ist eine endliche transitive $s$--$u$ Menge, d.h. f\"ur je zwei Elemente
$x$ und $y$ aus $E$ gibt es ein Wort $w$ in $s$ und $u$, so da{\ss}
$w(x) = y$ ist.
\item
Es gibt zwei voneinander verschiedene Punkte $\spunkt$ und $\upunkt$ in
$E$, f\"ur die gilt: $u(\spunkt)=\upunkt$ und $s(\upunkt)=\spunkt$.
\end{itemize}

Mengen dieser Art wollen wir {\em doppelt punktierte} (transitive)
$s$--$u$ Mengen nennen.

\begin{footnotesize}
\begin{center}
\setlength{\unitlength}{1pt}
\begin{picture}(100,50)(0,0)
% 
%-----------------------------------------------------------
% ********** MITTE ******************************* 
%
\put(30,25){\makebox(0,0)[r]{ $\spunkt$}}
%
\put(70,25){\makebox(0,0)[l]{ $\upunkt$}}
% 
 
% ************* horizontale Pfeile********************* 
%
\put(33,27){\vector(1,0){32}}
%
\put(65,23){\vector(-1,0){32}}
%
% *************** Pfeile links *************************
%
\put(-17,47){\vector(2,-1){30}}
%
\put(13,18){\vector(-2,-1){30}}
%
%**************** Pfeile rechts *************************
%
\put(87,32){\vector(2,1){30}}
%
\put(117,3){\vector(-2,1){30}}
%
%******************** Beschriften ************************
%
\put(50,32){\makebox(0,)[c]{$u$}}
%
\put(50,18){\makebox(0,)[c]{$s$}}
%
\put(1,42){\makebox(0,)[l]{$u$}}
%
\put(1,8){\makebox(0,)[l]{$s$}}
%
\put(99,42){\makebox(0,)[r]{$u$}}
%
\put(99,8){\makebox(0,)[r]{$s$}}
%
\end{picture}
\end{center}
\end{footnotesize}

Es ist klar, da{\ss} man durch Identifikation der beiden
ausgezeichnete Punkte zu einem ausgezeichneten Punkt (und Weglassen
der  beiden sie verbindenden Pfeile) aus einer doppelt 
punktierten $s$--$u$ Menge die Menge  der Nebenklassen nach einer
Untergruppe machen kann (man erh\"alt die Untergruppe als
Standuntergruppe des neuen ausgezeichneten Punktes) und da{\ss} dieses
Verfahren eine Bijektion von der Menge der Untergruppen von endlichem
Index in einer freien Gruppe mit zwei Erzeugenden und der Menge der
doppelt punktierten $s$--$u$ Mengen liefert. Wir k\"onnen und werden
deshalb von nun an nur noch doppelt punktierte Mengen betrachten. 
Es gilt der folgende Satz:

\smallskip
\noindent
{\sc Satz:} \\
Es gibt eine kanonische Bijektion zwischen der Menge (der Isomorphieklassen)
der doppelt punktierten $s$--$u$ Mengen mit einer $n$--elementigen
Tr\"agermenge $E$ und der  
Menge der konnexen Permutationen von $[n]$, die vertr\"aglich ist mit
der durch die Parameter $\alpha$ und $\beta$ gegebenen feineren Statistik.
\smallskip

\begin{center}
{\bf Von den Permutationen zu den doppelt punktierten Mengen}
\end{center}

\noindent
Ist $\sigma$ eine Permutation  von $[n]$, dann ist der Graphen
$\Gamma(\sigma)\subset [n] \times [n]$ definiert durch:
$\Gamma(\sigma) := \{(i,\sigma(i)) \mid i \in [n] \}$.

Die Permutation $\sigma$ definiert dann in naheliegender Weise eine
Permutation des Graphen von $\sigma$. Sie ist definiert durch
$(i,\sigma(i))\mapsto (\sigma(i), \sigma(\sigma(i)))$ und wird
ebenfalls mit $\sigma$ bezeichnet.

Die Permutation $\sigma$ ist genau dann konnex, wenn
es kein echtes Teilintervall $[k]$ von $[n]$ gibt, so da{\ss}
$\sigma([k]\times [k]) \subset [k] \times [k]$ ist, 

Jede Permutation  $w$ von $\Gamma(\sigma)$ induziert in naheliegender
Weise zwei Permutationen $w_{1}$ und $w_{2}$ von $[n]$. Sie sind
folgenderma{\ss}en definiert\footnote{die Projektionen eines Produktes
zweier Mengen auf die beiden Faktoren werden mit $pr_{1}$ bzw. 
$pr_{2}$ bezeichnet}
\begin{eqnarray*}
w_{1}(i) 	&=& pr_{1}w(i,\sigma(i))\\
w_{2}(j) 	&=& pr_{1}w(\sigma^{-1}(j),j)
\end{eqnarray*}

\smallskip\noindent
{\sc Beobachtung:} \\
Auf dem Graphen $\Gamma(\sigma)$ gibt es genau eine Permutation $s$
(genau eine Permutation $u$) mit den folgenden Eigenschaften:
\begin{itemize}
\item
Die Zyklen der Permutationen $s_{1}$ und $u_{2}$ sind
Intervalle. Auf jedem dieser Interrvalle operieren $s_{1}$
bzw. $u_{2}$
durch Schieben 
auf den Nachfolger. Der letzte Punkt des Intervalles, der keinen
Nachfolger besitzt, wird auf den
ersten geschoben.
\item
Die Anfangspunkte der zu $s_{1}$ geh\"origen Intervalle sind die
ersten Koordinaten der links--rechts Maxima von $\sigma$.
Die Anfangspunkte der der zu $u_{2}$ geh\"origen Intervalle sind die
zweiten Koordinaten der rechts--links Minima von $\sigma$.
\end{itemize}
Dies ist nichts anderes als die Foata~Sch\"utzenberger 
Korrespondenz\footnote{so genannt  von {\sc Goulden} 
und {\sc Jackson} \cite[{[3.3.17]}]{GoJ83}},
angewendet  auf $\sigma$ und 
$\sigma^{-1}$  \cite[Cha IV.5]{CaF69}, \cite[Cha I.3]{FoS70},
\cite[1.3.3]{Knu68}, \cite[5.1.2 Thm B]{Knu73}.

\smallskip\noindent
{\sc Beispiel:}\\
Wir betrachten die Permutation 
$\displaystyle\sigma={1\;2\;3\;4\;5\;6\;7\;8\;9 \choose
	 	      5\;2\;7\;1\;6\;3\;9\;8\;4}.
$
In den folgenden Diagrammen ist der  Graph 
$\Gamma(\sigma)$ der gegebenen Permutation dargestellt. Links 
sind die Zyklen der Permutation $s$ durch senkrechte Linien
voneinander getrennt, rechts die Zyklen der Permutation $u$ durch
horizontale Linien.\\[12pt]
\noindent
\begin{center}
\begin{minipage}[t]{5cm}
\begin{scriptsize}
\begin{center}
\setlength{\unitlength}{12pt}
\begin{picture}(11,11)(-.5,-.5)
% 
%-----------------------------------------------------------
%********** ZEHN PUNKTE ******************************* 
%
%
\put(1,5){\makebox(0,0)[c]{$\spadesuit $}}
\put(2,2){\makebox(0,0)[c]{$\spadesuit $}}
\put(3,7){\makebox(0,0)[c]{$\spadesuit $}}
\put(4,1){\makebox(0,0)[c]{$\spadesuit $}}
\put(5,6){\makebox(0,0)[c]{$\spadesuit $}}
\put(6,3){\makebox(0,0)[c]{$\spadesuit $}}
\put(7,9){\makebox(0,0)[c]{$\bigcirc$}}
\put(7,9){\makebox(0,0)[c]{$s$}}
\put(8,8){\makebox(0,0)[c]{$\spadesuit $}}
\put(9,4){\makebox(0,0)[c]{$\bigcirc$}}
\put(9,4){\makebox(0,0)[c]{$u$}}
%
\put(1,0){\makebox(0,0)[c]{$1 $}}
\put(2,0){\makebox(0,0)[c]{$2 $}}
\put(3,0){\makebox(0,0)[c]{$3 $}}
\put(4,0){\makebox(0,0)[c]{$4 $}}
\put(5,0){\makebox(0,0)[c]{$5 $}}
\put(6,0){\makebox(0,0)[c]{$6 $}}
\put(7,0){\makebox(0,0)[c]{$7 $}}
\put(8,0){\makebox(0,0)[c]{$8 $}}
\put(9,0){\makebox(0,0)[c]{$9 $}}
%
\put(0,1){\makebox(0,0)[c]{$1 $}}
\put(0,2){\makebox(0,0)[c]{$2 $}}
\put(0,3){\makebox(0,0)[c]{$3 $}}
\put(0,4){\makebox(0,0)[c]{$4 $}}
\put(0,5){\makebox(0,0)[c]{$5 $}}
\put(0,6){\makebox(0,0)[c]{$6 $}}
\put(0,7){\makebox(0,0)[c]{$7 $}}
\put(0,8){\makebox(0,0)[c]{$8 $}}
\put(0,9){\makebox(0,0)[c]{$9 $}}
% ************** Umrandung ******************************
%
\put(0.5,-0.5){\line(0,1){10}}
\put(2.5,-0.5){\line(0,1){10}}
\put(6.5,-0.5){\line(0,1){10}}
\put(9.5,-0.5){\line(0,1){10}}
% 
\put(0.5,0.5){\line(1,0){9}}
\put(0.5,9.5){\line(1,0){9}}
%
%******************************************************** 
\end{picture}\\[12pt]
$s_{1}=(12)(3456)(789)$
\end{center}
\end{scriptsize}
\end{minipage}
%
\hspace{1cm}
%
\begin{minipage}[t]{5cm}
\begin{scriptsize}
\begin{center}
\setlength{\unitlength}{12pt}
\begin{picture}(11,11)(-.5,-.5)
% 
%-----------------------------------------------------------
%********** ZEHN PUNKTE ******************************* 
%
\put(1,5){\makebox(0,0)[c]{$\spadesuit $}}
\put(2,2){\makebox(0,0)[c]{$\spadesuit $}}
\put(3,7){\makebox(0,0)[c]{$\spadesuit $}}
\put(4,1){\makebox(0,0)[c]{$\spadesuit $}}
\put(5,6){\makebox(0,0)[c]{$\spadesuit $}}
\put(6,3){\makebox(0,0)[c]{$\spadesuit $}}
\put(7,9){\makebox(0,0)[c]{$\bigcirc$}}
\put(7,9){\makebox(0,0)[c]{$s$}}
\put(8,8){\makebox(0,0)[c]{$\spadesuit $}}
\put(9,4){\makebox(0,0)[c]{$\bigcirc$}}
\put(9,4){\makebox(0,0)[c]{$u$}}
%
\put(1,0){\makebox(0,0)[c]{$1 $}}
\put(2,0){\makebox(0,0)[c]{$2 $}}
\put(3,0){\makebox(0,0)[c]{$3 $}}
\put(4,0){\makebox(0,0)[c]{$4 $}}
\put(5,0){\makebox(0,0)[c]{$5 $}}
\put(6,0){\makebox(0,0)[c]{$6 $}}
\put(7,0){\makebox(0,0)[c]{$7 $}}
\put(8,0){\makebox(0,0)[c]{$8 $}}
\put(9,0){\makebox(0,0)[c]{$9 $}}
%
\put(0,1){\makebox(0,0)[c]{$1 $}}
\put(0,2){\makebox(0,0)[c]{$2 $}}
\put(0,3){\makebox(0,0)[c]{$3 $}}
\put(0,4){\makebox(0,0)[c]{$4 $}}
\put(0,5){\makebox(0,0)[c]{$5 $}}
\put(0,6){\makebox(0,0)[c]{$6 $}}
\put(0,7){\makebox(0,0)[c]{$7 $}}
\put(0,8){\makebox(0,0)[c]{$8 $}}
\put(0,9){\makebox(0,0)[c]{$9 $}}
% ************** Umrandung ******************************
%
\put(0.5,0.5){\line(0,1){9}}
\put(9.5,0.5){\line(0,1){9}}
% 
\put(-0.5,0.5){\line(1,0){10}}
\put(-0.5,2.5){\line(1,0){10}}
\put(-0.5,3.5){\line(1,0){10}}
\put(-0.5,9.5){\line(1,0){10}}
%
%******************************************************** 
\end{picture}\\[12pt]
$u_{2}=(12)(3)(456789)$
\end{center}
\end{scriptsize}
\end{minipage}
\end{center}
\vspace*{24pt}

\smallskip\noindent
{\sc Lemma:}\\
Es gibt {\em genau} ein links--rechts Maximum $\spunkt \in \Gamma(\sigma)$
f\"ur das $ s u \spunkt = \spunkt$ ist.\\
Es gibt {\em genau} ein rechts--links Minimum 
$\upunkt \in \Gamma(\sigma)$
f\"ur das $ u s \upunkt = \upunkt$ ist.\\
Dar"uber hinaus  gilt f"ur diese Punkte:
$ s \cdot \upunkt = \spunkt $ und 
$ u \cdot \spunkt = \upunkt $. 


\smallskip
Die Kombination dieser Beobachtungen etabliert auf der Menge
$\Gamma(\sigma)$ die Struktur einer doppelt punktierten transitiven
$s$--$u$ Menge. 
Insgesamt haben wir somit eine Abbildung von der Menge der konnexen
Permutationen auf $[n]$ in die Menge der doppelt punktierten
transitiven $s$--$u$ Mengen. 
%In der folgenden Abbildung sind links die
%$s$--Zyklen durch horizontale Linien getrennt worden und rechts die
%$u$--Zyklen durch vertikale.
%Dem Leser sei empfohlen die Zyklen wirklich in die Abbildung
%einzuzeichnen. 



\begin{center}
{\bf Von den ${\cal F}_{2}$--Mengen zu den Permutationen}\\
Das Cayley Diagramm Modell
\end{center}

\noindent
Es soll nun umgekehrt eine Abbildung von der Menge (der Isomorphieklassen)
der
doppelt punktierten transitiven $s$--$u$ Mengen mit $n$ Elementen in
die Menge der konnexen Permutationen auf $[n]$ konstruiert werden.

Hierf"ur geben wir ein Verfahren an, durch das schrittweise
jedem Element von $E$ eine Position in der Menge 
$[n]\times [n]$ derart zugeordnet wird, da"s die dabei resultierende
Teilmenge des Quadrates $Q:=[n]\times [n]$  der Graph einer konnexen
Permutation von $[n]$ ist. 

{\sc Beispiel:}\\
\begin{center}
\begin{minipage}[t]{5.5cm}
\begin{scriptsize}
\begin{center}
\setlength{\unitlength}{12pt}
\begin{picture}(12,12)(-.5,-.5)
%********************* Cayley Diagramm *****************
%
\put(5,0){\makebox(0,0)[c]{$\bigcirc $}}
\put(5,0){\makebox(0,0)[c]{$s$}}
\put(0,2.5){\makebox(0,0)[c]{$\bigcirc $}}
\put(0,2.5){\makebox(0,0)[c]{$u$}}
\put(10,2.5){\makebox(0,0)[c]{$G$}}
\put(2.5,5){\makebox(0,0)[c]{$E$}}
\put(7.5,5){\makebox(0,0)[c]{$F$}}
\put(0,7.5){\makebox(0,0)[c]{$C$}}
\put(10,7.5){\makebox(0,0)[c]{$D$}}
\put(2.5,10){\makebox(0,0)[c]{$A$}}
\put(7.5,10){\makebox(0,0)[c]{$B$}}
%
%********** S Zyklen ************************
%\put(0.0,2.5){\vector(2,-1){5}}
%\put(5,0){\vector(2,1){5}}
%\put(10,2.5){\vector(-1,0){10}}
%\put(7.5,10){\vector(1,-1){2.5}}
%\put(10,7.5){\vector(-1,-1){2.5}}
%\put(7.5,5){\vector(-1,1){5}}
%\put(2.5,10){\vector(1,0){5}}
%\put(2.5,5){\vector(-1,1){2.5}}
%\put(0,7.5){\vector(1,-1){2.5}}
%
%\put(0,2.375){\(2,-1){4}}
%
\put(0.625,2.375){\vector(2,-1){4}}
\put(5.375,0.375){\vector(2,1){4}}
\put(9.5,2.5){\vector(-1,0){9}}
\put(7.80,9.70){\vector(1,-1){1.9}}
\put(9.70,7.20){\vector(-1,-1){1.9}}
\put(7.20,5.30){\vector(-1,1){4.4}}
\put(3,10){\vector(1,0){4}}
\put(2.375,5.375){\vector(-1,1){2}}
\put(0.125,7.125){\vector(1,-1){2}}
%
%********** U Zyklen ************************
%\put(5,0){\vector(-2,1){5}}
%\put(0,2.5){\vector(0,1){5}}
%\put(0,7.5){\vector(1,1){2.5}}
%\put(2.5,10){\vector(3,-1){7.5}}
%\put(10,7.5){\vector(0,-1){5}}
%\put(10,2.5){\vector(-2,-1){5}}
%\put(8,10.5){\oval(1,1)[r]}   %Schlaufe
%\put(8,10.5){\oval(1,1)[lt]}  %Schlaufe
%\put(7.5,10.5){\vector(0,-1)[0]}
%\put(2.5,5){\vector(1,0){5}}
%\put(7.5,5){\vector(-1,0){5}}
%
%\put(4.375,0.125){\vector(-2,1){4}}
%\put(0,3){\vector(0,1){4}}
%\put(0.25,7.75){\vector(1,1){2}}
%\put(3.25,9.75){\vector(3,-1){6}}
%\put(10,7){\vector(0,-1){4}}
%\put(9.675,2.125){\vector(-2,-1){4}}
%\put(8,10.5){\oval(1,1)[r]}   %Schlaufe
%\put(8,10.5){\oval(1,1)[lt]}  %Schlaufe
%\put(7.5,10.5){\vector(0,-1){0.125}}
%\put(8,10){\line(-1,0){0.125}}
%\put(3,5.125){\vector(1,0){4}}
%\put(7,4.875){\vector(-1,0){4}}
%*******************************************************
\end{picture}\\[12pt]
Die $s$--Bahnen von $E$
\end{center}
\end{scriptsize}
\end{minipage}
%
\hspace{1cm}
%
\begin{minipage}[t]{5.5cm}
\begin{scriptsize}
\begin{center}
\setlength{\unitlength}{12pt}
\begin{picture}(12,12)(-.5,-.5)
%********************* Cayley Diagramm *****************
%
\put(5,0){\makebox(0,0)[c]{$\bigcirc $}}
\put(5,0){\makebox(0,0)[c]{$s$}}
\put(0,2.5){\makebox(0,0)[c]{$\bigcirc $}}
\put(0,2.5){\makebox(0,0)[c]{$u$}}
\put(10,2.5){\makebox(0,0)[c]{$G$}}
\put(2.5,5){\makebox(0,0)[c]{$E$}}
\put(7.5,5){\makebox(0,0)[c]{$F$}}
\put(0,7.5){\makebox(0,0)[c]{$C$}}
\put(10,7.5){\makebox(0,0)[c]{$D$}}
\put(2.5,10){\makebox(0,0)[c]{$A$}}
\put(7.5,10){\makebox(0,0)[c]{$B$}}
%
%********** S Zyklen ************************
%\put(0.0,2.5){\vector(2,-1){5}}
%\put(5,0){\vector(2,1){5}}
%\put(10,2.5){\vector(-1,0){10}}
%\put(7.5,10){\vector(1,-1){2.5}}
%\put(10,7.5){\vector(-1,-1){2.5}}
%\put(7.5,5){\vector(-1,1){5}}
%\put(2.5,10){\vector(1,0){5}}
%\put(2.5,5){\vector(-1,1){2.5}}
%\put(0,7.5){\vector(1,-1){2.5}}
%
%\put(0.625,2.375){\vector(2,-1){4}}
%\put(5.375,0.375){\vector(2,1){4}}
%\put(9.5,2.5){\vector(-1,0){9}}
%\put(7.75,9.75){\vector(1,-1){2}}
%\put(9.75,7.25){\vector(-1,-1){2}}
%\put(7.25,5.25){\vector(-1,1){4.5}}
%\put(3,10){\vector(1,0){4}}
%\put(2.375,5.375){\vector(-1,1){2}}
%\put(0.125,7.125){\vector(1,-1){2}}
%
%********** U Zyklen ************************
%\put(5,0){\vector(-2,1){5}}
%\put(0,2.5){\vector(0,1){5}}
%\put(0,7.5){\vector(1,1){2.5}}
%\put(2.5,10){\vector(3,-1){7.5}}
%\put(10,7.5){\vector(0,-1){5}}
%\put(10,2.5){\vector(-2,-1){5}}
%\put(8,10.5){\oval(1,1)[r]}   %Schlaufe
%\put(8,10.5){\oval(1,1)[lt]}  %Schlaufe
%\put(7.5,10.5){\vector(0,-1)[0]}
%\put(2.5,5){\vector(1,0){5}}
%\put(7.5,5){\vector(-1,0){5}}
%
\put(4.375,0.125){\vector(-2,1){4}}
\put(0,3){\vector(0,1){4}}
\put(0.30,7.80){\vector(1,1){1.9}}
\put(3.25,9.75){\vector(3,-1){6}}
\put(10,7){\vector(0,-1){4}}
\put(9.675,2.125){\vector(-2,-1){4}}
\put(8,10.5){\oval(1,1)[r]}   %Schlaufe
\put(8,10.5){\oval(1,1)[lt]}  %Schlaufe
\put(7.5,10.5){\vector(0,-1){0.125}}
\put(8,10){\line(-1,0){0.125}}
\put(3,5.125){\vector(1,0){4}}
\put(7,4.875){\vector(-1,0){4}}
%*******************************************************
\end{picture}\\[12pt]
Die $u$--Bahnen von $E$.
\end{center}
\end{scriptsize}
\end{minipage}\\[12pt]
\end{center}
Wir starten, indem wir die Elemente der $s$--Bahn des Punktes
$\spunkt$ (mit $\spunkt$ startend) horizontal oberhalb des
Quadrates $Q$ so hinzeichnen, da"s ihr letztes Element (hier das
Element $\upunkt$) oberhalb der rechten oberen Ecke von $Q$
steht, und ebenso tragen wir die Elemente der $u$--Bahn von
$\upunkt$ rechts von dem Quadrat $Q$ vertikal so auf, da"s ihr letztes
Element (hier das Element $\spunkt$)  rechts von der oberen
Ecke von $Q$ steht. Die oberhalb des Quadrates liegenden Punkte von
$E$ sind hierdurch schon in ihrer ersten Koordinate festgelegt, die
rechts stehenden in ihrer zweiten. In der folgenden Abbildungen ist
links diese Konfiguration dargestellt:\\[12pt]
\begin{center}
\begin{minipage}[t]{5cm}
\begin{scriptsize}
\begin{center}
\setlength{\unitlength}{10pt}
\begin{picture}(11,11)(0,0)
% ******* 1. Bild vor ******* Umrandung ***********************
%
\put(0.5,0.5){\line(0,1){9}}
\put(9.5,0.5){\line(0,1){9}}
% 
\put(0.5,0.5){\line(1,0){9}}
\put(0.5,9.5){\line(1,0){9}}
%\put(1,5){\makebox(0,0)[c]{$\spadesuit $}}
%\put(2,2){\makebox(0,0)[c]{$\spadesuit $}}
%\put(3,7){\makebox(0,0)[c]{$\spadesuit $}}
%\put(4,1){\makebox(0,0)[c]{$\spadesuit $}}
%\put(5,6){\makebox(0,0)[c]{$\spadesuit $}}
%\put(6,3){\makebox(0,0)[c]{$\spadesuit $}}
%\put(7,9){\makebox(0,0)[c]{$\spadesuit $}}
%\put(8,8){\makebox(0,0)[c]{$\spadesuit $}}
%\put(9,4){\makebox(0,0)[c]{$\spadesuit $}}
%
%*****Oben*************************************************** 
%\put(1,10){\makebox(0,0)[c]{$C$}}
%\put(2,10){\makebox(0,0)[c]{$E$}}
%\put(3,10){\makebox(0,0)[c]{$D$}}
%\put(4,10){\makebox(0,0)[c]{$F$}}
%\put(5,10){\makebox(0,0)[c]{$A$}}
%\put(6,10){\makebox(0,0)[c]{$B$}}
\put(7,10){\makebox(0,0)[c]{$\spunkt$}}
\put(8,10){\makebox(0,0)[c]{$G$}}
\put(9,10){\makebox(0,0)[c]{$\upunkt$}}
\put(6.5,9.5){\line(0,1){1}}
\put(9.5,9.5){\line(0,1){1}}
\put(6.5,10.5){\line(1,0){3}}
%
%\put( ,9){\makebox(0,0)[c]{$\Uparrow$}}
%
%*****Rechts************************************************* 
%\put(10,1){\makebox(0,0)[c]{$F$}}
%\put(10,2){\makebox(0,0)[c]{$E$}}
%\put(10,3){\makebox(0,0)[c]{$B$}}
\put(10,4){\makebox(0,0)[c]{$\upunkt$}}
\put(10,5){\makebox(0,0)[c]{$C$}}
\put(10,6){\makebox(0,0)[c]{$A$}}
\put(10,7){\makebox(0,0)[c]{$D$}}
\put(10,8){\makebox(0,0)[c]{$G$}}
\put(10,9){\makebox(0,0)[c]{$\spunkt$}}
\put(9.5,3.5){\line(1,0){1}}
\put(9.5,9.5){\line(1,0){1}}
\put(10.5,3.5){\line(0,1){6}}
%
%\put(9,7){\makebox(0,0)[c]{$\Rightarrow$}}
%
\end{picture}
\end{center}
\end{scriptsize}
\end{minipage}
%
\hspace{1cm}
%
\begin{minipage}[t]{5cm}
\begin{scriptsize}
\begin{center}
\setlength{\unitlength}{10pt}
\begin{picture}(11,11)(0,0)
% ******* 1. Bild ******* Umrandung ***********************
%
\put(0.5,0.5){\line(0,1){9}}
\put(9.5,0.5){\line(0,1){9}}
% 
\put(0.5,0.5){\line(1,0){9}}
\put(0.5,9.5){\line(1,0){9}}
%\put(1,5){\makebox(0,0)[c]{$\spadesuit $}}
%\put(2,2){\makebox(0,0)[c]{$\spadesuit $}}
%\put(3,7){\makebox(0,0)[c]{$\spadesuit $}}
%\put(4,1){\makebox(0,0)[c]{$\spadesuit $}}
%\put(5,6){\makebox(0,0)[c]{$\spadesuit $}}
%\put(6,3){\makebox(0,0)[c]{$\spadesuit $}}
\put(7,9){\makebox(0,0)[c]{$\spadesuit $}}
\put(8,8){\makebox(0,0)[c]{$\spadesuit $}}
\put(9,4){\makebox(0,0)[c]{$\spadesuit $}}
%
%*****Oben*************************************************** 
%\put(1,10){\makebox(0,0)[c]{$C$}}
%\put(2,10){\makebox(0,0)[c]{$E$}}
%\put(3,10){\makebox(0,0)[c]{$D$}}
%\put(4,10){\makebox(0,0)[c]{$F$}}
%\put(5,10){\makebox(0,0)[c]{$A$}}
%\put(6,10){\makebox(0,0)[c]{$B$}}
\put(7,10){\makebox(0,0)[c]{$\spunkt$}}
\put(8,10){\makebox(0,0)[c]{$G$}}
\put(9,10){\makebox(0,0)[c]{$\upunkt$}}
%\put(6.5,9.5){\line(0,1){1}}
%\put(9.5,9.5){\line(0,1){1}}
%\put(6.5,10.5){\line(1,0){3}}
%
%\put( ,9){\makebox(0,0)[c]{$\Uparrow$}}
%
%*****Rechts************************************************* 
%\put(10,1){\makebox(0,0)[c]{$F$}}
%\put(10,2){\makebox(0,0)[c]{$E$}}
%\put(10,3){\makebox(0,0)[c]{$B$}}
\put(10,4){\makebox(0,0)[c]{$\upunkt$}}
\put(10,5){\makebox(0,0)[c]{$C$}}
\put(10,6){\makebox(0,0)[c]{$A$}}
\put(10,7){\makebox(0,0)[c]{$D$}}
\put(10,8){\makebox(0,0)[c]{$G$}}
\put(10,9){\makebox(0,0)[c]{$\spunkt$}}
\put(9.5,4.5){\line(1,0){1}} %%%%% Kasten
\put(9.5,7.5){\line(1,0){1}}
\put(10.5,4.5){\line(0,1){3}}
%
\put(9,7){\makebox(0,0)[c]{$\Rightarrow$}}
%
\end{picture}
\end{center}
\end{scriptsize}
\end{minipage}
\end{center}

F"ur diejenigen Punkte von $E$, die sowohl oben als auch rechts 
eingetragen sind, sind  schon beide Koordinaten bestimmt: sie werden
an der durch ihre  Koordinaten bestimmten 
Stelle in das Quadrat $Q$ eingetragen. Beispiele hierf"ur sind die
Punkte  $\spunkt$  und $\upunkt$. 

Erhalten bei diesem Verfahren s"amtliche Punkte oben und rechts schon
zwei Koordinaten,
dann ist die $s$--Bahn von $\spunkt$ gleich der $u$--Bahn von
$\upunkt$, und es folgt, da"s diese  Menge sowohl  unter der
Operation von $s$ als auch unter Operation von $u$  abgeschlossen ist;
sie ist daher schon gleich $E$ (denn es wurde ja vorausgesetzt, da"s
die  Menge $E$  eine transitive $s$--$u$ Menge ist). Alle Punkte von
$E$ haben dann schon ihren Platz in $[n]\times [n]$ gefunden, und wir
sind fertig.\\[12pt]
\begin{center}
\begin{minipage}[t]{5cm}
\begin{scriptsize}
\begin{center}
\setlength{\unitlength}{10pt}
\begin{picture}(11,11)(0,0)
% ******* 2. Bild vor ******* Umrandung ***********************
%
\put(0.5,0.5){\line(0,1){9}}
\put(9.5,0.5){\line(0,1){9}}
% 
\put(0.5,0.5){\line(1,0){9}}
\put(0.5,9.5){\line(1,0){9}}
%\put(1,5){\makebox(0,0)[c]{$\spadesuit $}}
%\put(2,2){\makebox(0,0)[c]{$\spadesuit $}}
%\put(3,7){\makebox(0,0)[c]{$\spadesuit $}}
%\put(4,1){\makebox(0,0)[c]{$\spadesuit $}}
%\put(5,6){\makebox(0,0)[c]{$\spadesuit $}}
%\put(6,3){\makebox(0,0)[c]{$\spadesuit $}}
\put(7,9){\makebox(0,0)[c]{$\spadesuit $}}
\put(8,8){\makebox(0,0)[c]{$\spadesuit $}}
\put(9,4){\makebox(0,0)[c]{$\spadesuit $}}
%
%*****Oben*************************************************** 
%\put(1,10){\makebox(0,0)[c]{$C$}}
%\put(2,10){\makebox(0,0)[c]{$E$}}
\put(3,10){\makebox(0,0)[c]{$D$}}
\put(4,10){\makebox(0,0)[c]{$F$}}
\put(5,10){\makebox(0,0)[c]{$A$}}
\put(6,10){\makebox(0,0)[c]{$B$}}
\put(7,10){\makebox(0,0)[c]{$\spunkt$}}
\put(8,10){\makebox(0,0)[c]{$G$}}
\put(9,10){\makebox(0,0)[c]{$\upunkt$}}
\put(6.5,9.5){\line(0,1){1}}
\put(2.5,9.5){\line(0,1){1}}
\put(2.5,10.5){\line(1,0){4}}
%
%\put(6,9){\makebox(0,0)[c]{$\Uparrow$}}
%
%*****Rechts************************************************* 
%\put(10,1){\makebox(0,0)[c]{$F$}}
%\put(10,2){\makebox(0,0)[c]{$E$}}
%\put(10,3){\makebox(0,0)[c]{$B$}}
\put(10,4){\makebox(0,0)[c]{$\upunkt$}}
\put(10,5){\makebox(0,0)[c]{$C$}}
\put(10,6){\makebox(0,0)[c]{$A$}}
\put(10,7){\makebox(0,0)[c]{$D$}}
\put(10,8){\makebox(0,0)[c]{$G$}}
\put(10,9){\makebox(0,0)[c]{$\spunkt$}}
\put(9.5,4.5){\line(1,0){1}}
\put(9.5,7.5){\line(1,0){1}}
\put(10.5,4.5){\line(0,1){3}}
%
%\put(9,5){\makebox(0,0)[c]{$\Rightarrow$}}
%
\end{picture}
\end{center}
\end{scriptsize}
\end{minipage}
%
\hspace{1cm}
%
\begin{minipage}[t]{5cm}
\begin{scriptsize}
\begin{center}
\setlength{\unitlength}{10pt}
\begin{picture}(11,11)(0,0)
% ******* 2. Bild ******* Umrandung ***********************
%
\put(0.5,0.5){\line(0,1){9}}
\put(9.5,0.5){\line(0,1){9}}
% 
\put(0.5,0.5){\line(1,0){9}}
\put(0.5,9.5){\line(1,0){9}}
%\put(1,5){\makebox(0,0)[c]{$\spadesuit $}}
%\put(2,2){\makebox(0,0)[c]{$\spadesuit $}}
\put(3,7){\makebox(0,0)[c]{$\spadesuit $}}
%\put(4,1){\makebox(0,0)[c]{$\spadesuit $}}
\put(5,6){\makebox(0,0)[c]{$\spadesuit $}}
%\put(6,3){\makebox(0,0)[c]{$\spadesuit $}}
\put(7,9){\makebox(0,0)[c]{$\spadesuit $}}
\put(8,8){\makebox(0,0)[c]{$\spadesuit $}}
\put(9,4){\makebox(0,0)[c]{$\spadesuit $}}
%
%*****Oben*************************************************** 
%\put(1,10){\makebox(0,0)[c]{$C$}}
%\put(2,10){\makebox(0,0)[c]{$E$}}
\put(3,10){\makebox(0,0)[c]{$D$}}
\put(4,10){\makebox(0,0)[c]{$F$}}
\put(5,10){\makebox(0,0)[c]{$A$}}
\put(6,10){\makebox(0,0)[c]{$B$}}
\put(7,10){\makebox(0,0)[c]{$\spunkt$}}
\put(8,10){\makebox(0,0)[c]{$G$}}
\put(9,10){\makebox(0,0)[c]{$\upunkt$}}
\put(3.5,9.5){\line(0,1){1}}
\put(4.5,9.5){\line(0,1){1}}
\put(5.5,9.5){\line(0,1){1}}
\put(6.5,9.5){\line(0,1){1}}
\put(3.5,10.5){\line(1,0){1}}
\put(5.5,10.5){\line(1,0){1}}
%
\put(6,9){\makebox(0,0)[c]{$\Uparrow$}}
%
%*****Rechts************************************************* 
%\put(10,1){\makebox(0,0)[c]{$F$}}
%\put(10,2){\makebox(0,0)[c]{$E$}}
%\put(10,3){\makebox(0,0)[c]{$B$}}
\put(10,4){\makebox(0,0)[c]{$\upunkt$}}
\put(10,5){\makebox(0,0)[c]{$C$}}
\put(10,6){\makebox(0,0)[c]{$A$}}
\put(10,7){\makebox(0,0)[c]{$D$}}
\put(10,8){\makebox(0,0)[c]{$G$}}
\put(10,9){\makebox(0,0)[c]{$\spunkt$}}
\put(9.5,4.5){\line(1,0){1}}
\put(9.5,5.5){\line(1,0){1}}
\put(10.5,4.5){\line(0,1){1}}
%
\put(9,5){\makebox(0,0)[c]{$\Rightarrow$}}
%
\end{picture}
\end{center}
\end{scriptsize}
\end{minipage}
\end{center}
Diejenigen Elemnte von $E$, f\"ur die erst eine Koordinate 
festliegt,  werden
durch einen Rahmen hervorgehoben. Man betrachte hierzu den rechte Teil
der vorangehenden Abbildung.
Wir w"ahlen dann unter den oben liegenden Punkten denjenigen, der
m"oglichst weit rechts liegt, bzw. falls es einen solchen Punkt nicht
gibt, den m"oglichst weit oben liegenden Punkt unter den rechts
liegenden. Dieser Punkt ist in dem rechten Teil der Abbildungen durch
den Pfeil $\Rightarrow$ markiert.
Im ersten Fall betrachten wir die $u$--Bahn des Punktes und
tragen sie auf der rechten Seite des Quadrates so ein, da"s ihr
letzter Punkt sich an den ersten Punkt der schon eingetragenen
$u$--Bahn anschlie"st. Im anderen Fall verf"ahrt man entsprechend und
tr"agt die $s$--Bahn des Punktes oberhalb des Quadrates und
anschlie"send an die schon eingetragene $s$--Bahn ein. Es ist
inzwischen sicherlich klar geworden, da{\ss} im linken Teil unserer
Abbildungen immer der Zustand wiedergegeben ist, in dem neue Zyklen
angef\"ugt wurden und rechts der, nach dem Eintragen der Punkte.\\[12pt]
\begin{center}
\begin{minipage}[t]{5cm}
\begin{scriptsize}
\begin{center}
\setlength{\unitlength}{10pt}
\begin{picture}(11,11)(0,0)
% ******* 3. Bild vor ******* Umrandung ***********************
%
\put(0.5,0.5){\line(0,1){9}}
\put(9.5,0.5){\line(0,1){9}}
% 
\put(0.5,0.5){\line(1,0){9}}
\put(0.5,9.5){\line(1,0){9}}
%\put(1,5){\makebox(0,0)[c]{$\spadesuit $}}
%\put(2,2){\makebox(0,0)[c]{$\spadesuit $}}
\put(3,7){\makebox(0,0)[c]{$\spadesuit $}}
%\put(4,1){\makebox(0,0)[c]{$\spadesuit $}}
\put(5,6){\makebox(0,0)[c]{$\spadesuit $}}
%\put(6,3){\makebox(0,0)[c]{$\spadesuit $}}
\put(7,9){\makebox(0,0)[c]{$\spadesuit $}}
\put(8,8){\makebox(0,0)[c]{$\spadesuit $}}
\put(9,4){\makebox(0,0)[c]{$\spadesuit $}}
%
%*****Oben*************************************************** 
\put(1,10){\makebox(0,0)[c]{$C$}}
\put(2,10){\makebox(0,0)[c]{$E$}}
\put(3,10){\makebox(0,0)[c]{$D$}}
\put(4,10){\makebox(0,0)[c]{$F$}}
\put(5,10){\makebox(0,0)[c]{$A$}}
\put(6,10){\makebox(0,0)[c]{$B$}}
\put(7,10){\makebox(0,0)[c]{$\spunkt$}}
\put(8,10){\makebox(0,0)[c]{$G$}}
\put(9,10){\makebox(0,0)[c]{$\upunkt$}}
\put(3.5,9.5){\line(0,1){1}}
\put(4.5,9.5){\line(0,1){1}}
\put(5.5,9.5){\line(0,1){1}}
\put(6.5,9.5){\line(0,1){1}}
\put(3.5,10.5){\line(1,0){1}}
\put(5.5,10.5){\line(1,0){1}}
\put(0.5,9.5){\line(0,1){1}}
\put(2.5,9.5){\line(0,1){1}}
\put(0.5,10.5){\line(1,0){2}}
%
%\put(4,9){\makebox(0,0)[c]{$\Uparrow$}}
%
%*****Rechts************************************************* 
%\put(10,1){\makebox(0,0)[c]{$F$}}
%\put(10,2){\makebox(0,0)[c]{$E$}}
\put(10,3){\makebox(0,0)[c]{$B$}}
\put(10,4){\makebox(0,0)[c]{$\upunkt$}}
\put(10,5){\makebox(0,0)[c]{$C$}}
\put(10,6){\makebox(0,0)[c]{$A$}}
\put(10,7){\makebox(0,0)[c]{$D$}}
\put(10,8){\makebox(0,0)[c]{$G$}}
\put(10,9){\makebox(0,0)[c]{$\spunkt$}}
\put(9.5,3.5){\line(1,0){1}}
\put(9.5,2.5){\line(1,0){1}}
\put(10.5,2.5){\line(0,1){1}}
\put(9.5,5.5){\line(1,0){1}}
\put(9.5,4.5){\line(1,0){1}}
\put(10.5,4.5){\line(0,1){1}}
%
%\put(9,7){\makebox(0,0)[c]{$\Rightarrow$}}
%
\end{picture}
\end{center}
\end{scriptsize}
\end{minipage}
%
\hspace{1cm}
%
\begin{minipage}[t]{5cm}
\begin{scriptsize}
\begin{center}
\setlength{\unitlength}{10pt}
\begin{picture}(11,11)(0,0)
% ******* 3. Bild ******* Umrandung ***********************
%
\put(0.5,0.5){\line(0,1){9}}
\put(9.5,0.5){\line(0,1){9}}
% 
\put(0.5,0.5){\line(1,0){9}}
\put(0.5,9.5){\line(1,0){9}}
\put(1,5){\makebox(0,0)[c]{$\spadesuit $}}
%\put(2,2){\makebox(0,0)[c]{$\spadesuit $}}
\put(3,7){\makebox(0,0)[c]{$\spadesuit $}}
%\put(4,1){\makebox(0,0)[c]{$\spadesuit $}}
\put(5,6){\makebox(0,0)[c]{$\spadesuit $}}
\put(6,3){\makebox(0,0)[c]{$\spadesuit $}}
\put(7,9){\makebox(0,0)[c]{$\spadesuit $}}
\put(8,8){\makebox(0,0)[c]{$\spadesuit $}}
\put(9,4){\makebox(0,0)[c]{$\spadesuit $}}
%
%*****Oben*************************************************** 
\put(1,10){\makebox(0,0)[c]{$C$}}
\put(2,10){\makebox(0,0)[c]{$E$}}
\put(3,10){\makebox(0,0)[c]{$D$}}
\put(4,10){\makebox(0,0)[c]{$F$}}
\put(5,10){\makebox(0,0)[c]{$A$}}
\put(6,10){\makebox(0,0)[c]{$B$}}
\put(7,10){\makebox(0,0)[c]{$\spunkt$}}
\put(8,10){\makebox(0,0)[c]{$G$}}
\put(9,10){\makebox(0,0)[c]{$\upunkt$}}
\put(1.5,9.5){\line(0,1){1}}
\put(2.5,9.5){\line(0,1){1}}
\put(1.5,10.5){\line(1,0){1}}
\put(3.5,9.5){\line(0,1){1}}
\put(4.5,9.5){\line(0,1){1}}
\put(3.5,10.5){\line(1,0){1}}
%
\put(4,9){\makebox(0,0)[c]{$\Uparrow$}}
%
%*****Rechts************************************************* 
%\put(10,1){\makebox(0,0)[c]{$F$}}
%\put(10,2){\makebox(0,0)[c]{$E$}}
\put(10,3){\makebox(0,0)[c]{$B$}}
\put(10,4){\makebox(0,0)[c]{$\upunkt$}}
\put(10,5){\makebox(0,0)[c]{$C$}}
\put(10,6){\makebox(0,0)[c]{$A$}}
\put(10,7){\makebox(0,0)[c]{$D$}}
\put(10,8){\makebox(0,0)[c]{$G$}}
\put(10,9){\makebox(0,0)[c]{$\spunkt$}}
%\put(9.5,3.5){\line(1,0){1}}
%\put(9.5,2.5){\line(1,0){1}}
%\put(10.5,2.5){\line(0,1){1}}
%
%\put(9,7){\makebox(0,0)[c]{$\Rightarrow$}}
%
\end{picture}
\end{center}
\end{scriptsize}
\end{minipage}
\end{center}
In der sich dann neu ergebenden Situation gibt man wiederum
diejenigen Punkten, die sowohl oben als auch rechts eingetragen wurden
den ihren Koordinaten entsprechenden Platz im Quadrat
$Q$. Da dies zumindest  f"ur den Startpunkt der neu hinzugekommenen Bahn
geschieht, nimmt nach diesem Schritt die Anzahl der Elemente von $E$, die
noch nicht eingeordnet sind, um mindestens 1 ab. \\[12pt]
\begin{center}
\begin{minipage}[t]{5cm}
\begin{scriptsize}
\begin{center}
\setlength{\unitlength}{10pt}
\begin{picture}(10,10)(0,0)
% ******* 4. Bild vor ******* Umrandung ***********************
%
\put(0.5,0.5){\line(0,1){9}}
\put(9.5,0.5){\line(0,1){9}}
% 
\put(0.5,0.5){\line(1,0){9}}
\put(0.5,9.5){\line(1,0){9}}
\put(1,5){\makebox(0,0)[c]{$\spadesuit $}}
%\put(2,2){\makebox(0,0)[c]{$\spadesuit $}}
\put(3,7){\makebox(0,0)[c]{$\spadesuit $}}
%\put(4,1){\makebox(0,0)[c]{$\spadesuit $}}
\put(5,6){\makebox(0,0)[c]{$\spadesuit $}}
\put(6,3){\makebox(0,0)[c]{$\spadesuit $}}
\put(7,9){\makebox(0,0)[c]{$\spadesuit $}}
\put(8,8){\makebox(0,0)[c]{$\spadesuit $}}
\put(9,4){\makebox(0,0)[c]{$\spadesuit $}}
%
%*****Oben*************************************************** 
\put(1,10){\makebox(0,0)[c]{$C$}}
\put(2,10){\makebox(0,0)[c]{$E$}}
\put(3,10){\makebox(0,0)[c]{$D$}}
\put(4,10){\makebox(0,0)[c]{$F$}}
\put(5,10){\makebox(0,0)[c]{$A$}}
\put(6,10){\makebox(0,0)[c]{$B$}}
\put(7,10){\makebox(0,0)[c]{$\spunkt$}}
\put(8,10){\makebox(0,0)[c]{$G$}}
\put(9,10){\makebox(0,0)[c]{$\upunkt$}}
\put(1.5,9.5){\line(0,1){1}}
\put(2.5,9.5){\line(0,1){1}}
\put(1.5,10.5){\line(1,0){1}}
\put(3.5,9.5){\line(0,1){1}}
\put(4.5,9.5){\line(0,1){1}}
\put(3.5,10.5){\line(1,0){1}}
%
%\put(2,9){\makebox(0,0)[c]{$\Uparrow$}}
%
%*****Rechts************************************************* 
\put(10,1){\makebox(0,0)[c]{$F$}}
\put(10,2){\makebox(0,0)[c]{$E$}}
\put(10,3){\makebox(0,0)[c]{$B$}}
\put(10,4){\makebox(0,0)[c]{$\upunkt$}}
\put(10,5){\makebox(0,0)[c]{$C$}}
\put(10,6){\makebox(0,0)[c]{$A$}}
\put(10,7){\makebox(0,0)[c]{$D$}}
\put(10,8){\makebox(0,0)[c]{$G$}}
\put(10,9){\makebox(0,0)[c]{$\spunkt$}}
\put(9.5,0.5){\line(1,0){1}}
\put(9.5,2.5){\line(1,0){1}}
\put(10.5,0.5){\line(0,1){2}}
%
%\put(9,7){\makebox(0,0)[c]{$\Rightarrow$}}
%
\end{picture}
\end{center}
\end{scriptsize}
\end{minipage}
%
\hspace{1cm}
%
\begin{minipage}[t]{5cm}
\begin{scriptsize}
\begin{center}
\setlength{\unitlength}{10pt}
\begin{picture}(10,10)(0,0)
% ******* 4. Bild ******* Umrandung ***********************
%
\put(0.5,0.5){\line(0,1){9}}
\put(9.5,0.5){\line(0,1){9}}
% 
\put(0.5,0.5){\line(1,0){9}}
\put(0.5,9.5){\line(1,0){9}}
\put(1,5){\makebox(0,0)[c]{$\spadesuit $}}
\put(2,2){\makebox(0,0)[c]{$\spadesuit $}}
\put(3,7){\makebox(0,0)[c]{$\spadesuit $}}
\put(4,1){\makebox(0,0)[c]{$\spadesuit $}}
\put(5,6){\makebox(0,0)[c]{$\spadesuit $}}
\put(6,3){\makebox(0,0)[c]{$\spadesuit $}}
\put(7,9){\makebox(0,0)[c]{$\spadesuit $}}
\put(8,8){\makebox(0,0)[c]{$\spadesuit $}}
\put(9,4){\makebox(0,0)[c]{$\spadesuit $}}
%
%*****Oben*************************************************** 
\put(1,10){\makebox(0,0)[c]{$C$}}
\put(2,10){\makebox(0,0)[c]{$E$}}
\put(3,10){\makebox(0,0)[c]{$D$}}
\put(4,10){\makebox(0,0)[c]{$F$}}
\put(5,10){\makebox(0,0)[c]{$A$}}
\put(6,10){\makebox(0,0)[c]{$B$}}
\put(7,10){\makebox(0,0)[c]{$\spunkt$}}
\put(8,10){\makebox(0,0)[c]{$G$}}
\put(9,10){\makebox(0,0)[c]{$\upunkt$}}
%\put(0.5,9.5){\line(0,1){1}}
%\put(2.5,9.5){\line(0,1){1}}
%\put(0.5,10.5){\line(1,0){2}}
%
%\put(2,9){\makebox(0,0)[c]{$\Uparrow$}}
%
%*****Rechts************************************************* 
\put(10,1){\makebox(0,0)[c]{$F$}}
\put(10,2){\makebox(0,0)[c]{$E$}}
\put(10,3){\makebox(0,0)[c]{$B$}}
\put(10,4){\makebox(0,0)[c]{$\upunkt$}}
\put(10,5){\makebox(0,0)[c]{$C$}}
\put(10,6){\makebox(0,0)[c]{$A$}}
\put(10,7){\makebox(0,0)[c]{$D$}}
\put(10,8){\makebox(0,0)[c]{$G$}}
\put(10,9){\makebox(0,0)[c]{$\spunkt$}}
%\put(9.5,0.5){\line(1,0){1}}
%\put(9.5,2.5){\line(1,0){1}}
%\put(10.5,0.5){\line(0,1){2}}
%
%\put(9,7){\makebox(0,0)[c]{$\Rightarrow$}}
%
\end{picture}
\end{center}
\end{scriptsize}
\end{minipage}
\end{center}
Nach endlich vielen Schritten dieser Art kommt man deshalb in  einen
Zustand, bei dem alle bis dahin eingetragenen Punkte von $E$ schon
ihren Platz im Quadrat gefunden haben. Das bedeutet aber, da"s die
Menge dieser Punkte sowohl unter der Operation von $s$ als auch der
Operation von $u$ abgeschlossen  und daher gleich $E$ ist; wir sind
dann fertig. Aufgrund der Konstruktion ist es klar, da"s in jeder
Zeile und in jeder Spalte von $Q$ genau ein Element von $E$ seinen
Platz gefunden hat, die enstandene Teilmenge von $Q$ ist daher der
Graph einer Permutation von $[n]$. Diese Permutation ist konnex, denn
w"are sie es nicht, dann w"are man bei der Konstruktion schon in einen
unter $s$ und $u$ stabilen Zustand gekommen, ohne dabei alle Elemente
aus $E$ ausgesch"opft zu haben. Weil $E$ eine transitive $s$--$u$ Menge
ist, geht dies nat"urlich nicht.
 
Wir haben hiermit also eine Abbildung angegeben, die jeder doppelt
punktierten transitiven $s$--$u$ Menge eine konnexe Permutation von
$[n]$ zuordnet. Diese Konstruktion ist invers zu der im ersten Teil
gegebenen Konstruktion und beide zusammen liefern die angek"undigte
Bijektion.\\[6pt] 

\noindent
{\sc Anmerkungen:}\\
Betrachtet man f\"ur eine konnexe Permutation zus\"atzlich noch die
Statistik der Inversionen, dann erh\"alt man ein q--Analogon
\cite{Zen87} f\"ur die erzeugende Funktion. Hierf\"ur gibt es noch
keine Interpretation im Rahmen der 
Cayley Diagramme.\\
Das Untergruppen-Modell l\"a{\ss}t sich
auf mehrere Generatoren verallgemeinern \cite{DrF87},   
wo eine Bijektion zu einem verallgemeinerten Modell von konnexen
Permutationen
konstruiert wird.\\
$Rekorde$ (links--rechts Maxima) sind auch fr\"uher schon betrachtet
\cite{Cha52}, \cite{FoS54} und wiederentdeckt \cite{Imh83} worden.
Eine alternative
Darstellung f\"ur Permutationen ist ein Paar transitiver gerichteter
Graphen,
die die Inversionen und nicht-Inversionen darstellen, deren Vereinigung den
vollst\"andigen gerichteten kreisfreien Graphen ergibt
\cite[5.1.1 Ex 11]{Knu73}. Die Konnexit\"at
entspricht in dieser Darstellung dem Zusammenhang des Inversionsgraphen, die
r--l Minima und l--r Maxima entsprechen den Quellen und Senken des
Inversionsgraphen. Die Symmetrieoperationen des Quadrates werden
\"uberf\"uhrt in das  
Umdrehen der gerichteten Kanten oder Austauschen des Graphenpaares. Eine 
Verbindung zu Robinson-Schensted \cite{Vie82} ist nicht zu erkennen, 
obwohl die Bilder bei {\sc Viennot} \"ahnlich aussehen.
In der Sprache von {\sc Viennot} sind die links--rechts Maxima die 
nord--westlich beleuchteten Elemente und die 
rechts--links Minima die s\"ud--\"ostlich beleuchteten Elemente.

\footnotesize
\begin{thebibliography}{Com74}
%
\bibitem[CaF69]{CaF69}
{\sc Cartier} (P.) et {\sc Foata} (D.) ---
{\em Probl\`emes combinatoires de commutation et r\'earrangements},
Lecture Notes in Mathematics 85, Springer (1969).
%
\bibitem[Cha52]{Cha52}
{\sc Chandler} (K.N.) ---
{\em The Distribution and Frequency of Record Values},
Journal of the Royal Statistical Society B 14 (1952) 220--228.
%
\bibitem[Com74]{Com74}
{\sc Comtet} (L.) ---
{\em Advanced Combinatorics},
Dordrecht (1974).
%
\bibitem[DrF85]{DrF85}
{\sc Dress} (A.W.M.) und {\sc Franz} (R.) ---
{\em Parametrizing the subgroups of finite index in a free group and
related topics}, 
Bayreuther Mathematische Schriften 20 (1985) 1--8.
%
\bibitem[DrF87]{DrF87}
{\sc Dress} (A.W.M.) und {\sc Franz} (R.) ---
{\em Zur Parametrisierung von Untergruppen freier Gruppen},
Beitr\"age zur Algebra und Geometrie 24 (1987) 125--134.
%
\bibitem[DuK86]{DuK86}
{\sc Dumont} (D.) et {\sc Kreweras} (G.) ---
{\em Sur le d\'eveloppement d'une fraction continue li\'ee \`a la s\'erie
hyp\'ergeom\'etrique et son interpr\'etation en termes de records et
anti-records dans les permutations},
S\'eminaire Lotharingien de Combinatoire, $14^{e}$ session,
Publ. I.R.M.A. Strasbourg, (1986), 67--74;\\
siehe auch:
European Journal of Combinatorics 9 (1988) 27--32.
%
\bibitem[FoS70]{FoS70}
{\sc Foata} (D.) et {\sc Sch\"utzenberger} (M.P.) ---
{\em Th\'eorie G\'eom\'etrique des Polyn\^omies Eul\'eriens},
Lecture Notes in Mathematics 138, Springer (1970).
%
\bibitem[FoS54]{FoS54}
{\sc Foster} (F.G.) and {\sc Stuart} (A.) ---
{\em Distribution Free Tests in Time-Series Based on the Breaking of
Records} (together with the subsequent discussion),
Journal of the Royal Statistical Society B 16 (1954) 1--22.
%
\bibitem[GoJ83]{GoJ83}
{\sc Goulden} (I.P.) and {\sc Jackson} (D.M.) ---
{\em Combinatorial Enumeration},
John Wiley, New York (1983).
%
\bibitem[Hal59]{Hal59}
{\sc Hall} (M.) ---
{\em The Theory of Groups},
Macmillan, New York (1959).
%
\bibitem[Imh83]{Imh83}
{\sc Imhof} (J.P.) ---
{\em Stirling Numbers and Records},
Journal of Combinatorial Theory A 34 (1983) 252--254.
%
\bibitem[Knu68]{Knu68}
{\sc Knuth} (D.E.) ---
{\em The Art of Computer Programming I (Fundamental Algorithms)},
Addison-Wesley, Reading (1968, 2nd Edition 1973).
%
\bibitem[Knu73]{Knu73}
{\sc Knuth} (D.E.) ---
{\em The Art of Computer Programming III (Sorting and Searching)},
Addison-Wesley, Reading (1973).
%
\bibitem[Sta78]{Sta78}
{\sc Stanley} (R.P.) ---
{\em Generating Functions},
in: Studies in Combinatorics (G.C. Rota, editor),
MAA Studies in Mathematics 17 (1978).
%
\bibitem[Vie82]{Vie82}
{\sc Viennot} (G.) ---
{\em Chain and Antichain Families Grids and Young Tableaux},
in: M. Pouzet, D. Riachard; {\em Orders: Descriptions and Rules},
Conference on Ordered Sets and their Applications (1982, l'Arbresle),
Annals of Discrete Mathematics 23 (1984) 409--464.	
%
\bibitem[Zen87]{Zen87}
{\sc Zeng} (J.) ---
{\em Records, Antirecords et Permutations Discordantes}
S\'eminaire Lotharingien de Combinatoire, $15^{e}$ session,
Publ. I.R.M.A. Strasbourg, (1987), 121--128.\\
siehe auch:
European Journal of Combinatorics 10 (1989) 103--110.
%
\end{thebibliography}
\end{document}
