\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}