Überdeckungen endlicher Mengen durch Teilmengen Kommentare sind willkommen.
Einführung
Aus der Theorie der Partitionen ist bekannt, wieviele disjunkte Überdeckungen für eine endliche Teilmenge durch ein Tupel von \(m\) nicht-leeren Teilmengen existieren. In diesem Beitrag wird die entsprechende Anzahl aller solcher Überdeckungen angegeben. Der Beweis verwendet elementare Kombinatorik.
Die Zahlenfolge OEIS A183109 \((1, 1, 7, 1, 25, 265, 1, 79, 2161, 41503, ...)\) in der OEISTM Datenbank dient als Startpunkt für dieses Problem. Diese Folge gibt die Anzahl binärer Matrizen ohne Null-Zeilen oder Null-Spalten an. Für \((n\times m)-\)Matrizen stellen die Folgenglieder auch die Anzahl \(u(n,m)\) der Überdeckungen einer \(n-\)elementigen Menge durch \(m\) nicht-leere Teilmengen dar (siehe Abschnitt 2). OEIS führt dafür keinen Beweis an. Riordan und Stein beweisen in [1], dass dieses Resultat ein Spezialfall eines sehr viel allgemeineren Theorems ist, das eine aufwändige Herleitung erfordert. In Abschnitt 3 wird ein kurzer Beweis geführt.
Im Folgenden sei \(M\) eine nicht-leere Menge mit \(|M| = n\) . \((B_1,~...~,B_m)\) sei ein \(m-\)Tupel von Teilmengen von \(M\) und \((A_1,~...~,A_m)\) ein \(m-\)Tupel nicht-leerer Teilmengen von \(M\) .
1. Der disjunkte Fall
Ist \((A_1,~...~,A_m)\) eine disjunkte Überdeckung von \(M\) , so ist die Menge \(\{A_1,~...~,A_m\}\) eine \(m-\)Partition von \(M\). Die Anzahl der \(m-\)Partitionen einer \(n-\) elementigen Menge wird durch die Stirling-Zahl 2. Art \(S(n,m)\) angegeben, siehe [2; 3.39].
\[S(n,m) = \frac{1}{m!}\sum_{j=0}^m (-1)^{m-j} \binom{m}{j} j^n\]
Da \((A_1,~...~,A_m)\) ein (geordnetes) \(m-\)Tupel ist und die \(A_i\) wegen der Disjunktheit paarweise verschieden sind, gibt es \(m!\) mögliche Reihenfolgen der \(A_i\) . Also ist die Anzahl \(v(n,m)\) dieser Tupel
\[v(n,m) = m!\cdot S(n,m)\]
Somit beträgt die Anzahl disjunkter Überdeckungen \((A_1,~...~,A_m)\) von \(M\)
\[v(n,m) = \sum_{j=0}^m (-1)^{m-j} \binom{m}{j} j^n\]
Wir zitieren dieses bekannte Resultat, weil die in Abschnitt 3 hergeleitete Formel für den nicht-disjunkten Fall von sehr ähnlicher Gestalt ist. - \(v(n,m)\) ist auch die Anzahl der surjektiven Abbildungen einer \(n-\)elementigen auf eine \(m-\)elementige Menge.
Die OEIS Datenbank enthält \(v(n,m)\) als Zahlenfolge OEIS A019538 \((1, 1, 2, 1, 6, 6, 1, 14, 36, 24, 1, 30, 150, 240, 120, ...)\). Diese Folge wird zunächst in einer Dreiecksgestalt mit \(v(n,m)\) in der \(n-\)ten Zeile an der \(m-\)ten Position dargestellt, mit \(m = 1,~...~,n\) ; die Zeilen werden dann zur Folge verkettet. (Das gleiche Prinzip gilt für die Folge \(u(n,m)\) aus der Einführung, die in Abschnitt 3 behandelt wird).
2. Überdeckungen und Matrizen
Ein \(m-\)Tupel \((B_1,~...~,B_m)\) von Teilmengen von \(M = \{m_1,~...~,m_n\}\) lässt sich repräsentieren durch eine \((n\times m)-\)Matrix \(B\) mit den Einträgen \(b_{ik} = 1\) für \(m_i \in B_k\) und \(b_{ik} = 0\) für \(m_i \notin B_k\) . Die \(i-\)te Zeile von \(B\) zeigt somit an (durch \(b_{ik} = 1\)), welche Teilmengen \(B_k\) das Element \(m_i\) enthalten, und die \(k-\)te Spalte von \(B\) zeigt an, welche Elemente von \(M\) auch Elemente von \(B_k\) sind. Das Gleiche gilt für \((A_1,~...~,A_m)\) , wenn man \(B_k\) durch \(A_k\) ersetzt.
Eine disjunkte Überdeckung von \(M\) durch \((A_1,~...~,A_m)\) entspricht einer Matrix \(B\) , die in jeder Zeile genau einen Eintrag \(1\) und in jeder Spalte mindestens einen Eintrag \(1\) aufweist.
Eine beliebige Überdeckung von \(M\) durch \((A_1,~...~,A_m)\) wird in Abschnitt 3 diskutiert und entspricht einer Matrix \(B\) , die in jeder Zeile und in jeder Spalte mindestens einen Eintrag \(1\) aufweist.
3. Überdeckungen einer Menge durch beliebige Teilmengen
Wir berechnen die Anzahl \(u(n,m)\) aller \(m-\)Tupel \((A_1,~...~,A_m)\) mit \(\bigcup A_k = M\) :
\[\textbf{(1)}~~~\textbf{Theorem}~~~u(n,m) = \sum_{j=0}^m (-1)^{m-j} \binom{m}{j} (2^j-1)^n\]
Beweis. Sei \((B_1,~...~,B_m)\) eine Überdeckung von \(M\) . Zur Erinnerung: Die Teilmengen \(B_k\) können leer sein. Die \((n\times m)-\)Matrix \(B\) ist wie in Abschnitt 2 definiert.
Da \((B_1,~...~,B_m)\) eine Überdeckung von \(M\) ist, muss jede Zeile von \(B\) mindestens eine \(1\) enthalten. Da es \(2^m-1\) verschiedene binäre \(m-\)Vektoren mit mindestens einer \(1\) gibt, folgt:
\[\textbf{(2)}~~~\text{Es gibt}~~(2^m-1)^n~~\text{verschiedene Matrizen}~~B.\]
Jede Matrix \(B\) enthält genau \(j\) Spalten mit mindestens einer \(1\) , mit einem \(j \in \{1,~...~,m\}\) . Die zugehörigen \(j\) Teilmengen \(B_k\) ergeben die Überdeckung von \(M\) und können mit \((A_1,~...~,A_j)\) identifiziert werden, während die anderen \(m-j\) Teilmengen leer sind. Wir nennen eine solche Matrix \(B\) eine \(j-\)deckende Matrix und erhalten:
\[\textbf{(3)}~~~\text{Es gibt}~~\binom{m}{j}\cdot u(n,j)~~~j\text{-deckende}~~(n\times m)\text{-Matrizen.}\]
Wir verbinden (2) und (3):
\[\textbf{(4)}~~~\sum_{j=1}^m \binom{m}{j} u(n,j) = (2^m-1)^n\]
\(u(n,j)\) in Gleichung (4) lassen sich mit der Binomischen Inversionsformel (5) für Zahlenfolgen \((a_j)\) und \((c_j)\) evaluieren, siehe [2; 3.38(i)] :
\[\textbf{(5)}~~~\sum_{j=0}^m \binom{m}{j} a_j = c_m~~~~\Rightarrow~~~~a_m = \sum_{j=0}^m \binom{m}{j} (-1)^{m-j} c_j\]
Mit \(u(n,0) = 0~,~~a_j = u(n,j)\) und \(c_m = (2^m-1)^n\) erhalten wir
\[u(n,m) = \sum_{j=0}^m \binom{m}{j} (-1)^{m-j} (2^j-1)^n~~~~~~~\textbf{qed.}\]
4. Bemerkungen
(a) Die Summenformeln für \(u(n,m)\) und \(v(n,m)\) sind von gleicher Gestalt.
(b) Die Anzahl \(m\) der Teilmengen kann die Anzahl \(n\) der Elemente übersteigen. Wie soll dann die Anordnung der \(u(n,m)\) zu einem "Dreieck" - wie am Ende von Abschnitt 1 beschrieben - gelingen? Die Antwort darauf zeigt, dass die in Abschnitt 2 verwendete Äquivalenz von "\(m-\)Überdeckungen" \((A_1,~...~,A_m)\) und Matrizen \(B\) günstig gewählt ist. Denn \(B\) ist eine binäre \((n\times m)-\)Matrix ohne Nullzeilen oder Nullspalten, und unter Transposition ist die Anzahl dieser Matrizen gleich der Anzahl binärer \((m\times n)-\)Matrizen ohne Nullzeilen oder Nullspalten. Diese Symmetrie erlaubt die Einschränkung \(m \le n\) , wie sie in OEIS A183109 verwendet wird. - Ein Beispiel: Die Anzahl der \(4-\)Überdeckungen einer \(12-\)elementigen Menge ist gleich der Anzahl der \(12-\)Überdeckungen einer \(4-\)elementigen Menge \((~u(12,4) = 129.690.975.930.463~)\).
(c) (1) lässt sich auch mit einem Inklusion-Exklusion-Beweis zeigen.
Literatur
[1] Riordan, J., Stein, P.R.: Arrangements on chessboards, Journal of Combinatorial Theory, Series A Vol. 12(1), 1972, S. 72-80
[2] Aigner, M.: Combinatorial Theory (Springer, Berlin, 2013)
Kommentare sind willkommen.
Stand 2020-10-13
Inhalt Blog | voriger Eintrag | nächster Eintrag
Manfred Börgens | Zur Leitseite
MB Matheblog # 10
english version