A logical expansion in mathematics. (Q5893004)

Gegeben sei eine endliche Anzahl \(n=n(1)\) von Elementen. \(A_i\) \((i=1,2,\dots,m)\) bedeute je eine Eigenschaft, \(n(A_i)\) bzw. \(n(\overline {A_i})\) die Anzahl der Elemente, die die Eigenschaft \(A_i\) haben bzw. nicht haben. Dann gilt: \[ \begin{gathered} n(\overline {A}_1\overline {A}_2\dots \overline A_m)=n-[n(A_1)+n(A_2)+\cdots +n(A_m)] \tag{*}\\ +[n(A_1 A_2)+n(A_1 A_3)+\cdots +n(A_{m-1}A_m)]-\cdots +(-1)^m n(A_1 A_2\dots A_m), \end{gathered} \] wobei der Ausdruck rechts unter Antwendung des Distributivgesetzes durch formales Ausrechnen von \(n[(1-A_1 )\dots (1-A_m )]\) gebildet ist. Verf. gibt einige Beispiele von mathematischen Antwendungen dieser Formel: je eine aus der Primzahllehre und der Wahrscheinlichkeitsrechnung sowie eine Ableitung der \textit{Birkhoff}schen Formel für die Anzahl der Färbungen einer Karte bzw. eines Graphen mit \(\lambda \) Farben, derart daß\ benachbarte Länder bzw. verbundene Ecken verschiedene Farben erhalten (\textit{Birkhoff}, 1912; F. d. M. 43, 572 (JFM 43.0572.*); ferner auch 1930; F. d. M. \(56_{\text{I}}\), 499. Vgl. auch Verf. 1931; F. d. M. \(57_{\text{I}}\), 727 und nachstehend besprochene Arbeit). Elemente sind dabei alle möglichen Färbungen des Graphen \(G\), die Eigenschaft \(A_{ab}\), die für jedes Paar von verbundenen Ecken \(a, b\) definiert ist, bedeutet: \(a\) und \(b\) haben gleiche Farbe. Dann ist \[ M(\lambda )=n(\overline {A}_{ab} \overline {A}_{ac} \dots \overline {A}_{ik}), \] wobei in der Klammer rechts alle \(\overline {A}_{ab}\) stehen. Ordnet man nun jedem einzelnen Glied der Formel (*): \((-1)^s n(A_{ab}\dots )\) (wobei \(n\) gerade für den Durchschnitt von \(s\) Eigenschaften \(A_{ab}\) gebildet ist) einen Graphen \(H\) zu, der aus allen Ecken von \(G\) und denjenigen Strecken von \(G\) besteht, deren Endpunkte in dem entsprechenden \(n(A_{ab}\dots )\) als Indexpaare auftreten, so ist \(n(A_{ab}\dots )\) offenbar gleich der Anzahl der Färbungen von \(H\), bei denen zusammenhängende Bestandteile von \(H\) gleich gefärbt sind, also gleich \(\lambda ^p\), wenn \(p\) die Anzahl der zusammenhängenden Bestandteile von \(H\) bedeutet, und \[ M(\lambda )=\sum _{p,s}(-1)^s (p,s)\lambda ^p, \] wo \((p,s)\) die Anzahl der Teilgraphen \(H\) von \(G\) mit \(s\) Strecken und \(p\) zusammenhängenden Bestandteilen bedeutet, oder auch \[ M(\lambda )=\sum _{i,j}(-1)^{i+j}m_{ij}\lambda ^{V-i}=\sum _i m_i \lambda ^{V-i} \quad \text{mit}\quad m_i=\sum _i (-1)^{i+j} m_{ij},\tag{**} \] wobei \(V\) die Anzahl der Ecken von \(G\), \(m_{ij}\) die Anzahl der Teilgraphen \(H\) vom Range \(i\) und der Nullität \(j\) bedeuten. Für die \(m_i\) gibt Verf. folgende Deutung: Bildet man alle Kreise von \(G\) und daraus - unter Beachtung gewisser Anordnungsvorschriften - die unvollständigen Kreise (``broken circuits'') durch Weglassen je einer Strecke aus einem Kreis, so ist \((-1)^i m_i\) die Anzahl der Teilgraphen mit \(i\) Strecken, die keinen unvollständigen Kreis ganz enthalten. (III 2.)