Analysis situs. Un problème d'énumération. (Q1828168)

Verf. beginnt mit der folgenden Aufgabe: Über einer Geraden seien in der oberen Halbebene \(p\) Halbkreise gezeichnet, die (einschließlich der Endpunkte) paarweise zueinander fremd sind; die Anzahl \(N_p\) derartiger Figuren ist zu bestimmen. Versteht man unter einem größten Halbkreis einen solchen, über den sich kein anderer mehr spannt, und unter einem System alle von einem größten umschlossenen Halbkreise (einschließlich des größten selbst), so ergibt sich die Rekursionsformel \[ N_{p+1,s}=\textstyle \sum\limits_{\nu =s-1}^{p} \displaystyle N_{p,\nu }\;\;\;(p\geqq 1,\;\,s\geqq 1),\qquad N_{p,\,0}\;\;\;=0,\;\;N_{1,\,1}=1, \] für die Anzahl \(N_{q,r}\) der Figuren aus \(q\) Halbkreisen, die in \(r\) Systeme verteilt sind, und \[ N_p=\textstyle \sum\limits_{s=1}^{p} \displaystyle N_{p,s}=N_{p+1,1}. \] Das aus dieser Rekursionsformel entstehende Zahlenschema ist bekannt (\textit{Lucas}, Théorie des nombres (Paris 1891; F. d. M. 23, 174 (JFM 23.0174.*)), S. 84 ff.); in geschlossener Form ergibt sich \[ N_{p,s}=\frac{s}{p}\frac{(2p-s-1)\,!}{(p-s)\,!\,(p-1)\,!}, \;\;N_p=\frac{1}{p+1}\frac{(2p)\,!}{p\,!\,p\,!}. \] Ein anderer Weg zur rekursiven Berechnung von \(N_p\) führt über die Abzählung der Figuren, bei denen eine Anzahl von Halbkreisen (und die Lage der Endpunkte der übrigen) vorgegeben ist. Verf. untersucht dann die Anzahl \(L_l\) der ``irreduziblen'' Figuren aus \(l\) Halbkreisen, d. h. solcher, die nicht durch Aneinanderreihen gleicher Teilfiguren entstehen. Er findet \[ L_l=\textstyle\sum\limits_{\varepsilon |l}\displaystyle\mu (\varepsilon )N_{\tfrac{l}{\varepsilon }}\quad(\mu \;\text{\textit{Moebius}funktion}), \] und für irreduzible Figuren mit gegebener Systemzahl \(s\) \[ L_{l,s}=\textstyle \sum\limits_{\varepsilon |(l,s)}\displaystyle \kern-3pt\mu (\varepsilon )N_{\tfrac{l}{\varepsilon },\tfrac{s}{\varepsilon }}. \] Ersetzt man nunmehr in der ursprünglichen Aufgabe die Gerade durch einen Kreis, mit anderen Werten: sieht man von zyklischer Vertauschung der Halbkreisendpunkte auf der Geraden ab, so ist offenbar der Aufbau einer Figur aus gleichen irreduziblen Figuren für die Ermittlung der zyklischen Symmetrien von Wichtigkeit. Für die Anzahl \(H_p\) von zyklisch verschiedenen Figuren aus \(p\) Halbkreisen ergibt sich eine recht komplizierte Formel \(\biggl(\)sie enthält Ausdrücke wie \(\sum\limits_{_{\substack{ l|p\\l<p}}}2l\textstyle \sum\limits_{s=1}^{l} \displaystyle\dfrac{1}{s}L_{l,s}\) und einen ähnlichen, ohne den Koeffizienten \(2l\)\(\biggr)\). Sie verdient Interesse, weil sie zugleich die Anzahl der verschiedenen \textit{ebenen} Bäume mit \(p\) Kanten angibt, wobei zwei ebene Bäume auch dann als verschieden anzusehen sind, wenn sie zwar homöomorph, aber in der Ebene nicht isotop sind. Zum Schluß zählt Verf. auf ähnliche Weise die verschiedenen ebenen Bäume gegebener Kantenzahl mit lauter Verzweigungspunkten der Ordnung 3 ab.