%************************************************************************
%              Andreas Dress und Christian Siebeneicher                 *
%                                                                       *
%                   Zur Abzaehlung periodischer Worte                   *
%                                                                       *
%************************************************************************
%
%
%***********  Man benoetigt zum Drucken den deutschen Style File  ******
%***********  darticle.sty      von Hubert Partl aus Wien         ******
%***********  Diese Files sind auf dem Listserver in Heidelberg   ******
%***********                    DHDURZ1                           ****** 
%***********                    Komando:                          ******
%***********   tell listserv at dhdurz1 get textools filelist     ******
%
                                %\documentstyle[12pt,mssymb,german]{article}
\documentclass[10pt]{article}
\usepackage{german}
\usepackage{amsmath}
%
%********************   Anpassungen an das  DIN A4  Format  ************
% 
\addtolength\topmargin{-27pt}
\addtolength\textheight{68pt}
\frenchspacing
\sloppy
%
%********************   Ein paar eigene Definitionen   ******************
%
\newcommand{\scirc}{\raisebox{1pt}{$\,\scriptstyle\circ\,$}}
\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}}
%
%***********************************************************************
%
\begin{document} 
%
\vspace*{2.4cm}
\begin{center}
{\bf                ZUR ABZ"AHLUNG PERIODISCHER WORTE            }\\[3mm]
%
{\scriptsize \sc VON}\\[3mm]
%
{\sc Andreas} DRESS
{\scriptsize \sc UND}
\normalsize
{\sc Christian} SIEBENEICHER% 
%\setcounter{footnote}{0}%
%\addtocounter{footnote}{-2}%
\footnote%
{Universit\"at Bielefeld, Fakult\"at f\"ur Mathematik, Postfach 10\,01\,31,
  D 33\,501 Bielefeld, \mbox{e--mail:
  dress@mathematik.uni-bielefeld.de sieben@mathematik.uni-bielefeld.de}}       
\end{center}

\footnotesize\noindent
{\sc Abstract.} --- We show that the basic bijection $\Psi$
of a diagram which has been introduced in
\cite{DS3} (see also \cite{DS2}) to unify the known combinatorial
proofs of the so called {\em cyclotomic identity}
(cf.~\cite{DS1,MR1,MR2,VW}) and which provides  
moreover a setting for bijections concerning primitive 
necklaces, defined and studied by 
{\sc Viennot} \cite{V}, 
{\sc de Bruijn} and {\sc Klarner} \cite{dBK}, and {\sc Gessel} \cite{DW},
may be viewed as a special instance of a
more general bijection defined for arbitrary
{\em cyclic sets}. Indeed, if this more general bijection is applied
to the  cyclic set $P(A)$ of 
periodic functions on the  integers with values in the set
$A$, one gets the bijection discussed in \cite{DS2,DS3}.

\normalsize

\medskip
\begin{center}
{\bf Eine Beobachtung "uber Bijektionen}
\end{center}

\noindent Da"s zwischen zwei Mengen mit offensichtlich gleicher Kardinalit"at
nicht immer nur {\em eine} wohlbestimmte kanonische Bijektion zu
existieren braucht, f"uhrt das wohlbekannte Beispiel eines affinen
Raumes {\bf A}  und des zugeh"orige Vektorraum $T(\mbox{\bf A})$ der
Translationen auf {\bf A} deutlich vor Augen.
Es gibt keine kanonische Bijektion zwischen  $T(\mbox{\bf A})$ und
{\bf A}. Zwar liefert nach Auswahl eines Basispunktes 
$a\in \mbox{\bf A}$ die Abbildung $x \mapsto a+x$ eine Bijektion von 
$T(\mbox{\bf A})$  auf {\bf A}, aber diese Abbildung ist nat"urlich
nicht kanonisch, sondern h"angt von der Auswahl von $a$ ab.
Oder, anders gesagt, sie ist nur dann kanonisch, wenn $a\in A$ ein in
irgendeiner Weise ausgezeichneter Punkt ist.
Zu einer unabh"angig von jeder solchen Auszeichnung stets
 kanonischen Bijektion kommt man bekanntlich jedoch, sozusagen
auf einer h"oheren Ebene,
zwischen den Mengen ${\bf A}\times T(\mbox{\bf A})$ und 
$ \mbox{\bf A}\times \mbox{\bf A}$
unter Benutzung der
Operation von  $T(\mbox{\bf A})$ auf {\bf A}: durch die Bijektion
$(a,x) \mapsto (a,a+x)$ werden die  durch Auswahl eines
Nullpunktes definierten unkanonischen Bijektionen
$T(\mbox{\bf A}) \rightarrow \mbox{\bf A}$ in gewisser Weise alle
in dem folgenden kommutativen Diagramm kanonisch zusammengefa"st:\\
\begin{center}
\begin{minipage}[t]{4.5cm}
\begin{small}
\begin{center}
\setlength{\unitlength}{.4pt}
\begin{picture}(210,100)(0,0)
% 
%-----------------------------------------------------------
%********** OBEN ******************************* 
%
\put(45,95){\makebox(0,0)[r]{$\mbox{\bf A} \times T(\mbox{\bf A})$}}
%
\put(165,95){\makebox(0,0)[l]{$\mbox{\bf A} \times {\bf A}$}}
% 
% ********** UNTEN ******************************* 
%
\put(95,0){\makebox(0,0)[c]{$\mbox{\bf A}$}}
% 
% 
% ************* Der horizontale Pfeil oben   ********************* 
%
\put(55,95){\vector(1,0){100}}
%
%---------------------------------------------------------------
%************* Die Pfeile von oben nach unten ********************* 
%
\put(15,75){\vector(1,-1){60}}
%
\put(175,75){\vector(-1,-1){60}}
% 
%******************** Beschriften ************************
%
%
\put(25,45){\makebox(0,0)[r]{$pr_{1}$}}
%
\put(165,45){\makebox(0,0)[l]{$pr_{1}$}}
%
\end{picture}
\end{center}
\end{small}
\end{minipage}
\hspace{1cm}
\begin{minipage}[t]{6cm}
\scriptsize
\vspace{-1.4cm}
Wir bezeichnen hier und im folgenden die kanonischen Projektionen von dem
Produkt zweier 
Mengen auf den ersten bzw. den zweiten Faktor (und auch deren
Einschr"ankung auf irgendeine Teilmenge des Produktes) mit $pr_{1}$
bzw. mit $pr_{2}$.
\end{minipage}
\end{center}
\normalsize
Allgemeiner hat man f"ur jede Gruppe $G$ und jeden Raum $X$, auf dem $G$
transitiv und treu operiert (also, mit anderen Worten, f"ur jeden 
{\em prinzipal homogenen Raum} $X$ zur Gruppe $G$)
ein analoges kommutatives Diagramm, in welchem
die durch die Auswahl eines Elementes $x$ aus $X$ definierten nicht
kanonischen Bijektionen
$g \mapsto x\cdot g$ von $G$ auf $X$ kanonisch zusammengefa"st werden:

\medskip

\begin{small}
\begin{center}
\setlength{\unitlength}{.4pt}
\begin{picture}(400,140)(0,0)
% 
%-----------------------------------------------------------
%********** OBEN ******************************* 
%
\put(120,135){\makebox(0,0)[r]{$(x,g)$}}
%
\put(125,95){\makebox(0,0)[r]{$X \times G$}}
%
\put(255,135){\makebox(0,0)[l]{$(x,x\cdot g)$}}
%
\put(260,95){\makebox(0,0)[l]{$X \times X$}}
% 
% ********** UNTEN ******************************* 
%
\put(195,0){\makebox(0,0)[c]{$X$}}
% 
% 
% ************* Die horizontalen Pfeile oben   ****************
%
\put(140,135){\vector(1,0){95}}
%
\put(135,135){\makebox(0,0)[r]{$\mapstochar$}}
%
\put(135,95){\vector(1,0){120}}
%
%---------------------------------------------------------------
%************* Pfeile von Unten zur Mitte ********************* 
%
\put(115,75){\vector(1,-1){60}}
%
\put(275,75){\vector(-1,-1){60}}
% 
%******************** Beschriften ************************
%
%
\put(125,45){\makebox(0,0)[r]{$pr_{1}$}}
%
\put(265,45){\makebox(0,0)[l]{$pr_{1}$}}
%
\end{picture}
\end{center}
\end{small}
\medskip
\noindent
Ist insbesondere $E$ eine Menge und ist $E!$ die Gruppe der
Permutationen 
von $E$, dann liefert die Operation von $E!$ auf der Menge
$\mbox{\bf B}(E,F)$ der Bijektionen von $E$ auf eine mit $E$
gleichm"achtige Menge $F$ hierf"ur ein
h"aufig betrachtetes Beispiel. 

Dieses Beispiel kann in der folgenden Weise verallgemeinert werden:
Sind $E_{1},E_{2}, \dots, E_{r}$ und $F$ gleichm"achtige, endliche
Mengen, dann ist klar, da"s  auch die Mengen
$\prod_{i}\mbox{\bf B}(E_{i},E_{i+1})$ 
und
$\prod_{i}\mbox{\bf B}(E_{i},F)$ 
gleichm"achtig sind. Eine kanonische Bijektion ist auch hier nicht
m"oglich, jedoch hat man wiederum kanonische Bijektionen auf h"oherem
Niveau,  zwischen 
$ \prod_{i}\mbox{\bf B}(E_{i},F) \times
\prod_{i}\mbox{\bf B}(E_{i},E_{i+1}) $ und
$\prod_{i}\mbox{\bf B}(E_{i},F)\times 
\prod_{i}\mbox{\bf B}(E_{i},F)$
("uber $\prod_{i}\mbox{\bf B}(E_{i},F)$),
die durch
\[
\begin{array}{c}
((\varphi_{i});(\sigma_{i}))_{i \bmod r} \mapsto 
((\varphi_{i});(\varphi_{i+1}\scirc \sigma_{i}))_{i \bmod r}\\[6pt]
%
((\varphi_{i});(\varphi_{i+1}^{-1}\scirc \tau_{i}))_{i \bmod r}
\leftarrow\!\mapstochar ((\varphi_{i});(\tau_{i}))_{i \bmod r}
\end{array}
\]
definiert sind

\begin{footnotesize}
\begin{center}
\setlength{\unitlength}{2pt}
\begin{picture}(200,70)(0,15)   %(x_max,y_max)(0,0) = Ecke links-unten)
%
%-----------------------------------------------------------------
% *************************** OBEN *******************************
%
\put(47,79){\makebox{$E_{1}$}}  
%
\put(147,79){\makebox{$E_{1}$}}         
%
% ************************** MITTE *******************************
%
\put(27,58.5){\makebox{$E_{2}$}}
\put(48,58.5){\makebox{$F$}}            
\put(68,58.5){\makebox{$E_{4}$}}                % links
%
\put(127,58.5){\makebox{$E_{2}$}}       
\put(148,58.5){\makebox{$F$}}   
\put(168,58.5){\makebox{$E_{4}$}}       % rechts
%
% *************************** UNTEN *******************************
%
\put(47,37){\makebox{$E_{3}$}}  
\put(147,37){\makebox{$E_{3}$}}         
%
% *********************** Pfeile Links *********************
%
\put(55,45){\vector(1,1){10}}
%
\put(35,55){\vector(1,-1){10}}
%
\put(45,75){\vector(-1,-1){10}}
%
\put(65,65){\vector(-1,1){10}}
%
\put(50,75){\vector(0,-1){10}}
%
\put(35,60){\vector(1,0){10}}
%
\put(65,60){\vector(-1,0){10}}
%
\put(50,45){\vector(0,1){10}}
%
% ***************** Pfeile Rechts *********************
%
\put(135,61){\vector(1,0){10}}
%
\put(135,59){\vector(1,0){10}}
%
\put(149,75){\vector(0,-1){10}}
%
\put(151,75){\vector(0,-1){10}}
%
\put(165,59){\vector(-1,0){10}}
%
\put(165,61){\vector(-1,0){10}}
%
\put(149,45){\vector(0,1){10}}
%
\put(151,45){\vector(0,1){10}}
%
%**********************  Beschriften der Pfeile *********************
% 
%********* links
%
\put(38,71){\makebox(0,0)[br]{\small$\sigma_{1}$}}
%
\put(38,50){\makebox(0,0)[tr]{\small$\sigma_{2}$}}
%
\put(63,50){\makebox(0,0)[tl]{\small$\sigma_{3}$}}
%
\put(63,71){\makebox(0,0)[bl]{\small$\sigma_{4}$}}
%
\put(55,70){\makebox(0,0)[c]{\small$\varphi_{1}$}}
%
\put(41,64){\makebox(0,0)[c]{\small$\varphi_{2}$}}
%
\put(46,50){\makebox(0,0)[c]{\small$\varphi_{3}$}}
%
\put(60,56){\makebox(0,0)[c]{\small$\varphi_{4}$}}
%
%********* rechts
%
\put(155,70){\makebox(0,0)[c]{\small$\varphi_{1}$}}
%
\put(145,70){\makebox(0,0)[c]{\small$\tau_{1}$}}
%
\put(140,64){\makebox(0,0)[c]{\small$\varphi_{2}$}}
%
\put(140,56){\makebox(0,0)[c]{\small$\tau_{2}$}}
%
\put(145,50){\makebox(0,0)[c]{\small$\varphi_{3}$}}
%
\put(155,50){\makebox(0,0)[c]{\small$\tau_{3}$}}
%
\put(160,56){\makebox(0,0)[c]{\small$\varphi_{4}$}}
%
\put(160,64){\makebox(0,0)[c]{\small$\tau_{4}$}}
%
\end{picture}
\end{center}
\end{footnotesize}

\noindent und die das folgende kommutative Diagramm etablieren:
\medskip
\begin{footnotesize}
\begin{center}
\setlength{\unitlength}{.4pt}
\begin{picture}(400,200)(0,0)
% 
%-----------------------------------------------------------
%********** OBEN ******************************* 
%
\put(145,175){\makebox(0,0)[r]{
$\displaystyle \prod_{i}\mbox{\bf B}(E_{i},F)
        \times \prod_{i}\mbox{\bf B}(E_{i},E_{i+1}) $}}
%
\put(255,175){\makebox(0,0)[l]{
$\displaystyle\prod_{i}\mbox{\bf B}(E_{i},F) 
\times \prod_{i}\mbox{\bf B}(E_{i},F)$}}
% 
% ********** UNTEN ******************************* 
%
\put(195,10){\makebox(0,0)[c]{$\prod_{i}\mbox{\bf B}(E_{i},F)$}}
% 
% 
% ************* Die horizontalen Pfeile oben   ********************* 
%
\put(155,187){\vector(1,0){90}}
%
\put(245,178){\vector(-1,0){90}}
%
%---------------------------------------------------------------
%************* Pfeile von Oben nach Unten ********************* 
%
\put(55,155){\vector(1,-1){120}}
%
\put(335,155){\vector(-1,-1){120}}
% 
%******************** Beschriften ************************
%
%
\put(75,95){\makebox(0,0)[r]{$pr_{1}$}}
%
\put(315,95){\makebox(0,0)[l]{$pr_{1}$}}
%
\end{picture}
\end{center}
\end{footnotesize}


Hat man eine Familie {\em ausgezeichneter} Bijektionen 
$\varphi_{i}:E_{i} \rightarrow F$, sind beispielsweise s"amtliche Mengen
linear geordnet, so hat man nat"urlich auch  eine 
{\em kanonische} Bijektion 
$\psi:\prod_{i}\mbox{\bf B}(E_{i},E_{i+1}) \rightarrow
\prod_{i}\mbox{\bf B}(E_{i},F)$. Wir werden  sp"ater hierauf
zur"uckkommen.

\medskip
\begin{center}
{\bf Eine Anwendung auf zyklische Mengen}
\end{center}

\noindent
Die kanonische Bijektion
\[
\prod_{i}\mbox{\bf B}(E_{i},F)
\times  \prod_{i}\mbox{\bf B}(E_{i},E_{i+1}) 
\rightarrow
\prod_{i}\mbox{\bf B}(E_{i},F) 
\times \prod_{i}\mbox{\bf B}(E_{i},F)
\]
kann in der Sprache der {\em zyklischen Mengen}
auf folgende einfache, aber "uberraschend folgenreiche Weise
interpretiert werden:

Sei $X$ eine Menge, sei $\alpha$  eine auf $X$ wirkenden
Permutation\footnote{Wir wollen 
dann $X$  eine {\em zyklische Menge} mit  {\em
Shift--Operator}   $\alpha$ nennen.} und sei
$S(X):=\{ u:X\rightarrow \No \mid \sum_{x \in X}u(x)<\infty \}$
das in \cite{DS1} betrachtete frei von $X$ erzeugte kommutative
Monoid, kurz die {\em symmetrische Algebra}  von $X$, die aus allen
auf $X$ definierten Funktionen mit Werten in 
$\No:=\{0,1,2,\dots\}$ und endlichem Tr"ager 
$supp(u):= \{x\in X \mid u(x) \ne 0\}$ besteht. 
Der Shift--Operator von $X$ induziert durch
$\alpha\cdot u:= u\scirc \alpha^{-1}$  einen Shift--Operator auf
$S(X)$, der auch $S(X)$ zu einer zyklischen Menge macht. F"ur 
$u\in S(X)$ sei\footnote{F"ur jede nat"urliche Zahl $n$ setzen wir
$[n]:=\{1,\dots,n\}.$}
\mbox{$[u]:=\{(x,i)\mid x\in X,\;i \in [u(x)] \}\subset X\times \No$}.
Die Menge $[u]$ ist genau dann invariant unter dem naheliegenden
Shift--Operator auf $X\times \No$,
wenn $u$ eine shift--invariante
Funktion auf $X$ ist. 
Die Menge der shift--invarianten Elemente von
$S(X)$ sei mit $s(X)$ bezeichnet.


F"ur jede  endliche Menge $E$ und jede Abbildung
$\pi: E \rightarrow X$ ist die Funktion
${}^{\#}\pi:X \longrightarrow \No,$
die definiert ist durch $x \mapsto \#\pi^{-1}(x)$, ein Element von $S(X)$.
Dieses Element ist genau dann invariant unter dem Shift--Operator (und liegt dann
in $s(X)$), wenn 
"uber jeder Bahn von $X$ s"amtliche
Fasern von $\pi$ gleichviel Elemente haben.
Bezeichnet man die Menge derjenigen Abbildungen $\pi$ von $E$
nach $X$, f"ur welche ${}^{\#}\pi$ shift--invariant ist,  mit
$X^{(E)}$, dann liefert die Zuordnung 
$\pi \mapsto {}^{\#}\pi$ eine kanonische Abbildung
${}^{\#}:X^{(E)} \rightarrow s(X)$.

Seien nun f"ur festes $\pi:E\rightarrow X$ aus $X^{(E)}$ mit
\[
T_{X,\pi}(E):= 
\{ \sigma \in E! \mid \pi \scirc \sigma = \alpha \scirc \pi \}
\]
die Menge der mit $\pi$ vertr"aglichen Shift--Operatoren 
$\sigma:E\stackrel{\sim}{\rightarrow}E$ und mit
\[
s_{X,\pi}(E):=
\{ \Phi \in \mbox{\bf B}(E,[{}^{\#}\pi]) \mid pr_{1}\scirc \Phi =\pi  \}.
\]
die Menge der Bijektionen zwischen $E$ und $[{}^{\#}\pi]$ "uber $X$
bezeichnet. 

Besteht  $\pi(E)=supp({}^{\#}\pi)$ aus einer einzigen Bahn des
Shift--Operators  $\alpha$,
w"ahlt man ein beliebiges Element
$x \in \pi(E)$, bezeichnet man die Fasern von $\pi$ "uber der Bahn
\mbox{$x,\alpha\cdot x,\dots, \alpha^{r-1}\cdot x$} von $x$ mit
$E_{1},E_{2},\dots,E_{r}$ und setzt man
$F= [{}^{\#}\pi(x)]$, so definiert
\[
\begin{array}{c}
\displaystyle
T_{X,\pi}(E)\stackrel{\sim}{\rightarrow}
        \prod_{i=1}^{r}\mbox{\bf B}(E_{i},E_{i+1})\\[12pt]
\displaystyle
\sigma \mapsto 
        (\sigma|_{E_{1}},\sigma|_{E_{2}},\dots,\sigma|_{E_{r}})
\end{array}
\]
(was wegen 
$\sigma(E_{i})= \sigma(\pi^{-1}(\alpha^{i-1}\cdot x))
= \pi^{-1}(\alpha^{i}\cdot x) = E_{i+1}$ wohldefiniert ist!) und
\[
\begin{array}{c}
\displaystyle
s_{X,\pi}(E)\stackrel{\sim}{\rightarrow}
        \prod_{i=1}^{r}\mbox{\bf B}(E_{i},F)\\[12pt]
\displaystyle
\Phi \mapsto 
(pr_{2}\scirc \Phi|_{E_{1}},
        pr_{2}\scirc \Phi|_{E_{2}},
                \dots,pr_{2}\scirc \Phi|_{E_{r}})
\end{array}
\]
kanonische Bijektionen, die folglich eine kanonische Bijektion
\begin{small}
\begin{center}
\setlength{\unitlength}{.4pt}
\begin{picture}(400,110)(0,0)
% 
%-----------------------------------------------------------
%********** OBEN ******************************* 
%
\put(125,95){\makebox(0,0)[r]{$s_{X,\pi}(E) \times T_{X,\pi}(E)$}}
%
\put(260,95){\makebox(0,0)[l]{$s_{X,\pi}(E)\times s_{X,\pi}(E)$}}
% 
% ********** UNTEN ******************************* 
%
\put(195,0){\makebox(0,0)[c]{$s_{X,\pi}(E)$}}
% 
% 
% ************* Die horizontalen Pfeile oben   ****************
%
\put(135,95){\vector(1,0){120}}
%
%---------------------------------------------------------------
%************* Pfeile von Unten zur Mitte ********************* 
%
\put(115,75){\vector(1,-1){60}}
%
\put(275,75){\vector(-1,-1){60}}
% 
%******************** Beschriften ************************
%
%
\put(125,45){\makebox(0,0)[r]{$pr_{1}$}}
%
\put(265,45){\makebox(0,0)[l]{$pr_{1}$}}
%
\end{picture}
\end{center}
\end{small}\noindent
"uber den jeweiligen Projektionen auf den ersten Faktor induzieren. 

Diese Bijektion l"a"st sich sogar  f"ur ganz beliebiges 
$\pi$ auch ohne Bezug auf die obige einf"uhrende Diskussion direkt
durch Betrachten der umkehrbar eindeutigen Korrespondenz
\begin{eqnarray*}
(\Phi,\sigma)
\leftrightarrow
(\Phi,\Phi^{'}) & \Longleftrightarrow   &
                                        \Phi^{'}|_{\pi^{-1}(x)}=
        \Phi|_{\pi^{-1}(\alpha x)}\scirc \sigma|_{\pi^{-1}(x)}\\[6pt]
                &                       &
                                        \mbox{ f"ur alle $x \in X$}
\end{eqnarray*}
etablieren.

Durch Einachr"ankung dieser Korrespondenz auf die Fasern (jeweils
bez"uglich der Abbildung $pr_{1}$) "uber einem beliebigen Element
$\Phi \in s_{X,\pi}(E)$ erh"alt man folglich auch (von der Auswahl von
$\Phi$ abh"angige) Bijektionen 
$\psi_{\Phi}:T_{X,\pi}(E)\rightarrow s_{X,\pi}(E)$. F"ur den Fall,
da"s $E$ linear geordnet ist (insbesondere also im Falle $E=[n]$),
gibt es in $s_{X,\pi}$ genau ein Element
$\Phi_{\pi}:E \stackrel{\sim}{\rightarrow} [{}^{\#}\pi]$, 
dessen Einschr"ankung auf jede
der Fasern von $\pi$ monoton w"achst. In dieser
Situation hat man deshalb sogar eine kanonische Bijektion
$\psi_{\pi}:T_{X,\pi}(E)\rightarrow s_{X,\pi}(E)$. 

Definiert man schlie"slich f"ur jede endliche Menge $E$ die Mengen
\[
T_{X}(E):=
\{(\sigma,\pi)\mid \sigma \in E!,\; \pi\in X^{E}, 
\pi\scirc \sigma= \alpha\scirc \pi \} \subset E!\times X^{(E)}
\]
bzw.
\[
s_{X}(E):= 
\{(u,\Phi)\mid u \in s(X), \Phi \in \mbox{\bf B}(E,[u])\},
\]
dann sind die Mengen
$T_{X,\pi}(E)$ bzw. $s_{X,\pi}(E)$ gerade die Fasern der
Projektions--Abbildung $pr_{2}:T_{X}(E)\rightarrow X^{(E)}$ bzw. der
Abbildung \mbox{$t:s_{X}(E)\rightarrow X^{(E)}$},
die definiert ist durch  $(u,\Phi) \mapsto pr_{1}\scirc \Phi$
und deren Komposition mit der Abbildung
${}^{\#}:X^{(E)}\rightarrow s(X)$ gleich der Projektion
$pr_{1}:s_{X}(E)\rightarrow s(X)$ ist.
Die obige Korrespondenz liefert also eine kanonische und "uber der
jeweiligen Projektion auf den ersten Faktor fasertreue
Bijektion der Faserprodukte \\
%
\begin{small}
\begin{center}
\setlength{\unitlength}{.4pt}
\begin{picture}(400,165)(0,-70)
% 
%-----------------------------------------------------------
%********** OBEN ******************************* 
%
\put(125,95){\makebox(0,0)[r]{$s_{X}(E)\times T_{X}(E) $}}
%
\put(55,70){\makebox(0,0)[r]{$\scriptstyle X^{(E)}$}}
%
\put(260,95){\makebox(0,0)[l]{$s_{X}(E)\times s_{X}(E)$}}
%
\put(330,70){\makebox(0,0)[l]{$\scriptstyle X^{(E)}$}}
% 
% ********** UNTEN ******************************* 
%
\put(195,-65){\makebox(0,0)[c]{$s_{X}(E)$}}
% 
% 
% ************* Die horizontalen Pfeile oben   ****************
%
\put(135,95){\vector(1,0){120}}
%
%---------------------------------------------------------------
%************* Pfeile von Unten zur Mitte ********************* 
%
\put(60,50){\vector(1,-1){90}}
%
\put(325,50){\vector(-1,-1){90}}
% 
%******************** Beschriften ************************
%
%
\put(95,5){\makebox(0,0)[r]{$pr_{1}$}}
%
\put(295,5){\makebox(0,0)[l]{$pr_{1}$}}
%
\end{picture}
\end{center}
\end{small}\noindent
Sie induziert durch Einschr"ankung auf das Bild eines (beliebigen)
Schnittes $\rho:X^{(E)} \rightarrow s_{X}(E)$  f"ur die Abbildung
$t:s_{X}(E) \rightarrow X^{(E)}$ eine (von $\rho$ abh"angige) Bijektion
$\psi_{\rho}:T_{X}(E) \rightarrow s_{X}(E)$. Falls die Menge $E$
linear geordnet 
ist, existiert wiederum ein kanonischer Schnitt
\[
\rho_{X}^{E}:X^{(E)}\rightarrow s_{X}(E)\qquad 
\pi \mapsto ({}^{\#}\pi,\Phi_{\pi})
\]
so da"s in diesem Falle auch eine kanonische Bijektion
\[
\psi_{X}^{E}:T_{X}(E)\stackrel{\sim}{\rightarrow} s_{X}(E)
\]
existiert.

\smallskip\noindent
{\sc Bemerkung}\\
F"ur den Fall, da"s die Menge $E$ linear geordnet
ist, liefert die Komposition des Schnittes 
$\rho_{X}^{E}:X^{(E)}\rightarrow s_{X}(E)$ mit dem Inversen der
kanonischen Bijektion 
$\psi_{X}^{E}:T_{X}(E) \rightarrow s_{X}(E)$  einen kanonischen
Schnitt f"ur die Abbildung 
$pr_{2}:T_{X}(E) \rightarrow X^{(E)}$. In dem
Bild $(\sigma_{\pi},\pi)$ von $\pi$ unter diesem Schnitt, ist  
$\sigma_{\pi}$ diejenige der Gleichung 
$\pi \scirc \sigma = \alpha\scirc \pi$ gen"ugende
Permutation von $E$, die  auf den Fasern von $\pi$  monoton
w"achst.



\medskip
\begin{center}
{\bf Der Spezialfall der Menge der periodischen Funktionen}
\end{center}

\noindent
Ist speziell $X=P(A)$, gleich  der zyklischen Menge
der auf   $\Z$ definierten {\em periodischen Funktionen}%
\footnote{Der Shift--Operator  
$\alpha:P(A) \rightarrow P(A)$ ist definiert durch
$(\alpha \cdot g)(i):= g(i+1)$ f"ur alle $g \in P(A)$}
 mit Werten in der
Menge $A$ (cf. \cite{DS3}), dann hat man
zus"atzlich zu den vielen von der Auswahl eines Schnittes 
$\rho:X^{(E)}\rightarrow s_{X}(E)$
abh"angigen
(unkanonischen) Bijektionen
$T_{P(A)}(E) \rightarrow s_{P(A)}(E)$ noch eine kanonische Bijektion 
$\omega:E!\times A^{E} \longrightarrow T_{P(A)}(E)$. Sie ist wie folgt
definiert:
f"ur  jedes Element
$(\sigma,f)\in E!\times A^{E}$  und jedes $\epsilon \in E$ wird durch 
die Zuordnung $i \mapsto f(\sigma^{i}(\epsilon))$
eine periodische Punktion 
$f_{\sigma}^{\epsilon}:\Z\rightarrow A$ definiert. Die Zuordnung 
$\epsilon \mapsto f_{\sigma}^{\epsilon}$ ist
mit $\sigma$ und dem Shift--Operator $\alpha$ vertr"aglich (d.h., es
ist 
$f_{\sigma}^{\epsilon}\scirc \sigma = 
\alpha \scirc f_{\sigma}^{\epsilon}$),
und sie definiert daher eine "aquivariante  Abbildung
$\pi_{\sigma,f}:(E,\sigma) \longrightarrow (P(A),\alpha)$. Durch
die Zuordnung
\[
(\sigma,f) \mapsto (\sigma,\pi_{\sigma,f})
\]
wird daher eine nat"urliche Abbildung
\[
\omega:E!\times A^{E} \longrightarrow T_{P(A)}(E)
\]
definiert, die leicht als Bijektion zu erkennen ist: ihre
 Umkehrabbildung ist durch
\[
(\sigma, \pi) \mapsto (\sigma, ev \scirc \pi)
\]
gegeben,  wobei $ev:P(A)\rightarrow A$ durch die Zuordnung
$g \mapsto g(0)$ definiert ist.
Abstrakt gesehen resultieren diese Bijektionen aus der Tatsache, da"s
der Funktor 
$A\mapsto P(A)$ von der Kategorie der Mengen in die Kategorie der
zyklischen Mengen links--adjungiert zum Vergi"sfunktor   ist, wobei die
Evaluationsabbildung $ev$  eine der beiden Adjunktionsabbildungen ist und die
Zuordnung $f \mapsto \pi_{\sigma,f}$ die andere
Adjunktionsabbildung definiert.

Auf der Menge $E!\times A^{E}$ hat man eine Reihe weiterer kanonisch
definierter Abbildungen. 
\begin{itemize}
\item
Die Projektion $\quad pr_{2}:E!\times A^{E} \rightarrow A^{E}$
\item
Die Abbildung 
$\quad r:E!\times A^{E} \rightarrow P(A)^{(E)} \qquad
(\sigma,f)\mapsto \pi_{\sigma,f}$.\\
F"ur sie gilt $r= pr_{2}\scirc \omega$.
\item
Die Abbildung 
$\quad q:E!\times A^{E} \rightarrow s(P(A)) \qquad
(\sigma,f)\mapsto u_{\sigma,f}$,\\ [6pt]
wobei (cf.~\cite{DS2,DS3}) 
$
\quad 
u_{\sigma,f}(g):=\#\{\epsilon \in E \mid f_{\sigma}^{\epsilon}=g\}
        ={}^{\#}\pi_{\sigma,f}(g)$\\[6pt]
ist. F"ur diese Abbildung gilt daher $q={}^{\#}\scirc r$.
\end{itemize}
Dar"uber hinaus induziert die Komposition mit der Evaluation
\mbox{$ev:P(A)\rightarrow A$}  eine kanonische Abbildung
$ev^{*}:P(A)^{(E)}\rightarrow A^{E}$.
F"ur die Komposition von $ev^{*}$ mit der
Abbildung $t:s_{P(A)}(E)\rightarrow P(A)^{(E)}$ gilt:
\[
ev^{*}\scirc t\,(u,\Phi)=ev^{*}(pr_{1}\scirc \Phi)
        =ev\scirc pr_{1}\scirc \Phi.
\]
Die Komposition $ev^{*}\scirc t$ ist daher gleich der in
\cite{DS2,DS3} definierten Abbildung\footnote{Man beachte, da"s dort
die Menge $s_{P(A)}(E)$ mit $S^{A}(E)$ bezeichnet wurde.}
$p:s_{P(A)}(E)\rightarrow A^{E}$. Ferner sieht man
unmittelbar, da"s die zu dem
Element $(\sigma,f)\in E!\times A^{E}$ geh"orige Abbildung
$ev^{*}\scirc r (\sigma,f)=ev^{*}(\pi_{\sigma,f}):E\rightarrow A$ in
folgender Weise wirkt:
$\quad \epsilon \mapsto f_{\sigma}^{\epsilon}(0)=f(\epsilon),\quad$
und dies bedeutet, da"s $ev^{*}\scirc r=pr_{2}$ ist.

Schlie"slich hat man noch eine nat"urliche Abbildung (cf. \cite{DS3}) 
\[
\delta:s(P(A))\rightarrow S(A) \qquad
\delta(u)(a)=\sum_{g(0)=a}u(g),
\]
und eine analog zur Abbildung
${}^{\#}:P(A)^{(E)}\rightarrow s(P(A))$ definierte Abbildung
${}^{\#}:A^{E}\rightarrow S(A)$.
Es  ist klar, da"s f"ur jedes
Element $\pi \in P(A)^{(E)}$ gilt:
$\delta({}^{\#}\pi)={}^{\#}(ev \scirc \pi)$. Dies bedeutet aber, da"s
die Kompositionen 
$\delta \scirc pr_{1}:P(A)^{(E)}\rightarrow S(A)$ und 
${}^{\#}\scirc p:P(A)^{(E)}\rightarrow S(A)$
"ubereinstimmen. 

Wir fassen nun alle diese Daten in dem folgenden kommutativen
Diagramm zusammen. In ihm sind, 
bis auf die von der Auswahl eines $t$--Schnittes 
$\rho:X^{(E)}\rightarrow s_{X}(E)$
abh"angende Bijektion 
$\psi_{\rho}:T_{P(A)}(E)\rightarrow s_{P(A)}(E)$,
s"amtliche Abbildungen kanonisch:\\
\begin{footnotesize}
\begin{center}
\setlength{\unitlength}{.6pt}
\begin{picture}(450,260)(5,-75)
% 
%-----------------------------------------------------------
%********** OBEN ******************************* 
%
\put(230,180){\makebox(0,0)[c]{$E!\times A^{E} $}}
% 
% ********** MITTE ******************************* 
%
\put(0,95){\makebox(0,0)[r]{$A^{E} $}}
%
\put(135,95){\makebox(0,0)[r]{$P(A)^{(E)}$}}
%
\put(230,95){\makebox(0,0)[c]{$T_{P(A)}(E)$}}
%
\put(320,95){\makebox(0,0)[l]{$P(A)^{(E)}$}}
%
\put(445,95){\makebox(0,0)[l]{$s(P(A))$}}
% 
% ********** UNTEN ******************************* 
%
\put(230,10){\makebox(0,0)[c]{$s_{P(A)}(E)$}}
% 
%*************** GANZ  UNTEN ***************************
%
\put(225,-60){\makebox(0,0)[c]{$S(A)$}}
% 
 
% ************* Pfeile von Oben zur Mitte ********************* 
%
\thicklines\put(168,163){\line(-3,-1){168}}\thinlines
%
\put(168,163){\vector(-3,-1){168}}
%
\put(203,163){\vector(-3,-2){80}}
%
\put(230,163){\vector(0,-1){56}}
%
\put(250,163){\vector(3,-2){84}}
%
\put(275,163){\vector(3,-1){168}}
%
\thicklines\put(275,163){\line(3,-1){168}}\thinlines
%
%---------------------------------------------------------------
%************* Der Pfeil von der Mitte nach Unten ******** 
%
\put(230,82){\vector(0,-1){56}}
% 
%************* Pfeile von der Mitte nach ganz Unten ******** 
%
\put(-5,82){\vector(3,-2){200}}
%
\put(450,82){\vector(-3,-2){200}}
%
%---------------------------------------------------------------
%************* Horizontale Pfeile in der Mitte ***************
%
\put(65,95){\vector(-1,0){50}}
%
\put(185,95){\vector(-1,0){45}}
%
\put(275,95){\vector(1,0){45}}
%
\put(395,95){\vector(1,0){45}}
%
%-------------------------------------------------------------
%************* Pfeile von Unten zur Mitte ********************* 
%
\thicklines\put(175,26){\line(-3,1){168}}\thinlines
%
\put(175,26){\vector(-3,1){168}}
%
\put(198,26){\vector(-3,2){84}}
%
\put(250,26){\vector(3,2){84}}
%
\put(268,26){\vector(3,1){168}}
%
\thicklines\put(268,26){\line(3,1){168}}\thinlines
% 
%******************** Beschriften ************************
%
\put(65,135){\makebox(0,)[r]{$pr_{2}$}}
%
\put(150,135){\makebox(0,)[r]{$r$}}
%
\put(310,135){\makebox(0,0)[r]{$r$}}
%
\put(380,135){\makebox(0,0)[l]{$q$}}
%
\put(235,135){\makebox(0,0)[l]{$\omega$}}
%
\put(60,105){\makebox(0,0)[r]{$ev^{*}$}}
%
\put(175,105){\makebox(0,0)[r]{$pr_{2}$}}
%
\put(305,105){\makebox(0,0)[r]{$pr_{2}$}}
%
\put(420,105){\makebox(0,0)[r]{${}^{\#}$}}
%
\put(70,51){\makebox(0,0)[r]{$p$}}
%
\put(150,51){\makebox(0,0)[r]{$t$}}
%
\put(310,51){\makebox(0,0)[r]{$t$}}
%
\put(372,51){\makebox(0,0)[l]{$pr_{1}$}}
%
\put(235,51){\makebox(0,0)[l]{$\psi_{\rho}$}}
%
\put(80,10){\makebox(0,0)[r]{${}^{\#}$}}
%
\put(367,10){\makebox(0,0)[l]{$\delta$}}
%
\end{picture}
\end{center}
\end{footnotesize}
Ist  $E=[n]$, dann hat man, wie wir gesehen haben,  einen
kanonischen $t$--Schnitt
$\rho_{A}^{n}:= \rho_{P(A)}^{[n]}:P(A)^{[n]} 
                \rightarrow s_{P(A)}([n])$ 
und folglich auch eine kanonische
Bijektion $\psi_{A}^{n}:=\psi_{P(A)}^{[n]}:T_{P(A)}(E)
                        \rightarrow s_{P(A)}(E)$.
Setzt man nun
\[
s^{n}(P(A)):= \{u\in s(P(A)) \mid |u|:=\sum_{g\in P(A)}u(g)=n\},
\]
und entsprechend 
$S^{n}(A):= \{v\in S(A) \mid |v|:=\sum_{a\in A}v(a)=n\}$,
dann geht unser Diagramm in das folgende Diagramm "uber, in welchem nunmehr
s"amtliche Pfeile kanonisch und surjektiv und die
senkrechten Pfeile Bijektionen sind: 

\begin{footnotesize}
\begin{center}
\setlength{\unitlength}{.6pt}
\begin{picture}(450,260)(5,-75)
% 
%-----------------------------------------------------------
%********** OBEN ******************************* 
%
\put(230,180){\makebox(0,0)[c]{$[n]!\times A^{n} $}}
% 
% ********** MITTE ******************************* 
%
\put(0,95){\makebox(0,0)[r]{$A^{n} $}}
%
\put(135,95){\makebox(0,0)[r]{$P(A)^{([n])}$}}
%
\put(230,95){\makebox(0,0)[c]{$T_{P(A)}([n])$}}
%
\put(320,95){\makebox(0,0)[l]{$P(A)^{([n])}$}}
%
\put(445,95){\makebox(0,0)[l]{$s^{n}(P(A))$}}
% 
% ********** UNTEN ******************************* 
%
\put(230,10){\makebox(0,0)[c]{$s_{P(A)}([n])$}}
% 
%*************** GANZ  UNTEN ***************************
%
\put(225,-60){\makebox(0,0)[c]{$S(A)$}}
% 
 
% ************* Pfeile von Oben zur Mitte ********************* 
%
\thicklines\put(168,163){\line(-3,-1){168}}\thinlines
%
\put(168,163){\vector(-3,-1){168}}
%
\put(203,163){\vector(-3,-2){80}}
%
\put(230,163){\vector(0,-1){56}}
%
\put(250,163){\vector(3,-2){84}}
%
\put(275,163){\vector(3,-1){168}}
%
\thicklines\put(275,163){\line(3,-1){168}}\thinlines
%
%---------------------------------------------------------------
%************* Der Pfeil von der Mitte nach Unten ******** 
%
\put(230,82){\vector(0,-1){56}}
% 
%************* Pfeile von der Mitte nach ganz Unten ******** 
%
\put(-5,82){\vector(3,-2){200}}
%
\put(450,82){\vector(-3,-2){200}}
%
%---------------------------------------------------------------
%************* Horizontale Pfeile in der Mitte ***************
%
\put(65,95){\vector(-1,0){50}}
%
\put(185,95){\vector(-1,0){45}}
%
\put(275,95){\vector(1,0){45}}
%
\put(395,95){\vector(1,0){45}}
%
%-------------------------------------------------------------
%************* Pfeile von Unten zur Mitte ********************* 
%
\thicklines\put(175,26){\line(-3,1){168}}\thinlines
%
\put(175,26){\vector(-3,1){168}}
%
\put(198,26){\vector(-3,2){84}}
%
\put(250,26){\vector(3,2){84}}
%
\put(268,26){\vector(3,1){168}}
%
\thicklines\put(268,26){\line(3,1){168}}\thinlines
% 
%******************** Beschriften ************************
%
\put(65,135){\makebox(0,)[r]{$pr_{2}$}}
%
\put(150,135){\makebox(0,)[r]{$r$}}
%
\put(310,135){\makebox(0,0)[r]{$r$}}
%
\put(380,135){\makebox(0,0)[l]{$q$}}
%
\put(235,135){\makebox(0,0)[l]{$\omega$}}
%
\put(60,105){\makebox(0,0)[r]{$ev^{*}$}}
%
\put(175,105){\makebox(0,0)[r]{$pr_{2}$}}
%
\put(305,105){\makebox(0,0)[r]{$pr_{2}$}}
%
\put(420,105){\makebox(0,0)[r]{${}^{\#}$}}
%
\put(70,51){\makebox(0,0)[r]{$p$}}
%
\put(150,51){\makebox(0,0)[r]{$t$}}
%
\put(310,51){\makebox(0,0)[r]{$t$}}
%
\put(372,51){\makebox(0,0)[l]{$pr_{1}$}}
%
\put(235,51){\makebox(0,0)[l]{$\psi_{A}^{n}$}}
%
\put(80,10){\makebox(0,0)[r]{${}^{\#}$}}
%
\put(367,10){\makebox(0,0)[l]{$\delta$}}
%
\end{picture}
\end{center}
\end{footnotesize}
In diesem Diagramm erkennt man in dem dicker ausgezogenen Rhombus das in 
\cite{DS2,DS3} etablierte Viereck, und aus einem  Vergleich mit
der dort gegebenen Definition f"ur die Abbildung $\Psi$ geht
unmittelbar hervor, da"s diese mit der Komposition 
$\psi_{A}^{n}\scirc \omega$
"ubereinstimmt.
Ferner lassen sich die dort gezogenen Folgerungen aus dem
vervollst"andigten Diagramm besonders bequem ablesen:

\smallskip
\noindent
{\bf 1.} Hat die Menge $A$ die Kardinalit"at $q$, dann gilt:
\begin{eqnarray*}
n! \cdot q^{n}  &=& \#[n]!\times A^{[n]}=
                        \#T_{P(A)}([n]) = \#s_{P(A)}([n])\\
                &=& \sum_{u\in s^{n}(P(A))}\# pr_{1}^{-1}(u)\\
                &=& \sum_{u\in s^{n}(P(A))}n!\\
                &=& n!\cdot \# s^{n}(P(A))
\end{eqnarray*}
und es folgt
\[
q^{n}=  \# s^{n}(P(A))
\]
{\bf 2.} Ist  $v \in S^{n}(A)$, dann ist die Anzahl der Elemente $f\in A^{n}$,
f"ur die ${}^{\#}f=v$ ist, bekanntlich gleich 
dem (in \cite{DS2,DS3} mit $((v))$ bezeichneten)
Multinomialkoeffizienten 
$ \binom{n}{v}:= \frac{n!}{v!}
        :=\frac{n!}{\prod_{a\in A}v(a)!}$.
Folglich ist die Anzahl der $(u,\Phi)\in s_{P(A)}([n])$, die durch die
Komposition ${}^{\#}\scirc p$ auf $v$ abgebildet werden, gleich der
Anzahl der $(\sigma,\pi)\in T_{P(A)}([n])$,  die durch
${}^{\#}\scirc ev^{*} \scirc pr_{2}$ auf $v$ abgebildet werden,
also gleich $ n!\cdot \binom{n}{v}$. Andererseits ist
diese Anzahl
wegen der Kommutativit"at des unteren Vierecks in unserem Diagramm
aber auch die Anzahl der Urbilder von $v$ unter
$\delta\scirc pr_{1}$, und  da alle Fasern der Projektion
$pr_{1}:s_{P(A)}([n])\rightarrow s^{n}(P(A))$ die gleiche
Kardinalit"at $n!$ haben,
folgt, da"s die Menge 
$\delta^{-1}(v)$ genau $\binom{n}{v}$ Elemente hat.
F"ur diese Menge gilt aber
\begin{eqnarray*}
\delta^{-1}(v)  &=& \{u\in s^{n}(P(A))\mid \delta(u)=v\}\\
                &=& \{u\in s^{n}(P(A))\mid \sum_{g(0)=a}
                        u(g)=v(a) \quad \mbox{ f"ur alle }a\in A \}
\end{eqnarray*}
Definiert man also f"ur jede Bahn $T$ (unter dem Shift--Operator
$\alpha$) in $P(A)$ und jedes $a\in A$ die Zahlen
\begin{eqnarray*}
\Delta(a,T)&:= &\#\{g\in T \mid g(0)= a\}\\
        &=& \sum_{
\begin{array}{c}
                \scriptstyle            g \in T \\[-6pt]
                \scriptstyle                    g(0)= a
                
\end{array}}       1
\end{eqnarray*}
und setzt $u(T)$ gleich dem gemeinsamen Wert von $u$ auf allen
Elementen der Bahn $T \subset P(A)$, dann erh"alt man
\begin{eqnarray*}
\delta^{-1}(v)  &=& \{u\in s^{n}(P(A))\mid \sum_{T\subset P(A)}
        \Delta(a,T)\cdot u(T)=v(a) \quad \mbox{ f"ur alle }a\in A \}\\
                &=& \{u\in s^{n}(P(A))\mid \Delta \cdot u = v\}.
\end{eqnarray*}
Wegen $\# \delta^{-1}(v)=\binom{n}{v} $ ergibt sich
hieraus also unmittelbar die Aussage von Theorem 1 aus \cite{DS2},
da"s die Anzahl der ganzzahligen, nicht negativen L"osungen der linearen
diophantischen Gleichung 
$\Delta \cdot u = v$ gerade gleich $\binom{n}{v}$ ist.

3. Ist die Menge $A$ linear geordnet, beispielsweise
$A=\N=\{1,2,\dots \}$, dann tragen auch die Mengen $A^{n}$ und
$P(A)$ kanonische lineare Ordnungen. Auf der Menge $A^{n}$ ist es
die lexikographische Ordnung, auf der Menge $P(A)$ ist es die
folgenderma"sen definierte lineare Ordnung: Es gilt $g<g'$ genau dann,
wenn es ein  $k \in \No$ gibt, so da"s 
\begin{eqnarray*}
ev(\alpha^{k} \cdot g)  & < & ev(\alpha^{k} \cdot g')\\
ev(\alpha^{k-1} \cdot g)& = & ev(\alpha^{k-1} \cdot g')\\
 \vdots                 & = & \vdots \\
ev(\alpha \cdot g)      & = & ev(\alpha \cdot g')\\
ev(g)                   & = & ev(g')
\end{eqnarray*}
gilt.

Betrachtet man $P(A)$ mit dieser Ordnung, dann gibt es
zu jedem $u\in s^{n}(P(A))$ genau
eine monotone Abbildung
$\pi_{u}:[n]\rightarrow P(A)$, f"ur die
${}^{\#}\pi_{u} = u$ ist. Die Zuordnung 
$u \mapsto \pi_{u}$ definiert also einen
kanonischen Schnitt $\lambda:s^{n}(P(A))\rightarrow  P(A)^{([n])}$
f"ur die Abbildung 
${}^{\#}:P(A)^{([n])} \rightarrow  s^{n}(P(A))$. 
Die Komposition 
$\rho_{A}^{n} \scirc \lambda:s^{n}(P(A)) \rightarrow s_{P(A)}([n])$ von
$\lambda$ 
mit dem am Ende des letzten Paragraphen definierten
$t$--Schnitt $\rho_{A}^{n}:P(A)^{([n])}\rightarrow s_{P(A)}([n])$
liefert 
daher einen Schnitt f"ur die Komposition ${}^{\#}\scirc t$. Komponiert
mit dem Inversen von $\psi_{A}^{n}$ definiert dieser
eine kanonische, eineindeutige Korrespondenz zwischen den
Elementen von $s^{n}(P(A))$ und der Menge derjenigen Elemente
$(\sigma,\pi)\in T_{P(A)}([n])$, f"ur die die Abbildung 
$\pi:[n]\rightarrow P(A)$ monoton w"achst und die Permutation $\sigma$ auf
den {\em Konstanz--Intervallen} von $\pi$ (d.h. den Fasern von $\pi$)
ebenfalls 
monoton w"achst. Da die Evaluationsabbildung $ev:P(A)\rightarrow A$
gleichfalls monoton w"achst, ist die Komposition $f:= ev \scirc \pi$ f"ur jedes Element
$(\sigma,\pi)$ der beschriebenen Menge, ebenso wie die Funktion
$\pi$ monoton wachsend. Es zeigt sich, da"s die Permutation
$\sigma$ sogar auf den Fasern der Funktion $f$ monoton w"achst.
Sind n"amlich  $\epsilon$ und $ \epsilon'$ Elemente von $[n]$ mit
$\epsilon < \epsilon'$ , $f(\epsilon) = f(\epsilon')$ aber
$\pi(\epsilon) < \pi(\epsilon')$, dann gilt aufgrund der Definition
der Ordnung 
in $P(A)$  auch 
$\alpha\cdot\pi(\epsilon) < \alpha\cdot\pi(\epsilon')$. Weil $\pi$
"aquivariant ist, folgt hieraus 
$\pi(\sigma(\epsilon))< \pi(\sigma(\epsilon'))$, und da $\pi$ monoton
w"achst, folgt hieraus $\sigma(\epsilon)<\sigma(\epsilon')$.
Insgesamt erh"alt man damit die folgende Aussage (cf. \cite{DW}):

\smallskip\noindent
{\sc Gessel'}s {\sc Lemma}\\
Ist die Menge $A$ linear geordnet, dann definiert der $q$--Schnitt 
\[
(\psi_{A}^{n}\scirc\omega)^{-1}\scirc \lambda:s^{n}(P(A))\rightarrow 
        [n]!\times A^{([n])}
\]
eine Bijektion von $s^{n}(P(A))$ auf die Menge derjenigen Elemente
$(\sigma,f) \in [n]!\times A^{([n])}$, f"ur die die Funktion $f$
monoton w"achst und die Permutation $\sigma$ auf den Fasern von $f$
ebenfalls.

\smallskip
Genauso einfach l"a"st sich im Falle eines linear geordneten $A$  die
von {\sc de~Bruijn} und {\sc Klarner} definierte Bijektion 
$A^{n} \stackrel{\sim}{\rightarrow} s^{n}P(A)$ (cf.~\cite{dBK})
durch die Konstruktion
geeigneter Schnitte in dem obigen Diagramm herleiten (cf.~\cite{DS3}).


\medskip
\begin{center}
{\bf Zyklische Mengen und Funktoren}
\end{center}

\noindent
Aus unserer Diskussion folgt weiterhin, da"s die Kardinalit"aten der
Werte der Funktoren
\[
E\mapsto T_{X}(E)
\]
und
\[
E\mapsto s_{X}(E),
\]
die auf der Kategorie der enlichen Mengen (mit den Bijektionen als
Morphismen) definiert sind,
 "ubereinstimmen, d.h. da"s f"ur jede endliche \mbox{Menge $E$}
\[
\#T_{X}(E)=\#s_{X}(E)
\]
gilt. Als unmittelbare Konsequenz der Definitionen ergeben sich
dar"uber hinaus die folgenden funktoriellen Bijektionen:
\[
T_{X\sqcup Y}(E) \cong 
\coprod_{F \subset E}T_{X}(F)\times T_{Y}(E \setminus F)
\]
und
\[
s_{X\sqcup Y}(E) \cong 
\coprod_{F \subset E}s_{X}(F)\times s_{Y}(E \setminus F).
\]
Mit der von {\sc Joyal} vorgeschlagenen Definition des Produktes solcher
Funktoren (cf.~\cite{J}) hat man also
\[
T_{X\sqcup Y} \cong T_{X}\cdot T_{Y} \quad \mbox{und} \quad
s_{X\sqcup Y} \cong s_{X}\cdot s_{Y}.
\]
Ist daher 
$X\cong \coprod a_{k}C(k)$ die kanonische Zerlegeung der zyklischen
Menge $X$ in Bahnen, wobei $C(k)$ den {\em Zyklus der L"ange k}
bezeichnet und $a_{k}$ die Vielfachheit angibt, mit der dieser in der
Zyklenzerlegung von $X$ vorkommt, dann hat man die kanonischen
Zerlegungen 
\[
T_{X}(E) \cong \prod (T_{C(k)}(E))^{a_{k}}
\]
und 
\[
s_{X}(E) \cong \prod (s_{C(k)}(E))^{a_{k}}.
\]
F"ur die Kardinalit"aten der Werte des Funktor $s_{C(k)}$ ergibt sich
unmittelbar aus der Definition (siehe auch \cite{DS1}):
\[
\#s_{C(k)}(E)= \left \{
\begin{array}{lll}
(\#E)! & \mbox{falls} & k \mbox{ ein Teiler von } \#E \mbox{ ist}\\
0 & \mbox{sonst} &
\end{array}
\right .
\]
Man erh"alt somit f"ur die  von  {\sc Joyal} in \cite{J} f"ur Funktoren $F$
der obigen Art definierte {\em Kardinalit"at}
\[
\# F := \sum_{n=0}^{\infty}\#F([n])\cdot \frac{t^{n}}{n!}
\]
im Falle $F=T_{C(k)}$ und $F=s_{C(k)}$ die  Reihe
\[
\#T_{C(k)}=\#s_{C(k)}
        =\sum_{i=0}^{\infty}(k\cdot i)!\frac{t^{k\cdot i}}{(k\cdot i)!}
        =\frac{1}{1-t^{k}}.
\]

F"ur die Kardinalit"at der zu einer beliebigen  zyklischen Menge
geh"origen Funktoren ergibt sich dann wegen der leicht zu
verifizierenden Formel
\mbox{$\#(F_{1}\cdot F_{2})=\# F_{1} \cdot \# F_{2}$}
die folgende Identit"at von
Potenzreihen: 
\[
\#T_{X} = \#s_{X} 
=\prod_{j=1}^{\infty}\left(\frac{1}{1-t^{j}}\right)^{a_{j}}.
\]
Ist insbesondere $X=P(A)$ und enth"alt die Menge $A$ gerade
$q$ Elemente, dann liefert die kanonische Zyklenzerlegung 
\[
P(A)= \sum_{j=1}^{\infty}M(q,j)C(j)
\]
von $P(A)$, in welcher die Koeffizienten $M(q,j)$ gerade die durch
M"obius Inversion berechenbaren und im Kontext der {\em zyklotomischen
Identit"at} diskutierten (cf.~\cite{MR1,MR2,DS1})
Gr"o"sen 
\[
M(q,j)=\frac{1}{j}\sum_{d|j}\mu(j)q^{j/d}
\]
bezeichnen,
zusammen mit der aus unserem Diagramm folgenden Tatsache,
da"s $\#s^{n}(P(A)) =q^{n}$ ist, die folgende Identit"at von
Potenzreihen
\[
\frac{1}{1-qt}
=\prod_{j=1}^{\infty}\left(\frac{1}{1-t^{j}}\right)^{M(q,j)},
\]
also gerade die zyklotomische Identit"at.

\pagebreak
\footnotesize
\begin{thebibliography}{MR2}
%
\bibitem[dBK]{dBK}
{\sc de~Bruijn} (N.G.) and {\sc 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.) and {\sc Siebeneicher} (Ch.) ---
{\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.) und {\sc Siebeneicher} (Ch.) ---
{\em Ein Lemma "uber Perlenketten},
S\'eminaire Lotharingien de Combinatoire, $20^{e}$ session,
Publ. I.R.M.A. Strasbourg, (1988), 47--55.
%
\bibitem[DS3]{DS3}
{\sc Dress} (A.W.M.) and {\sc Siebeneicher} (Ch.) ---
{\em On the Number of Solutions of Certain Linear Diophantine Equations}
to appear in: Hokkaido Mathematical Journal.
%
\bibitem[DW]{DW}
{\sc D\'esarm\'enien} (J.) et {\sc Wachs} (M.) --- 
{\em Descentes des d\'erangement et mots crculaires},
S\'eminaire Lotharingien de Combinatoire, $19^{e}$ session,
Publ. I.R.M.A. Strasbourg, (1988), 13--21.
%
\bibitem[J]{J}
{\sc Joyal} (A.) ---
{\em Une Th\'eorie combinatoire des s\'eries formelles},
Advances in Mathematics, vol.~{\bf 42} (1981), 1--82.
%
\bibitem[MR1]{MR1}
{\sc Metropolis} (N.) and {\sc Rota} (G.-C.) --- 
{\em Witt Vectors and the Algebra of Necklaces},
Advances in Mathematics, vol.~{\bf 50} (1983), 95--125.
%
\bibitem[MR2]{MR2}
{\sc Metropolis} (N.) and {\sc Rota} (G.-C.) --- 
{\em The cyclotomic Identity},
Contemporary Mathematics, 
vol.~{\bf 34} Amer.~Math. Soc. (1984), 19--24.  
%
\bibitem[V]{V}
{\sc Viennot} (G.) ---
{\em Alg\'ebre de Lie Libres et Monoides Libres},
Lecture Notes in Mathematics {\bf 691}, Springer (1978).
%
\bibitem[VW]{VW}
{\sc Varadarajan} (K.) and {\sc Wehrhahn} (K.),
{\em Aperiodic Rings, Necklace Rings and Witt Vectors}, preprint (1988). 
%
\end{thebibliography}

\end{document}


\bibitem[MR2]{MR2}
N.~Metropolis and G.-C.~Rota:
{\em The cyclotomic Identity},\\
in Contemporary Mathematics vol.~{\bf 34}  AMS (1984), 19--24.
