\documentstyle[a4,german,12pt,twoside,leqno]{report}
\topmargin0.8cm
\textheight21.4cm
\pagestyle{myheadings}
\markboth{\hfill {\sc a.~r.~kr\"auter} \hfill}{\hfill {\sc zirkulante matrizen} \hfill}
\begin{document}
\newcounter{abschnitt}
\newcounter{zaehler}[abschnitt]
\renewcommand{\theequation}{\arabic{abschnitt}.\arabic{zaehler}}
\renewcommand{\labelenumi}{[\arabic{enumi}]}

\thispagestyle{empty}

\setlength{\baselineskip}{12pt}

\noindent
{\footnotesize S\'eminaire Lotharingien de Combinatoire, B11b (1984), 11 pp.
\newline [Formerly: Publ.~I.~R.~M.~A.~Strasbourg, 1985, 266/S-11, p. 82 - 94.]}

\vspace{39pt}

\setlength{\baselineskip}{15pt}

\begin{center}
{\bf \"UBER DIE PERMANENTE GEWISSER ZIRKULANTER MATRIZEN UND DAMIT ZUSAMMENH\"ANGENDER 
TOEPLITZ-MATRIZEN}

\vspace{9pt}

{\sc von

\vspace{9pt}

Arnold Richard KR\"AUTER}
\end{center}

\vspace{21pt}

\setlength{\baselineskip}{12pt}

{\footnotesize {\sc Zusammenfassung.} \quad Zur Einf\"uhrung werden zwei Anwendungen der 
Permanente zir\-ku\-lan\-ter (0,1)-Matrizen auf klassische Abz\"ahlprobleme besprochen. Darauf 
folgt ein kurzer \"Uberblick \"uber die bisher erschienene einschl\"agige Literatur zu dem 
im Titel genannten Thema im Falle von (0,1)-Matrizen. F\"ur das analoge Problem bei 
$(1,-1)$-Matrizen werden schlie"slich einige neue Ergebnisse angek\"undigt, wobei auf die 
Pr\"asentation der zu ihrer Herleitung erforderlichen Me\-tho\-den
be\-son\-de\-rer Wert gelegt wird.
Eine dieser Methoden f\"uhrt nebenbei auf einen neuen Beweis der Touchardschen Formel f\"ur 
die reduzierten M\'enage-Zahlen.

\vspace{6pt}

{\sc Abstract.} \quad In the introductory section, a discussion of two applications of the 
permanent of circulant (0,1) matrices to classical enumeration problems is given, followed 
by a short survey of the hitherto published literature on the topic mentioned in the title 
in the case of (0,1) matrices. As to the analogous problem for $(1,-1)$ matrices, we 
announce a couple of recent results, where special attention is given to the presentation 
of the methods needed to establish them. By the way, one of these methods gives rise to a 
new proof of Touchard's formula for the reduced m\'enage numbers.}

\vspace{6pt}

\setlength{\baselineskip}{15pt}

\stepcounter{abschnitt} \stepcounter{zaehler}

\begin{center}
{\bf 1. Zwei einf\"uhrende Beispiele}
\end{center}

Die {\it Permanente} einer $n \times n$-Matrix $A = (a_{ij})$ ist definiert durch

\begin{equation}
{\rm per} \, A = \sum_{\sigma \in S_n} a_{1\sigma(1)} \cdot 
... \cdot
a_{n\sigma(n)},
\end{equation}
\stepcounter{zaehler}

\noindent wobei $S_n$ die symmetrische Gruppe der Ordnung $n$ bezeichnet. Ferner bezeichne 
$I_n$ die $n \times n$-Einheitsmatrix, $J_n$ die $n \times n$-Matrix mit lauter Einsen
und $P_n$ jene $n \times n$-Permutationsmatrix, deren Einsen in den Positionen (1,2), (2,3), 
..., $(n-1,n),$ $(n,1)$ stehen. \\
Das erste der hier zu behandelnden Beispiele ist das bekannte {\it probl\`eme des 
ren\-con\-tres} (Montmort, 1708), welches sich so formulieren l\"a"st: {\it Auf wieviele Arten 
k\"onnen sich $n$ Ehepaare zu $n$ Tanzpaaren formieren, so da"s kein Herr mit seiner Ehefrau
tanzt?}\\ 
Es bezeichne $X_i$ die Menge jener Damen, die mit dem $i$-ten Herrn tanzen d\"urfen $(i = 
1,...,n).$ Die {\it Inzidenzmatrix} f\"ur die Mengen $X_1,...,X_n$ ist dann gerade $J_n-I_n$ 
und die gesuchte Anzahl von M\"oglichkeiten ergibt sich gem\"a"s [15, p. 31] zu

\begin{equation}
{\rm per} \, (J_n-I_n) = d_n,
\end{equation}
\stepcounter{zaehler}

\noindent wobei $d_n$ die $n$-te {\it D\'erangement-Zahl}

\begin{equation}
d_n = \sum_{k=0}^n (-1)^k \, \displaystyle\frac{n!}{k!}
\end{equation}
\stepcounter{zaehler}

\noindent bezeichnet. Die Formel (1.2) l\"a"st sich mithilfe elementarer 
per\-ma\-nen\-ten\-the\-o\-re\-ti\-scher Methoden induktiv herleiten (siehe [15, p. 44]). \\ 
Im Vergleich dazu ist die L\"osung des {\it probl\`eme des m\'enages} (Lucas, 1891) etwas 
aufwendiger: {\it Auf wieviele Arten k\"onnen sich $n$ Ehepaare an einen runden Tisch
setzen, so da"s Damen und Herren abwechselnd sitzen und keine Dame neben ihrem Ehemann 
sitzt?} \\ 
Wir bestimmen diese Anzahl f\"ur den Fall, da"s die Sitzordnung der Herren bereits feststeht 
(daf\"ur gibt es klarerweise $2 \cdot n!$ M\"oglichkeiten). Dann lautet die 
In\-zi\-denz\-ma\-trix 
$J_n-I_n-P_n$ und die gesuchte Antwort

\begin{equation}
{\rm per} \, (J_n-I_n-P_n) = \mu_n,
\end{equation}
\stepcounter{zaehler}

\noindent wobei $\mu_n$ die $n$-te {\it reduzierte M\'enage-Zahl}

\begin{equation}
\mu_n = \sum_{k=0}^n (-1)^k \, \displaystyle\frac{2n}{2n-k} {2n-k \choose k} (n-k)!
\end{equation}
\stepcounter{zaehler}

\noindent bezeichnet (zu dieser Formel siehe Touchard [21, p. 632]).

\stepcounter{abschnitt} \stepcounter{zaehler}

\begin{center}
{\bf 2. Zirkulante und Toeplitzsche (0,1)-Matrizen}
\end{center}

Die in Abschnitt 1 behandelten Matrizen

\begin{equation}
J_n-I_n = \sum_{k=1}^{n-1} P_n^k \qquad \mbox{und} \qquad J_n-I_n-P_n = \sum_{k=2}^{n-1} 
P_n^k
\end{equation}
\stepcounter{zaehler}

\noindent sind Spezialf\"alle von

\begin{equation}
c_0 I_n + c_1 P_n + c_2 P_n^2 + ... + c_{n-1} P_n^{n-1},
\end{equation}
\stepcounter{zaehler}

\noindent wobei die $c_k$ entweder 0 oder 1 sind $(k = 0,...,n-1).$ Eine solche Matrix 
nennen wir {\it zirkulante $(0,1)$-Matrix:} bei gegebener erster Zeile der Matrix geht 
die $(i+1)$-te Zeile aus der $i$-ten $(i = 1,...,n-1)$ durch Verschiebung um eine Spalte 
nach rechts hervor (das $n$-te Element der $i$-ten Zeile wird erstes Element der $(i+1)$-ten 
Zeile). \\
Im allgemeinen ist die Permanente von (2.2) schwer zu berechnen, weshalb explizite Formeln 
bisher nur f\"ur Spezialf\"alle vorliegen. Wir w\"ahlen zun\"achst $c_0 = ... = c_{r-1} = 1$ 
und $c_r = ... = c_{n-1} = 0,$ betrachten also die Matrizen

\begin{equation}
Q(n,r) = \sum_{k=0}^{r-1} P_n^k.
\end{equation}
\stepcounter{zaehler}

Erste Untersuchungen \"uber die Permanente der $Q(n,r)$ stammen von Men\-del\-sohn [11]. Das 
weitere Interesse an dieser Matrizenklasse entspringt dem folgenden in [11, p. 32, Formel
(12)] enthaltenen Ergebnis, welches in unserer Notation so lautet: f\"ur festes $r$ gilt

\begin{equation}
{\rm per} \, Q(n,r) \sim K(r) \, \alpha^n,
\end{equation}
\stepcounter{zaehler}

\noindent wobei $K(r)$ eine nur von $r$ abh\"angige Konstante und $\alpha$ die im Intervall 
$]1,2[$ liegende Wurzel von $x^r - 2x^{r-1} + 1 = 0$ ist. F\"ur festes $r > 5$ und 
hinreichend gro"ses $n$ folgt wegen $\alpha < 2$

\[
K(r) \, \alpha^n < K(r) \, 2^n < \left(\displaystyle\frac{r}{e} \right)^n < n! \, \left( 
\displaystyle\frac{r}{n} \right)^n,
\]

\noindent also

\[
{\rm per} \, Q(n,r) < n! \, \left( \displaystyle\frac{r}{n} \right)^n.
\]

\noindent Damit w\"are in $\frac{1}{r} \, Q(n,r)$ eine einfache Matrizenklasse gefunden, 
welche die Ver\-mu\-tung von van der Waerden (mittlerweile von Falikman und Egory\v{c}ev 
bewiesen; siehe etwa [10, pp. 47 - 52]) ad absurdum f\"uhrt. In der Tat konnte Minc [14]
zeigen, da"s (2.4) bereits f\"ur $r \geq 5$ falsch ist. Ferner wies er darauf hin, da"s die 
Formeln f\"ur ${\rm per} \, Q(n,3)$ und ${\rm per} \, Q(n,4)$ in [11] inkorrekt sind. Wir 
begn\"ugen uns deshalb mit der Wiedergabe der fol\-gen\-den trivialen beziehungsweise bekannten 
Formeln aus [11, p. 31]:

\begin{equation}
\left\{ \begin{array}{l@{\quad = \quad}l}
        {\rm per} \, Q(n,1) & 1, \\
        {\rm per} \, Q(n,2) & 2, \\
        {\rm per} \, Q(n,n-2) & \mu_n, \\
        {\rm per} \, Q(n,n-1) & d_n, \\
        {\rm per} \, Q(n,n) & n!. \\
        \end{array} \right.
\end{equation}
\stepcounter{zaehler}

\noindent F\"ur $r \geq 3$ stellt sich heraus, da"s die Werte von ${\rm per} \, Q(n,r)$ eng
zusammenh\"angen mit der Permanente der Toeplitzschen (0,1)-Matrizen

\begin{equation}
\mbox{$ F(n,r) = \left[ \begin{array}{cccccc}
                1 & \cdots & 1 & 0 & \cdots & 0 \\
                1 & \ddots & & \ddots & \ddots & \vdots \\
                0 & \ddots & \ddots & & \ddots & 0 \\
                \vdots & \ddots & \ddots & \ddots & & 1 \\
                \vdots & & \ddots & \ddots & \ddots & \vdots \\
                0 & \cdots & \cdots & 0 & 1 & 1 \\
                \end{array} \right]
                \mbox{$ \begin{array}{l}
                \rule{0mm}{20,5mm} \\
                \!\!\! \left. \rule[-8.5mm]{0mm}{17mm} \right\} {\scriptstyle r-1} \\
                \end{array} $} $}.
\end{equation}
\stepcounter{zaehler}

\noindent (In einer {\it Toeplitz-Matrix} sind die Elemente mit gleicher Differenz von
Zeilen- und Spaltenindex gleich.)

\bigskip

{\sc Satz 1} \, (Minc [14, p. 257]). \quad {\it F\"ur alle} $n \geq 2r-2$ {\it gilt}

\begin{equation}
{\rm per} \, F(n,r) = f_{n,r-1},
\end{equation}
\stepcounter{zaehler}

\noindent {\it wobei} $f_{n,r}$ {\it die n-te Fibonacci-Zahl der Ordnung} $r,$

\begin{equation}
f_{n,r} = \left\{ \begin{array}{l@{\quad \mbox{ \it f\"ur} \quad}l}
                  0 & n < 0, \\
                  1 & n = 0, \\
                  f_{n-1,r} + ... + f_{n-r,r} & n > 0, \\
                  \end{array} \right.
\end{equation}
\stepcounter{zaehler}

\noindent {\it bezeichnet} (siehe Miles [13, p. 745]).

\bigskip

Unter Verwendung dieses Satzes lassen sich nun folgende Beziehungen herleiten:

\bigskip

{\sc Satz 2} \, (Minc [14, pp. 257 - 258]). \quad {\it F\"ur alle} $n \geq 5$ {\it gilt}

\begin{equation}
\left\{ \begin{array}{l@{\quad = \quad}l}
        {\rm per} \, Q(n,3) & f_{n-1,2} + 2 \, f_{n-2,2} + 2, \\
        {\rm per} \, Q(n,3) & {\rm per} \, Q(n-1,3) + {\rm per} \, Q(n-2,3)- 2, \\
        {\rm per} \, Q(n,3) & \left[ \frac{1}{2} \, (1+\sqrt{5})\right]^n + \left[
        \frac{1}{2} \, (1-\sqrt{5}) \right]^n + 2 \\
        \end{array} \right.
\end{equation}
\stepcounter{zaehler}

\noindent {\it und f\"ur alle} $n \geq 7$ {\it gilt}

\begin{equation}
\left\{ \begin{array}{lcl}
        {\rm per} \, Q(n,4) & = & 2 \, (f_{n-1,3} + 2 \, f_{n-2,3} + 3 \, f_{n-3,3} + 1), \\
        {\rm per} \, Q(n,4) & = & {\rm per} \, Q(n-1,4) + {\rm per} \, Q(n-2,4) \; + \\
        & & + \; {\rm per} \, Q(n-3,4) - 4, \\
        {\rm per} \, Q(n,4) & = &  2 \, (\alpha_1^n+\alpha_2^n+\alpha_3^n+1), \\
        \end{array} \right.
\end{equation}
\stepcounter{zaehler}

\noindent {\it wobei} $\alpha_1, \; \alpha_2, \; \alpha_3$ {\it die Wurzeln von}
$x^3-x^2-x-1=0$ {\it sind.}

\bigskip

Die in Satz 2 erw\"ahnten Rekursionsformeln f\"ur ${\rm per} \, Q(n,r)$ f\"uhren zu der 
fol\-gen\-den

\bigskip

{\sc Vermutung.} \quad {\it F\"ur alle} $n \geq 3$ {\it gilt}

\begin{equation}
{\rm per} \, Q(n,r) = \sum_{k=1}^{r-1} {\rm per} \, Q(n-k,r) + C(r),
\end{equation}
\stepcounter{zaehler}

\noindent {\it worin} $C(r)$ {\it eine nur von} $r$ {\it abh\"angige Konstante bezeichnet.}

\bigskip

Bereits f\"ur $r=5$ konnte aber ein Gegenbeispiel gefunden werden.

\bigskip

{\sc Satz 3} \, (Metropolis-Stein-Stein [12, p. 292]). \quad {\it F\"ur alle} $n \geq 15$ 
{\it gilt}

\begin{equation}
{\rm per} \, Q(n,5) = \sum_{k=1}^{10} a_k \, {\rm per} \, Q(n-k,5) + 24,
\end{equation}
\stepcounter{zaehler}

\noindent {\it wobei} $(a_1,...,a_{10}) = (2,2,0,-2,-8,-6,-2,0,2,1)$ {\it ist.}

\bigskip

In [12] findet man \"uberdies neben einer expliziten Rekursion f\"ur ${\rm per} \, Q(n,6)$ 
ausf\"uhrliche Tabellen der Werte von ${\rm per} \, Q(n,r)$ f\"ur $4 \leq r \leq 9, \quad r 
\leq n \leq 80.$ Eine gegen\"uber den bereits bekannten Formeln (2.9) neue Darstellung von 
${\rm per} \, Q(n,3)$ durch Summen von Binomialkoeffizienten wurde \"ubrigens von 
King und Parker [7] hergeleitet. \\ 
Permanenten von zirkulanten (0,1)-Matrizen, welche sich von den $Q(n,r)$ 
un\-ter\-schei\-den, 
wurden im Zusammenhang mit verschiedenen Aufgabenstellungen betrachtet, so beispielsweise 
bei der Behandlung des {\it mehrdimensionalen Dimerenproblems} (ei\-nen sch\"onen \"Uberblick 
\"uber den aktuellen Stand dieses von zahlreichen Forschern in Angriff genommenen Problems 
findet man bei Minc [16, pp. 233 - 236]). Andere erw\"ahnenswerte Untersuchungen stammen von
Tinsley [20] (Charakterisierung der Gleichheit von Permanente und Betrag der Determinante 
bei sogenannten {\it Abelschen} (0,1)-Matrizen), Brualdi-Newman [2] (Studium des 
asymptotischen Verhaltens der minimalen Permanente zirkulanter (0,1)-Matrizen), Kim-Roush 
[6] (Behandlung einer abgeschw\"achten Version der Vermutung von van der Waerden), 
Nemeth-Se\-ber\-ry-Shu [17] (Bestimmung der M\"achtigkeit des Wertebereiches der Permanente auf
der Menge aller zirkulanten $n \times n$-(0,1)-Matrizen) sowie Eades-Praeger-Seberry [5].

\newpage

\stepcounter{abschnitt} \stepcounter{zaehler}

\begin{center}
{\bf 3. Zirkulante und Toeplitzsche (1,--1)-Matrizen}
\end{center}

Zirkulante Matrizen und Toeplitz-Matrizen aus den Elementen 1 und $-1$ treten als extremale 
Matrizen bei Problemen auf, welche mit der Bestimmung guter oberer Schranken f\"ur die 
Permanente nichtsingul\"arer $(1,-1)$-Matrizen zusammenh\"angen (siehe Kr\"auter-Seifter 
[8], [9] und Seifter [19]). Es sind dies Matrizen der Bauart

\begin{equation}
\mbox{$ T(n,r) = \left[ \begin{array}{cccccc}
                -1 & \cdots & -1 & 1 & \cdots & 1 \\
                1 & \ddots & & \ddots & \ddots & \vdots \\
                \vdots & \ddots & \ddots & & \ddots & 1 \\
                \vdots & & \ddots & \ddots & & -1 \\
                \vdots & & & \ddots & \ddots & \vdots \\
                1 & \cdots & \cdots & \cdots & 1 & -1 \\
                \end{array} \right]
                \mbox {$ \begin{array}{l}
                \rule{0mm}{20.5mm} \\
                \left. \rule[-8.5mm]{0mm}{17mm} \right\} {\scriptstyle r}\\
                \end{array} $} $}
\end{equation}
\stepcounter{zaehler}

\noindent und

\begin{equation}
\mbox{$ Z(n,r) = \left[ \begin{array}{ccccccc}
                -1 & \cdots & -1 & 1 & \cdots & \cdots & 1 \\
                1 & \ddots & & \ddots & \ddots & & \vdots \\
                \vdots & \ddots & \ddots & & \ddots & \ddots & \vdots \\
                1 & & \ddots & \ddots & & \ddots & 1 \\
                -1 & \ddots & & \ddots & \ddots & & -1 \\
                \vdots & \ddots & \ddots & & \ddots & \ddots & \vdots \\
                -1 & \cdots & -1 & 1 & \cdots & 1 & -1 \\
                \end{array} \right]
                \mbox {$ \begin{array}{l}
                \rule{0mm}{25.5mm} \\
                \left. \rule[-8.5mm]{0mm}{17mm} \right\} {\scriptstyle r}\\
                \end{array} $} $}.
\end{equation}
\stepcounter{zaehler}

Die im vorigen Abschnitt erw\"ahnte Arbeit [5] verdient wegen der darin 
ent\-hal\-te\-nen Methoden 
zur Berechnung der Permanente besonderes Interesse. Hier sollen nun zwei weitere Methoden 
vorgestellt werden, welche bei der Betrachtung von $(1,-1)$-Matrizen von Nutzen sind. Dazu 
f\"uhren wir einige Bezeichnungen ein. F\"ur $k \leq n$ bezeichne $Q_{k,n}$ die Menge

\begin{equation}
Q_{k,n} = \left\{ \alpha = (\alpha_1,...,\alpha_k) \in {\bf N}^k: 1 \leq \alpha_1 < ... < 
\alpha_k \leq n \right\}.
\end{equation}
\stepcounter{zaehler}

F\"ur $\alpha, \beta \in Q_{k,n}$ sei $A(\alpha|\beta)$ jene $(n-k) \times 
(n-k)$-Untermatrix von $A,$ welche aus $A$ durch Streichung der Zeilen mit den Indizes 
$\alpha$ und der Spalten mit den Indizes $\beta$ entsteht (f\"ur $k = 0$ ist 
$A(\alpha|\beta) = A$). $A[\alpha|\beta]$ bezeichne das Komplement von $A(\alpha|\beta)$ in 
$A.$ \\
Zu jeder $n \times n$-$(1,-1)$-Matrix $A$ gibt es eine geeignete $n \times n$-(0,1)-Matrix 
$B,$ so da"s

\begin{equation}
A = J_n - 2B
\end{equation}
\stepcounter{zaehler}

\noindent gilt. Nach einem Satz \"uber die Permanente der Summe zweier Matrizen (Caianiello
[3, p. 644, Formel (18)]; siehe auch [15, p. 18, Theorem 1.4]) haben wir dann

\begin{equation}
\left\{ \begin{array}{lll} 
        {\rm per} \, A & = & \sum_{k=0}^n \sum_{\alpha,\beta \in Q_{k,n}} {\rm per} \,            
        (J_n[\alpha|\beta]) \; {\rm per} \, (-2 B(\alpha|\beta)) = \\ 
        & & \\
        & = &  \sum_{k=0}^n (-2)^k (n-k)! \, \sigma_k (B), \\
        \end{array} \right.
\end{equation}
\stepcounter{zaehler}

\noindent wobei

\begin{equation}
\left\{ \begin{array}{lll} 
        \sigma_k (B) & = & \sum_{\alpha,\beta \in Q_{n-k,n}} {\rm per} \,                 
        (B(\alpha|\beta)) \qquad \mbox{f\"ur}\quad 1 \leq k \leq n-1, \\ \sigma_0 (B)& =                       
        & 1, \\   
        \sigma_n (B)& = & {\rm per} \, B \\
        \end{array} \right.
\end{equation}
\stepcounter{zaehler}

\noindent ist. Die Bestimmung der Permanente einer $(1,-1)$-Matrix ist somit 
zur\"uckgef\"uhrt auf die Berechnung der Summen aller $k$-reihigen Unterpermanenten einer 
ent\-spre\-chen\-den (0,1)-Matrix. Die explizite Bestimmung von $\sigma_k (B)$ l\"a"st sich f\"ur 
kleine $k$ noch mit vertretbarem Aufwand durchf\"uhren. In bezug auf die Matrizen (3.1) und 
(3.2) erhalten wir f\"ur $r = 1$ und $r = 2$ folgende Resultate:

\bigskip

{\sc Satz 4.}

\begin{equation}
{\rm per} \, T(n,1) = \sum_{k=0}^n (-2)^k \, \displaystyle\frac{n!}{k!}.
\end{equation}
\stepcounter{zaehler}
\begin{equation}
{\rm per} \, Z(n,1) = {\rm per} \, T(n,1).
\end{equation}
\stepcounter{zaehler}

F\"ur $A = T(n,1)$ ist n\"amlich in (3.4) $B = I_n$ und somit f\"ur $0 \leq k \leq n$

\begin{equation}
\sigma_k (B) = {n \choose k}.
\end{equation}
\stepcounter{zaehler}

{\sc Satz 5.}

\begin{equation}
{\rm per} \, T(n,2) = \sum_{k=0}^n (-2)^k \, {2n-k \choose k} \, (n-k)!.
\end{equation}
\stepcounter{zaehler}
\begin{equation}
{\rm per} \, Z(n,2) = {\rm per} \, T(n,2) - 2 \, {\rm per} \, T(n-1,2).
\end{equation}
\stepcounter{zaehler}
\begin{equation}
{\rm per} Z(n,2) = \sum_{k=0}^n (-2)^k \, \displaystyle\frac{2n}{2n-k} {2n-k \choose k} \, 
(n-k)!.
\end{equation}
\stepcounter{zaehler}

Auf die Pr\"asentation detaillierter Beweise sowie auf die Behandlung der F\"alle $r \geq 3$ 
wollen wir hier verzichten; dies soll im Rahmen einer in Vorbereitung befindlichen 
ausf\"uhrlicheren Note geschehen.

\bigskip

{\sc Bemerkung.} \quad Ersetzt man in (3.4) $2B$ durch $B,$ erh\"alt man auf die gleiche 
Weise anstelle der Beziehungen (3.7) und (3.12) die Formeln (1.3) und (1.5). Die eben 
skizzierte Methode liefert somit unter anderem einen neuen Zugang zur 
Tou\-chard\-schen Formel 
f\"ur die reduzierten M\'enage-Zahlen. \\
F\"ur gro"se Werte von $r$ ist es n\"utzlich, einen anderen Weg einzuschlagen. Im probl\`eme 
des rencontres ist - mathematisch formuliert - die Anzahl jener
Per\-mu\-ta\-ti\-o\-nen aus $S_n$ zu 
bestimmen, welche keinen Fixpunkt besitzen, das hei"st kein $i$ wiederum in $i$ 
\"uberf\"uhren. Man kann also sagen, alle $(i,j)$-ten Elemente der Inzidenzmatrix mit $j = 
\sigma (i) = i$ f\"ur ein $\sigma \in S_n$ repr\"asentieren {\it verbotene
Po\-si\-ti\-o\-nen} von 
$\sigma.$ Diesen Sachverhalt wollen wir folgenderma"sen verallgemeinern: Die Matrix $A = 
(a_{ij})$ sei gegeben durch

\begin{equation}
a_{ij} = \left\{ \begin{array}{l}
         t, \quad \mbox{falls} \quad j = \sigma (i) \quad \mbox{f\"ur ein} \quad \sigma \in          
         S_n \quad \mbox{verboten ist,} \\
         1 \quad \mbox{sonst.}
\end{array} \right.
\end{equation}
\stepcounter{zaehler}

Jedem $\sigma \in S_n$ entspricht umkehrbar eindeutig das Produkt $a_{1 \sigma (1)} \cdot
... \cdot a_{n \sigma (n)};$ daraus und aus (3.13) folgt somit: $\sigma \in S_n$ {\it ist 
eine Permutation mit} $k$ {\it verbotenen Po\-si\-ti\-o\-nen genau dann, wenn} $a_{1 \sigma (1)} 
\cdot ... \cdot a_{n \sigma (n)} = t^k$ {\it gilt.} \\
Bezeichnet man nun mit $\nu_k$ die Anzahl der Permutationen mit $k$ verbotenen
Po\-si\-ti\-o\-nen, 
so erh\"alt man bei Summation \"uber alle $\sigma \in S_n$

\begin{equation}
\sum_{\sigma \in S_n} a_{1 \sigma (1)} \cdot ... \cdot a_{n \sigma (n)} = \sum_{k=0}^n \nu_k 
t^k =: N_n (t).
\end{equation}
\stepcounter{zaehler}

\noindent Der Ausdruck auf der linken Seite von (3.14) ist gem\"a"s (1.1) gerade ${\rm per} 
\, A.$ Wir fassen zusammen:

\begin{equation}
{\rm per} \, A = N_n (t).
\end{equation}
\stepcounter{zaehler}

\noindent Diese Beziehung soll im folgenden zur Berechnung von ${\rm per} \, T(n,n)$ 
herangezogen werden (siehe Kr\"auter-Seifter [8, pp. 57 - 58, Lemma 2]). Die Matrix $S_n (t) 
= (s_{ij})$ sei definiert durch

\begin{equation}
s_{ij} = \left\{ \begin{array}{l}
                 t \quad \mbox{f\"ur} \quad 1 \leq i \leq j \leq n, \\
                 1 \quad \mbox{sonst.} \\
                 \end{array} \right.
\end{equation}
\stepcounter{zaehler}

\noindent Dann gilt f\"ur das gem\"a"s den obigen Ausf\"uhrungen konstruierte, zur Matrix 
$S_n (t)$ geh\"orige Polynom $N_n (t)$ gem\"a"s (3.15)

\begin{equation}
{\rm per} \, S_n (t) = N_n (t).
\end{equation}
\stepcounter{zaehler}

\noindent Nach Riordan [18, p. 215] hat die Folge der Polynome $N_n (t)$ die exponentiell 
erzeugende Funktion (man definiert $N_0 (t) := 0$)

\begin{equation}
\sum_{n=0}^{\infty} N_n (t) \, \displaystyle\frac{x^n}{n!} = \displaystyle\frac{1-t}{1 - t 
\exp[x(1-t)]},
\end{equation}
\stepcounter{zaehler}

\noindent aus welcher f\"ur $t = -1$ mit (3.17) sofort

\begin{equation}
\sum_{n=0}^{\infty} {\rm per} \, T(n,n) \, \displaystyle\frac{x^n}{n!} = 
\displaystyle\frac{2}{1 + e^{2x}}
\end{equation}
\stepcounter{zaehler}

\noindent folgt. Die gleiche exponentiell erzeugende Funktion besitzt die Zahlenfolge \\
$2^n E_n (0),$ wobei $E_n (y)$ das $n$-te {\it Euler-Polynom} bezeichnet (siehe [4, p. 48, 
Formel (14b)]). Somit ist f\"ur alle $n \geq 0$

\begin{equation}
{\rm per} \, T(n,n) = 2^n E_n (0).
\end{equation}
\stepcounter{zaehler}

\noindent Der bekannte Zusammenhang von $E_n (0)$ mit den {\it Bernoulli-Zahlen} (siehe etwa 
[1, p. 805, Formel 23.1.20]) f\"uhrt bei geeigneter Zusammenfassung [1, p. 75, Formel 
4.3.67]) letztlich auf das folgende Ergebnis:

\bigskip

{\sc Satz 6.}

\begin{equation}
{\rm per} \, T(n,n) = (-1)^{(n+1)/2} \, \tau_n,
\end{equation}
\stepcounter{zaehler}

\noindent {\it wobei} $\tau_n$ {\it die} $n$-{\it te Tangenszahl} [4, p. 259], {\it 
definiert durch}

\begin{equation}
\sum_{n=0}^{\infty} \tau_n \, \displaystyle\frac{x^n}{n!} = \tan \, x,
\end{equation}
\stepcounter{zaehler}

\noindent {\it ist.}

\bigskip

{\sc Bemerkung.} \quad Wegen $\tau_{2k} = 0$ ist auch ${\rm per} \, T(2k,2k) = 0$ f\"ur alle 
$k \geq 0.$ Dieses Resultat findet man bereits bei Wang [22, p. 359, Example 2]. 
Abschlie"send notieren wir noch die (triviale) Formel f\"ur ${\rm per} \, Z(n,n):$

\bigskip

{\sc Satz 7.}

\begin{equation}
{\rm per} \, Z(n,n) = (-1)^n n!.
\end{equation}
\stepcounter{zaehler}

\begin{center}
{\sc Literatur}
\end{center}

\setlength{\baselineskip}{12pt}

\begin{footnotesize}
\begin{enumerate}

\item Milton {\sc Abramowitz} and Irene A. {\sc Stegun} (editors), {\it Handbook of 
Mathematical Functions.} Ninth printing. New York: Dover, 1972.
\item Richard Anthony {\sc Brualdi} and Morris {\sc Newman,} Some theorems on the permanent. 
{\it Jour\-nal of Research of the National Bureau of Standards (B)} {\bf 69,} 159 - 163 
(1965).
\item Eduardo E. {\sc Caianiello,} Regularization and renormalization I. General Part. {\it 
Il Nuovo Cimento (10)} {\bf 13,} 637 - 661 (1959).
\item Louis {\sc Comtet,} {\it Advanced Combinatorics.} Revised and enlarged edition. 
Translated from the French by J. W. {\sc Nienhuys.} Dordrecht: Reidel, 1974.
\item Peter {\sc Eades,} Cheryl Elisabeth {\sc Praeger,} and Jennifer Roma {\sc Seberry,} 
Some remarks on the permanents of circulant (0,1) matrices. {\it Utilitas Mathematica} {\bf 
23,} 145 - 159 (1983).
\item Ki Hang {\sc Kim} and Fred William {\sc Roush,} On a conjecture of Erd\H{o}s and 
R\'enyi. {\it Linear Algebra and Its Applications} {\bf 23,} 179 - 189 (1979).
\item Bruce W. {\sc King} and Francis Dunbar {\sc Parker,} A Fibonacci matrix and the 
permanent function. {\it The Fibonacci Quarterly} {\bf 7,} 539 - 544 (1969).
\item Arnold Richard {\sc Kr\"auter} and Norbert {\sc Seifter,} On some
questions concerning permanents of $(1,-1)$-matrices. {\it Israel Journal of Mathematics} 
{\bf 45,} 53 - 62 (1983).
\item Arnold Richard {\sc Kr\"auter} and Norbert {\sc Seifter,} Some properties of the 
permanent of $(1,-1)$-matrices. {\it Linear and Multilinear Algebra} {\bf 15,} 207 - 223 
(1984).
\item Arnold Richard {\sc Kr\"auter,} Permanenten - Ein kurzer \"Uberblick. {\it 
Publications de l'Insti\-tut de Recherche Math\'ematique Avanc\'ee Strasbourg} {\bf 230,} 39 
- 
83 (1984).
\item Nathan Saul {\sc Mendelsohn,} Permutations with confined displacements. {\it Canadian 
Ma\-the\-ma\-ti\-cal Bul\-le\-tin} {\bf 4,} 29 - 38 (1961).
\item Nicholas {\sc Metropolis,} Marvin Leonard {\sc Stein,} and Paul R. {\sc Stein,} 
Permanents of cyclic (0,1) matrices. {\it Journal of Combinatorial Theory} {\bf 7,} 291 - 
321 (1969).
\item Ernest P. {\sc Miles,} Jr., Generalized Fibonacci numbers and associated matrices. 
{\it The Ame\-ri\-can Mathematical Monthly} {\bf 67,} 745 - 752 (1960).
\item Henryk {\sc Minc,} Permanents of (0,1)-circulants. {\it Canadian Mathematical 
Bulletin} {\bf 7,} 253 - 263 (1964).
\item Henryk {\sc Minc,} {\it Permanents.} Encyclopedia of Mathematics and Its Applications, 
Volume 6. Reading: Addison-Wesley, 1978.
\item Henryk {\sc Minc,} Theory of permanents 1978 - 1981. {\it Linear and Multilinear 
Algebra} {\bf 12,} 227 - 263 (1983).
\item Evi {\sc Nemeth,} Jennifer {\sc Seberry,} and Michael {\sc Shu,} On the distribution 
of the permanent of cyclic (0,1) matrices. {\it Utilitas Mathematica} {\bf 16,} 171 - 182 
(1979).
\item John {\sc Riordan,} {\it An Introduction to Combinatorial Analysis.} Fourth printing. 
New York: Wiley, 1967.
\item Norbert {\sc Seifter,} Upper bounds for permanents of $(1,-1)$-matrices. {\it Israel 
Journal of Mathematics} {\bf 48,} 69 - 78 (1984).
\item Marion Franklin {\sc Tinsley,} Permanents of cyclic matrices. {\it Pacific Journal of 
Mathematics} {\bf 10,} 1067 - 1082 (1960).
\item Jacques {\sc Touchard,} Sur un probl\`eme de permutations. {\it Comptes Rendus de 
l'Aca\-d\'e\-mie des Sciences Paris} {\bf 198,} 631 - 633 (1934).
\item Edward Tzu-Hsia {\sc Wang,} On permanents of $(1,-1)$-matrices. {\it Israel Journal of 
Mathematics} {\bf 18,} 353 - 361 (1974).

\end{enumerate}
\end{footnotesize}

\vspace{36pt}

\begin{tabular}{lp{4.8cm}l}
& & Arnold Richard {\sc Kr\"auter} \\
& & Institut f\"ur Mathematik und \\
& & Angewandte Geometrie \\
& & Montanuniversit\"at Leoben \\
& & Franz-Josef-Stra"se 18 \\
& & A-8700 Leoben, \"Osterreich \\
& & E-mail: {\sf kraeuter@unileoben.ac.at} \\
\end{tabular}

\end{document}
