×

The number of labeled two-terminal series-parallel networks. (English) Zbl 0075.01101

Die Arbeit behandelt die kombinatorische Frage nach der Anzahl der auf Reihen- und Parallelschaltung zurückführbaren Netzwerke mit \(n\) Zweigen, wobei noch einige oder alle dieser Zweige durch \(r\) verschiedene Marken unterschieden werden können. Dabei gelten Netzwerke als nicht verschieden, die man durch Vertauschen von in Serie liegenden oder von parallel liegenden Bestandteilen ineinander überführen kann. Mit den fraglichen Anzahlen als Potenzreihenkoeffizienten wird eine erzeugende Funktion von zwei Variablen gebildet. Für diese Funktion lassen sich mit Hilfe eines Satzes von G. Pólya [Acta Math. 68, 145–254 (1937; Zbl 0017.23202)] Relationen aufstellen, die Rekursionsformeln entsprechen. Als Anwendung ergeben sich Kongruenzeigenschaften für die Anzahlen, die besonders im Falle von lauter verschieden markierten Zweigen \((n = r)\) bemerkenswert sind.
Reviewer: Alfred Stöhr

MSC:

05A15 Exact enumeration problems, generating functions

Keywords:

Combinatorics

Citations:

Zbl 0017.23202
PDFBibTeX XMLCite
Full Text: DOI