×

zbMATH — the first resource for mathematics

A logical expansion in mathematics. (English) JFM 58.0605.08
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 Birkhoffschen 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 (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.)

PDF BibTeX XML Cite
Full Text: DOI