\documentclass[12pt,twoside]{article}
\usepackage{german,amsfonts}
%************************************************************************
%              Andreas Dress und Christian Siebeneicher                 *
%                                                                       *
%                   Ein Lemma ueber Perlenketten                        *
%                                                                       *
%************************************************************************

%\author{Andreas~W.M.~Dress\\Christian~Siebeneicher}
%\title{Ein Lemma "uber Perlenketten}
%\pagestyle{empty}
%\pagestyle{myheadings} 
%\markboth{\rm A. DRESS UND CH.
%SIEBENEICHER}{\rm PERLENKETTEN}
\date{ }
\addtolength{\topmargin}{-34pt}
\addtolength{\textheight}{68pt}
\hoffset=.25in
\voffset=.5in
\setlength{\parindent}{0pt}
\setlength{\parskip}{5pt plus 2pt minus 1pt}
\frenchspacing
\sloppy

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

\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} 
%\maketitle
%\clearpage
\vspace*{2.4cm}
\begin{center}
{\bf EIN LEMMA "UBER PERLENKETTEN}\\[3mm]
\begin{scriptsize}
VON
\end{scriptsize}\\[3mm]
{\sc Andreas} DRESS
\begin{scriptsize} 
UND
\end{scriptsize}
{\sc Christian} SIEBENEICHER\\[1.2cm]
\end{center}
\begin{footnotesize}
{\bf Abstract:} We establish a diagram providing various bijections
related to the theory of necklaces (or `aperiodic words') and
clarifying the relationship between these bijections.
\end{footnotesize}
\medskip

Ist $E$ eine endliche Menge, $\sigma:E \longrightarrow E$ eine
zyklische Permutation von $E$ und $f:E \longrightarrow A$ eine
Abbildung von $E$ in die Menge $A$, dann nennt man das Paar
$(\sigma,f)$ eine {\em Perlenkette} ("uber $E$). Die Elemente der
Menge $E$ sind die {\em Perlen} des Perlenkette. Diese sind vermittels
der Abbildung $f$ durch Farben aus $A$ gef"arbt; die Perle 
$\epsilon \in E$ hat die Farbe $f(\epsilon)$.  Die Komposition
$f\circ\sigma^{i}$ liefert f"ur jedes $i\in \N=\{1,2,\dots\}$ eine
weitere F"arbungsabbildung und also auch eine weitere Perlenkette
$(\sigma,f\circ\sigma^{i})$. Stimmt die urspr"ungliche Perlenkette
$(\sigma,f)$ f"ur ein $i$ mit $\sigma^{i}\ne 1_{E}$ mit $(\sigma,f)$
"uberein, dann sagt man, $(\sigma,f)$ sei {\em periodisch}. Eine nicht
periodische Perlenkette hei"st {\em aperiodisch} oder {\em primitiv}.

Ist die Permutation $\sigma$ nicht notwendigerweise \mbox{zyklisch},
dann erhalten wir anstelle einer Perlenkette eine ganze Familie von
Perlenketten ("uber $E$), eine {\em Auslage von Perlenketten}.  Die
einzelnen Perlenketten der Auslage sind gegeben durch die
Einschr"ankung der Abbildung $ f:E \longrightarrow A$ auf die Zyklen
von $\sigma$.

Hat man $a$ Farben zur Verf"ugung ($\# A = a < \infty $), dann gibt es
in einer $n$--elementigen Menge $E$ genau $n!\cdot a^{n}$ Auslagen von
Perlenketten. Die exponentielle erzeugende Funktion f"ur die Auslagen
von Perlenketten ist daher gleich
\[
1+\sum_{n=1}^{\infty}n!\cdot a^{n}\,\frac{t^{n}}{n!}=\frac{1}{1-at}.
\]
F"ur diese hat man die Produktzerlegung
\[
\frac{1}{1-at}=
\prod_{n=1}^{\infty}\left(\frac{1}{1-t^{n}}\right)^{M(a,n)},
\]
die sogenannte {\em zyklotomische Identit"at}, mit ganzzahligen
Exponenten
\[
M(a,n)=\frac{1}{n}\sum_{d|n}\mu(d)a^{\frac{n}{d}}
\]
($\mu$ die M"obius--Funktion). Die Exponenten in der Produktzerlegung
berechnet man am einfachsten, wenn man zur logarithmischen Ableitung
der zyklotomischen Identit"at "ubergeht (cf.~\cite{G}). Da $M(a,n)$
gleich der Anzahl der primitiven Perlenketten der L"ange $n$ ist, lag
es nahe, nach einer kombinatorischen Interpretation der zyklotomischen
Identit"at zu suchen. In \cite{MR} liefern {\sc N.Metropolis} und
\mbox{\sc G.-C.Rota} eine solche Interpretation. Die zentrale Rolle
hierbei spielt eine Bijektion zwischen bestimmten Teilmengen der Menge
der Auslagen von Perlenketten "uber
\(
[n]:=\{1,\dots,n\}
\)
und der Menge \( [n]! \) der Permutationen von
\( [n] \).
Ein andere kombinatorische Interpretation der zyklotomischen
Identit"at ergibt sich \mbox{(cf.~\cite{DS1})}, wenn man symmetrische
Potenzen der Menge $P(A)$ der {\em periodischen Funktionen} auf der
Menge \Z\ der ganzen Zahlen mit Werten in der Menge $A$ betrachtet.

Wir wollen hier nun eine recht nar"urlich erscheinende Bijektion
angeben, die diese beiden Aspekte als Spezialf"alle enth"alt.  Hierzu
betrachten wir f"ur eine Perlenkette $(\sigma,f)$ und eine Perle
$\epsilon \in E$ die Abbildung
\[
f_{\sigma}^{\epsilon}:\Z \longrightarrow A \qquad i \mapsto
f(\sigma^{i}\,\epsilon),
\]
die offensichtlich eine {\em periodische} Funktion auf \Z\ mit Werten
in $A$ definiert. Man kann sie als Perle einer neuen Perlenkette
auffassen, wenn man auf der Menge $P(A)$ die {\em Shift}--Abbildung
$\alpha:P(A) \longrightarrow P(A)$ dadurch definiert, da"s man f"ur 
$g\in P(A)$ setzt:
\[
 (\alpha\, g)(i):= g(i+1) \quad \mbox{f"ur alle} \quad i \in \Z.
\]
Auf der Bahn
\mbox{$\pi_{(\sigma,f)}=\{f_{\sigma}^{\eta}\mid \eta \in E \}$ }
von $f_{\sigma}^{\epsilon}$, der sogenannten {\it Shift--Periode} von
$(\sigma,f)$, induziert die Shift--Abbildung $\alpha$ eine zyklische
Permutation, und man erh"alt eine Perlenkette, wenn man die Perlen
(die Elemente) von $\pi_{(\sigma,f)}$ mittels der Evaluationsabbildung
an der Stelle $0$, also mittels
\[
ev:P(A) \longrightarrow A \qquad g \mapsto g(0)
\]
f"arbt. Wir bezeichnen diese Perlenkette ebenfalls mit
$\pi_{(\sigma,f)}$.  Sie ist offensichtlich primitiv.  Geht man von
einer Auslage von Perlenketten aus, dann erh"alt man auf diese Weise
eine Auslage $\Pi_{(\sigma,f)}$ von primitiven Perlenketten "uber der
nunmehr ebenfalls mit $\Pi_{(\sigma,f)}$ bezeichneten Menge
$\{f_{\sigma}^{\eta}\mid \eta \in E \}$.  Wir merken an, da"s in der
Auslage $\Pi_{(\sigma,f)}$ in der Regel weniger Perlenketten enthalten
sind als in der urspr"unglichen Auslage $(\sigma,f)$.

Um diesen Informationsverlust wenigstens teilweise wieder
wettzumachen, betrachtet man die Funktion
\[
u_{(\sigma,f)}:P(A) \longrightarrow \No\qquad u_{(\sigma,f)}(g):=
\#\{\epsilon \in E\mid f_{\sigma}^{\epsilon} = g \}.
\]
Sie veschwindet au"serhalb von $\Pi_{(\sigma,f)}$ und ist konstant auf
den Shift--Perioden der zu $(\sigma,f)$ geh"origen Perlenketten.  Der
konstante Wert von $u_{(\sigma,f)}$ auf der Shift--Periode $\pi$ ist
gleich der Anzahl derjenigen Perlen aus $E$, die eine beliebige aber
feste Perle von $\pi$ als zugeh"orige periodische Funktion haben. Ist
$l$ die L"ange der Periode $\pi$, dann ist die Anzahl der Perlen aus
$E$, deren zugeh"orige periodische Funktion in $\pi$ liegt, gleich $l
\cdot u(\pi)$.  Insbesondere folgt, da"s die Menge
\[
[u_{(\sigma,f)}] := \{(g,k)\mid g \in P(A) \mbox{ und } 1 \le k \le
u_{(\sigma,f)}(g)\}\subset P(A)\times \No
\]
die gleiche Kardinalit"at hat wie die Menge $E$.

F"ur eine vollst"andige Rekonstruktion der urspr"unglichen Auslage von
Perlenketten aus der zugeh"origen Auslage von primitiven Perlenketten
ist es n"utzlich (n"otig?), die Tr"agermenge $E$ der Perlenkette zu
normieren. Wir w"ahlen $E=[n]=\{1,\dots,n\}$.  Die nat"urliche Ordnung
von $[n]$ erlaubt es dann, die Funktion
\[
\begin{array}{c}
k_{(\sigma,f)}:[n] \longrightarrow \No \\[6pt]
\nu \mapsto k_{(\sigma,f)}(\nu):=\#\{\mu \in [n] \mid 
\mu \le \nu \, \mbox{ und }\, f_{\sigma}^{\mu} = f_{\sigma}^{\nu}\}
\end{array}
\]
zu definieren und mit ihrer Hilfe die Abbildung
\[
[n] \longrightarrow P(A)\times \No \qquad
\nu \mapsto (f_{\sigma}^{\nu},k_{(\sigma,f)}(\sigma\,\nu))
\]
zu konstruieren.  Diese Abbildung ist injektiv, und ihre
Einschr"ankung auf das Bild liefert eine Bijektion
\(
\Phi_{(\sigma,f)}:[n] \longrightarrow [u_{(\sigma,f)}].
\)

Wir zeigen, da"s die Auslage $(\sigma,f)$ durch das Paar
\mbox{$(u_{(\sigma,f)},\Phi_{(\sigma,f)})$} eindeutig bestimmt ist.
Hierzu setzen wir $u:=u_{(\sigma,f)}$, $\Phi:=\Phi_{(\sigma,f)}$ und
$\Phi(\nu):=(g_{\nu},k_{\nu})$ und betrachten die ebenfalls mit $ev$
bezeichnete Abbildung
\[
ev: P(A)\times \No \longrightarrow A \qquad (g,k) \mapsto g(0).
\]
Dann hat man:
\begin{itemize}
\item   \( \displaystyle
        ev\circ \Phi_{(\sigma,f)}(\nu)  = 
        ev(f_{\sigma}^{\nu},k_{(\sigma,f)}(\sigma \nu))         
        = f_{\sigma}^{\nu}(0)
        = f(\nu),       \)      
        und man sieht, da"s die
        F"arbungsabbildung $f$ eindeutig durch das Paar         
        \(
        (u_{(\sigma,f)},\Phi_{(\sigma,f)})      
        \)      
        bestimmt ist.
\item   \( \displaystyle
        (g_{\sigma\,\nu},k_{\sigma\,\nu})
                =\Phi_{(\sigma,f)}(\sigma\,\nu) 
        = (f_{\sigma}^{\sigma\,\nu},k_{(\sigma,f)}
                                (\sigma(\sigma\,\nu))),
        \)\\    
        und also\\
        \(\begin{array}{ccl}
        g_{\sigma\,\nu}(i) 
                &=&f_{\sigma}^{\sigma\,\nu}(i) 
        =f(\sigma^{i}(\sigma\,\nu))
        =f(\sigma^{i+1}\,\nu)=f_{\sigma}^{\nu}(i+1)\\
                &=&g_{\nu}(i+1) \\ &=&\alpha\,g_{\nu}(i).
        \end{array}\)\\
        Es ist daher \( g_{\sigma \nu}=\alpha \, g_{\nu}\),     
        und folglich gilt       
        \(
                \sigma\,\nu \in \{ \mu \in [n] \mid g_{\mu}
                =\alpha\,g_{\nu} \}.
        \) 
        Schreibt man also\\     
        \(
        \{\mu \in [n]\mid g_{\mu} 
        = \alpha\,g_{\nu}\}     
        = \{\mu_{1},\mu_{2},\dots,\mu_{u(g_{\nu})}\}\) \\ 
        mit 
        $\mu_{1} < \mu_{2} < \dots < \mu_{u(g_{\nu})}$, 
        dann ist $\sigma\,\nu =\mu_{k_{\nu}}$ 
        aufgrund der
        Definition der Abbildung $k_{(\sigma,f)}\circ\sigma$.\, 
        Der Wert der Permutation $\sigma$ auf dem Element 
        $\nu \in [n]$ ist also durch das
        Element $\Phi(\nu)=(g_{\nu},k_{\nu})$ in 
        $[u]$ festgelegt und damit
        ist auch die Permutation $\sigma$ eindeutig durch 
        das Paar
        \(
        (u_{(\sigma,f)},\Phi_{(\sigma,f)})
        \)
        bestimmt.
\end{itemize}
Insgesamt haben wir also eine bijektive Korrespondenz zwischen den
Auslagen von Perlenketten in $[n]$ und den zugeh"origen Paaren
\(
(u_{(\sigma,f)},\Phi_{(\sigma,f)}).
\)
Diese erh"alt einen konzeptionellen Rahmen wenn wir\\[6pt]  
die {\bf Mengen}\\[9pt]
\mbox{ \(\displaystyle s^{n}(P(A))\! := \!
        \{ u\! : \! P(A) \rightarrow \No \mid \!\!
        \sum_{g \in P(A)} \! \!\! u(g)= n  
        \mbox{ , } u(g)\!=\!u(\alpha g) 
        \mbox{ f"ur alle } g\! \in \!P(A) \}\)    }\\[3pt]
\( S^{A}(n) := 
\{(u,\Phi) \mid 
u \in s^{n}(P(A)),\Phi:[n] \longrightarrow [u] \, 
\mbox{ bijektiv}\} \)\\[9pt] 
und die {\bf Abbildungen}\\[9pt]
$p:S^{A}(n) \rightarrow A^{[n]}\; 
: \; (u,\Phi) \mapsto ev \circ \Phi $\\[6pt] 
$q:[n]!\times A^{[n]}\longrightarrow s^{n}(P(A)) \; : \;
(\sigma,f) \mapsto u_{(\sigma,f)}$ \\[9pt] betrachten und dann alles
in dem folgenden Diagramm arrangieren,\\
\begin{footnotesize}
\begin{center}
\setlength{\unitlength}{.6pt}
\begin{picture}(410,190)(0,0) 
% 
% das erste Argument legt den Rahmen des Bildes fest.  
% das zweite Argument erlaubt es, das Bild 
% nach rechts und oben zu schieben.  
%
%---------------------------------------------------------------- 
%********** OBEN ******************************* 
%
\put(195,180){\makebox(0,0)[c]{$[n]!\times A^{[n]} $}}
% 
% ********** MITTE ******************************* 
%
\put(105,95){\makebox(0,0)[r]{$A^{[n]} $}}
%
\put(285,95){\makebox(0,0)[l]{$s^{n}(P(A))$}}
% 
% **********UNTEN ******************************* 
%
\put(195,10){\makebox(0,0)[c]{$S^{A}(n)$}}
% 
% 
% ************* Pfeile von Oben zur Mitte ********************* 
%
\put(168,163){\vector(-1,-1){56}}
%
\put(222,163){\vector(1,-1){56}}
% 
%-------------------------------------------------------------
%
%************* Der senkrechte Pfeil von Oben nach Unten ******
%
%\put(195,163){\vector(0,-1){140}} 
%
%---------------------------------------------------------------- 
%************* Pfeile von Unten zur Mitte ********************* 
%
\put(165,26){\vector(-1,1){56}}
%
\put(225,26){\vector(1,1){56}}
% 
%******************** Beschriften *****************************
%
\put(130,135){\makebox(0,)[r]{$pr_{2}$}}
%
\put(260,135){\makebox(0,0)[l]{$q$}}
%
\put(130,51){\makebox(0,0)[r]{$p$}}
%
\put(260,51){\makebox(0,0)[l]{$pr_{1}$}}
% 
%\put(105,95}{\makebox(0,0)[l]{$\Psi$}}
\end{picture}\\
\end{center}
\end{footnotesize}
% 
in dem $pr_{1}$ und $pr_{2}$ die kanonischen Projektionen auf den
ersten bzw. den 

\pagebreak
zweiten Faktor sind und $[n]!$ die Menge der
Permutationen der Menge $[n]$ bezeichnet.


Mit diesen Definitionen hat man dann das folgende\\[9pt]

{\bf Lemma}: {\em Es gibt eine Bijektion
\( 
\; \Psi:[n]!\times A^{[n]}\longrightarrow S^{A}(n), \;
\)
die das Diagram kommutativ erg"anzt:}\\
\begin{footnotesize}
\begin{center}
\setlength{\unitlength}{.6pt}
\begin{picture}(410,190)(0,0)
% 
%-----------------------------------------------------------
%********** OBEN ******************************* 
%
\put(195,180){\makebox(0,0)[c]{$[n]!\times A^{[n]} $}}
% 
% ********** MITTE ******************************* 
%
\put(105,95){\makebox(0,0)[r]{$A^{[n]} $}}
%
\put(285,95){\makebox(0,0)[l]{$s^{n}(P(A))$}}
% 
% ********** UNTEN ******************************* 
%
\put(195,10){\makebox(0,0)[c]{$S^{A}(n)$}}
% 
% 
% ************* Pfeile von Oben zur Mitte ********************* 
%
\put(168,163){\vector(-1,-1){56}}
%
\put(222,163){\vector(1,-1){56}}
% 
%---------------------------------------------------------------
%************* Der senkrechte Pfeil von Oben nach Unten ******** 
%
\put(195,163){\vector(0,-1){140}}
% 
%-------------------------------------------------------------
%************* Pfeile von Unten zur Mitte ********************* 
%
\put(165,26){\vector(-1,1){56}}
%
\put(225,26){\vector(1,1){56}}
% 
%******************** Beschriften ************************
%
\put(130,135){\makebox(0,)[r]{$pr_{2}$}}
%
\put(260,135){\makebox(0,0)[l]{$q$}}
%
\put(130,51){\makebox(0,0)[r]{$p$}}
%
\put(260,51){\makebox(0,0)[l]{$pr_{1}$}}
%
\put(200,95){\makebox(0,0)[l]{$\Psi$}}
\end{picture}
\end{center}
\end{footnotesize}
\vspace{6pt}
{\bf Beweis:} Man definiert die Abbildung
\(
\Psi:[n]!\times A^{[n]} \longrightarrow S^{A}(n)
\)
durch
\(
(\sigma,f) \mapsto (u_{(\sigma,f)},\Phi_{(\sigma,f)}).
\)
Es gilt dann
\[
pr_{1}\circ \Psi(\sigma,f)=u_{(\sigma,f)}=q(\sigma,f),
\]
das rechte Dreieck des Diagrammes ist also kommutativ. 
Ferner hat man f"ur jedes $\nu \in [n]$
\[
\begin{array}{ccl}
p\circ\Psi(\sigma,f)(\nu) 
        & = & ev(\Phi_{(\sigma,f)}(\nu)) 
         =ev(f_{\sigma}^{\nu},k_{(\sigma,f)}(\sigma \nu))\\[6pt]
        & = & f_{\sigma}^{\nu}(0) = f(\sigma^{0}\,\nu)\\[6pt] 
        & = & f(\nu),
\end{array}
\]
$\Psi$ erg"anzt also in der Tat das Diagramm kommutativ.

Die Injektivit"at von $\Psi$ ist das unmittelbare Ergebnis der
Diskussion der Zuordnung
\(
(\sigma,f) \mapsto (u_{(\sigma,f)},\Phi_{(\sigma,f)}),
\)
und diese legt dar"uber hinaus auch nahe, wie man zu gegebenem
\( 
(u,\Phi) \in S^{A}(n) 
\) 
ein Urbild in 
\(
[n]!\times A^{[n]}
\)
findet.                       \hfill $\Box$
%
\begin{corollary}
Es gibt eine Bijektion zwischen der Menge der Auslagen von
Perlenketten in $[n]$ mit Shift--Periode $\pi$ und der Menge $[n]!$
der Permutationen von $[n]$ (cf.~\mbox{\rm \cite{MR}}).
\end{corollary}
%
{\bf Beweis}: Ist $l$ die L"ange der Periode $\pi$, dann ist 
$n=k\cdot l$ 
mit passendem $k$.  Sei $u:P(A) \longrightarrow \No$ diejenige
Funktion, die auf jedem der Elemente von $\pi$ den Wert $k$ hat und
au"serhalb von $\pi$ verschwindet. Die Faser $q^{-1}(u)$ von $q$ "uber
$u$ ist offensichtlich gleich der Menge der Auslagen von Perlenketten
in $[n]$ mit der Shift--Periode $\pi$. Die Einschr"ankung der
Bijektion $\Psi$ auf $q^{-1}(u)$ liefert eine Bijektion auf die Menge
\mbox{ $pr_{1}^{-1}(u)=\{(u,\Phi)\in S^{A}(n) 
\mid \Phi:[n] \rightarrow [u] \mbox{ bijektiv}\}$}.
 Die Komposition von $\Phi$ mit einer beliebigen Bijektion $[u]
\rightarrow [n]$ liefert dann eine Bijektion der gew"unschten Art.
\hfill $\Box$

Die Fasern der Projektionsabbildungen $pr_{1}$ und $pr_{2}$ haben
jeweils die Kardinalit"at $n!$. Deshalb haben auch die Fasern der
Abbildungen $p$ und $q$ die Kardinalit"at $n!$. Insbesondere sind
daher die Mengen
\( s^{n}(P(A)) \) und $A^{[n]}$ gleich m"achtig,
was in \cite{DS1} in anderer Weise gezeigt wurde.  Ist 
$\#A = a < \infty$, dann erh"alt man das 
%
\begin{corollary}
Ist
\[
Z(P(A),t):=1+\sum_{n=1}^{\infty}\#s^{n}(P(A))\cdot t^{n}
\]
die $\zeta$--Funktion der Menge $P(A)$ im Sinne von 
\mbox{\rm \cite{DS1}}, dann gilt
\[
Z(P(A),t)=\frac{1}{1-at}.
\]
\end{corollary}
%
Die Menge $P(A)$ zerf"allt unter der Shift--Abbildung in disjunkte
Zyklen.  Da die $\zeta$--Funktion einer disjunkten Vereinigung gleich
dem Produkt der \mbox{$\zeta$--Funktionen} der einzelnen Summanden ist
\mbox{(cf.~\cite{DS1})}, ist $Z(P(A),t)$ gleich dem Produkt der
$\zeta$--Funktionen der in $P(A)$ gelegenen Zyklen. Die
\mbox{$\zeta$--Funktion} eines Zyklus der L"ange $n$ ist aber gleich
$\displaystyle \frac{1}{1-t^{n}}$
\mbox{(cf.~\cite{DS1})}.
Das ergibt:
\begin{corollary}
Die $\zeta$--Funktion der Menge $P(A)$ der periodischen Funktionen auf
\Z\ mit Werten in der Menge $A$ besitzt die
Produktzerlegung
\[
\frac{1}{1-at}=
\prod_{n=1}^{\infty}\left(\frac{1}{1-t^{n}}\right)^{M(a,n)},
\]
in der $M(a,n)$ gleich der Anzahl der Zyklen der L"ange $n$ in $P(A)$
oder, "aquivalent hierzu, gleich der Anzahl der primitiven
Perlenketten der L"ange $n$ ist.
\end{corollary}
Wie uns {\sc Volker Strehl} mitteilte, haben {\sc N.G.~de~Bruijn} und
{\sc D.A.~Klarner} in \cite{dBK} eine explizite Bijektion $
A^{[n]}\longrightarrow s^{n}(P(A))$ angegegeben.

Im Rahmen unserer "Uberlegungen l"a"st sich zur Existenz solcher
Bijektionen folgendes sagen. Sind 
$s:A^{[n]}\longrightarrow [n]!\times A^{[n]}$ 
und 
$t:s^{n}(P(A))\longrightarrow [n]!\times A^{[n]}$ 
zwei Schnitte, d.h. ist 
$pr_{1}\circ s = 1_{A^{[n]}}$ 
und 
$p \circ t = 1_{s^{n}(P(A))}$, 
dann induzieren die Einschr"ankungen von 
$pr_{1}$
bzw. von $p$ auf das Bild von $s$ bzw. das Bild von $t$ Bijektionen
$pr_{1}:\mbox{Bild}\;s \longrightarrow A^{[n]}$ bzw.
$p:\mbox{Bild}\;t \longrightarrow s^{n}(P(A))$.  
Ist $\mbox{Bild}\;s = \mbox{Bild}\;t$,
 dann sind $p \circ s$ und $pr_{1} \circ t$ zueinander
inverse Bijektionen zwischen $A^{[n]}$ und $s^{n}(P(A))$.

Schnitte der angegebenen Art erh"alt man, wenn die Menge $A$ linear
geordnet ist und man auf der Menge $A^{*}$ aller W"orter "uber $A$ die
lexikographische Ordnung betrachtet.

Den Elementen der Mengen $A^{[n]}$ und $P(A)$ kann man in
naheliegender Weise W"orter zuordnen: der Abbildung $f:[n]
\longrightarrow A$ das Wort $f(1)\cdots f(n)$ und der periodischen
Funktion $g$ mit der Periode $k$ das Wort $g(1)\cdots g(k)$.  Das
erlaubt dann die Definition induzierter linearer Ordnungen auf
$A^{[n]}$ und $P(A)$:
\begin{itemize}
\item   $f \preceq f'$ genau dann, wenn  
        $f(1)\cdots f(n) \preceq f'(1)\cdots f'(n)$,
\item   $g \preceq g'$ genau dann, wenn
        $g(1)\cdots g(k) \preceq g'(1)\cdots g'(k')$ ist.
\end{itemize}
Diejenigen periodische Funktionen, die minimal sind in ihrer
Shift--Periode, nennt man {\it normal}, die zugeh"origen W"orter sind
die sogenannten {\it Lyndon--W"orter}.  F"ur Lyndon--W"orter hat man
(cf.~\cite[p.~362]{BP} und \cite[p.~67]{L})
\begin{itemize}
\item   Ein Wort ist genau dann ein Lyndon--Wort, wenn es kleiner ist
        als jeder seiner echten Rechtsfaktoren.
\item   Sind $l$ und $m$ Lyndon--W"orter und ist $l \preceq m$, dann ist
        auch $lm$ ein Lyndon--Wort (und es ist $lm \preceq m$).
\item   Ist $w=l_{1}l_{2}\cdots l_{k}$ ein Produkt von Lyndon--W"ortern, 
        und
        ist $l_{1} \succeq l_{2} \succeq \dots \succeq l_{k}$, dann
        ist $l_{k}$ der kleinste Rechts--Faktor von $w$.
\end{itemize}
Ist $f \in A^{[n]}$, dann sei $f=f_{1}f_{2}\cdots f_{k}$ dasjenige
Produkt von Lyndon--W"ortern, bei dem $f_{k}$ ein m"oglichst kleiner
Rechts--Faktor von $f$ ist (mit der L"ange $l_{k}$), $f_{k-1}$ ein
m"oglichst kleiner Rechts--Faktor von dem Restwort von $f$, das
entsteht, wenn man den Rechtsfaktor $f_{k}$ wegl"a"st usw. Es gilt
dann $f_{1} \succeq f_{2} \succeq \dots \succeq f_{k}$, und wenn wir
gleiche Faktoren zusammenfassen k"onnen wir schreiben:
\[
f = f_{1}^{u_{1}}\cdots f_{k}^{u_{k}}.
\]
Die W"orter $f_{1}^{u_{1}},f_{2}^{u_{2}},\dots,f_{k}^{u_{k}}$
definieren dann Abbildungen
\[
\begin{array}{ccl}
f_{1}^{u_{1}}& : & \{1,\dots,u_{1}l_{1}\}\longrightarrow A,\\
f_{2}^{u_{2}}& : & \{u_{1}l_{1}+1,\dots,u_{1}l_{1}+u_{2}l_{2}\}
                                        \longrightarrow A,\\
\vdots       &   &        \\
f_{k}^{u_{k}}& : & \{u_{1}l_{1} + \dots + u_{k-1}l_{k-1}+1,\dots,n\}
                                        \longrightarrow A,
\end{array}
\]
die nat"urlich nichts anderes sind als die Einschr"ankungen von $f$
auf das jeweilige Teilintervall von $[n]$.  Betrachtet man auf jedem
dieser Teilintervalle die zyklische Permutation, die jedem Element des
Intervalls das n"achstgr"o"sere Element zuordnet und das letzte
Element auf das erste abbildet, dann erh"alt man insgesamt eine
Permutation $\sigma_{f}$ von $[n]$, und das Paar $(\sigma_{f},f)$
definiert daher eine Auslage von Perlenketten "uber $[n]$. Es ist
klar, da"s die Zuordnung $f \mapsto (\sigma_{f},f)$ einen Schnitt
$s:A^{[n]}\longrightarrow [n]!\times A^{[n]}$ definiert.

Ganz entsprechend kann man jedem Element $u \in s^{n}(P(A))$ eine
Auslage von Perlenketten "uber $[n]$ zuordnen, indem man zun"achst die
Shift--Perioden des Tr"agers von $u$ mittels der in ihnen enthaltenen
normalen Elemente nach absteigender Gr"o"se ordnet. Hat in dieser
absteigenden Folge die $i$--te Shift--Periode die L"ange $l_{i}$ und
hat $u$ auf ihr den Wert $u_{i}$, dann ordnet man ihr das
Teilintervall
\(
\{u_{1}l_{1}+ \dots u_{i-1}l_{i-1}+1,
                \dots, u_{1}l_{1}+ \dots+ u_{i}l_{i}\}
\)
von $[n]$ zu. Es hat die L"ange $u_{i}l_{i}$, und
\[
\{1,\dots,u_{1}l_{1}\}\cup \{u_{1}l_{1}+1,
                \dots,u_{1}l_{1}+u_{2}l_{2}\}
\cup\dots \cup
\{u_{1}l_{1}+ \dots u_{k-1}l_{k-1}+1,\dots, n\}
\] 
ist eine disjunkte Zerlegung des Intervalles $[n]$.  Auf jedem dieser
Teilintervalle betrachtet man wieder die naheliegende zyklische
Permutation und erh"alt so insgesamt eine Permutation $\sigma_{u}$ von
$[n]$.  Das erste Element 
$u_{1}l_{1}+ \dots u_{i-1}l_{i-1}+1$
des $i$--ten Teilintervalles
f"arbt man mit der Farbe $g(0)$ des normalen Elementes $g$ der
$i$--ten Shift--Periode, und seine Bilder unter den Iterierten von
$\sigma_{u}$ erhalten die Farbe des entsprechenden Iterierten von $g$
unter dem Shift.  Zusammen genommen liefert dies eine F"arbung $f_{u}$
des Intervalles $[n]$ und also eine Auslage $(\sigma_{u},f_{u})$ von
Perlenketten, deren Bild unter $p$ gleich $u$ ist. Offensichtlich
definiert die Zuordnung $u \mapsto (\sigma_{u},f_{u})$ einen Schnitt
$t:s^{n}(P(A))\longrightarrow [n]!\times A^{[n]}$.

Aufgrund der Eigenschaften der Lyndon--W"orter ist es klar, da"s die
Bilder der Schnitte $s$ und $t$ "ubereinstimmen und die Abbildungen 
$p \circ s$ und $pr_{1} \circ t$ 
deshalb zueinander inverse Bijektionen
zwischen $A^{[n]}$ und $s^{n}(P(A))$ definieren. Dies liefert im
wesentlichen die Konstruktion von {\sc de Bruin} und {\sc Klarner}.  
%
\begin{small}
\begin{thebibliography}{MR2}
%
\bibitem[BP]{BP}
{\sc Berstel~J., Perrin~D.} --- 
{\em Theory of Codes} --- Academic Press (1985).  
%
\bibitem[dBK]{dBK}
{\sc de~Bruijn N.G., Klarner~D.A.} --- 
{\em Multisets of aperiodic cycles},\\ 
SIAM J.~Alg.~Disc.~Meth., vol.~{\bf 3}(1982), 359--368.  
%
\bibitem[DS1]{DS1}
{\sc Dress~A.W.M., Siebeneicher C}h. --- 
{\em The Burnside Ring of the
Infinite Cyclic Group and its Relations to 
The Necklace Algebra,
\mbox{$\lambda$--Rings} and 
The Universal Ring of Witt Vectors}(1987);\\ 
to appear in: Advances in Mathematics.  
%
\bibitem[DS2]{DS2}
{\sc Dress A.W.M., Siebeneicher C}h. --- 
{\em On the Number of
Solutions of Certain Linear Diophantine Equations},\\ 
preprint Bielefeld (1988).  
%
\bibitem[G]{G}
{\sc Gauss C.F.} --- {\em Werke Band II} --- 
K\"onigliche Gesellschaft
der Wissen\-schaften, G\"ottingen (1863), 219--222.  
%
\bibitem[L]{L}
{\sc Lothaire M.} --- {\em Combinatorics on Words},\\ 
Encyclopedia of Mathematics and its Applications,\\ 
Addison--Wesley Publishing Company (1983).  
%
\bibitem[MR]{MR}
{\sc Metropolis N., Rota G.-C.} --- 
{\em The cyclotomic Identity},\\
Contemporary Mathematics, 
vol.~{\bf 34} Amer.~Math. Soc. (1984), 19--24.  
%
\end{thebibliography}
\end{small}
\begin{flushright}
\parbox{43em}{
Andreas~{\sc Dress} und Christian~{\sc Siebeneicher},\\ 
Universit\"at Bielefeld,\\ 
Fakult\"at f\"ur Mathematik,\\ 
Postfach 10\,01\,31,\\ 
D 33\,501 Bielefeld\\ 
electronic mail: dress@mathematik.uni-bielefeld.de\\
\hspace*{7em}sieben@mathematik.uni-bielefeld.de.}
\end{flushright}
\end{document}

