MB Matheblog # 39voriger Eintrag nächster Eintrag
Index der gesamten Website
| MB Matheblog # 39 |
Inhalt Blog voriger Eintrag nächster Eintrag |
zur Leitseite Index der gesamten Website |
Nicht-leere endliche Mengen werden hier der Einfachheit halber als \([n] = \{1,~...,~n\}\) dargestellt. Wir betrachten Mengen \(M_{(m)}~=~\{M_1,~...,~M_m\}\) von \(m\) paarweise verschiedenen Teilmengen \(M_i\) von \([n]\) . Eine solche Menge heißt "Überdeckung" (engl. "cover" oder "covering") von \([n]\) , oder genauer "\(m-\)Überdeckung", falls die Vereinigung \(\bigcup M_i = [n]\) ist. Die Anzahl möglicher Überdeckungen wird mit \(c.(n,.)\) bezeichnet; die Punkte werden ggfs. durch Symbole ersetzt, die für verschiedene Bedingungen an die Überdeckungen stehen. Werden die \(c.(n,.)\) tabellarisch dargestellt, steht \(n\) für die Zeilen.
1. Überdeckende \(M_{(m)}\) mit \(M_i~\neq~\emptyset\)
\(c~(n,m)\) Anzahl \(m-\)Überdeckungen mit nicht-leeren Teilmengen
\[m~\le~2^n-1\]
\[c~(n,m)~=~\sum_{i~=~0}^n~(-1)^{n-i}~\binom{n}{i}~\binom{2^i-1}{m}~=~\frac{1}{m!}~\sum_{i~=~0}^m~S_{1~}(m+1,~i+1)\cdot (2^i-1)^n\]
mit \(S_1\) Stirling-Zahl 1. Art.
OEIS A055154 – Die Formeln sind von dort.
1
1 3 1
1 12 32 35 21 7 1
1 39 321 1225 2919 4977 6431 6435 5005 3003 1365 455 105 15 1
...
Satz
\[c~(n,m)~=~\binom{2^n-1}{m}~~~\text{für}~~~m~\ge~2^{n-1}\]
\[c~(n,m)~\lt~\binom{2^n-1}{m}~~~\text{für}~~~m~\lt~2^{n-1}\]
Dabei ist \(\binom{2^n-1}{m}\) die Anzahl aller möglichen \(M_{(m)}\) mit \(M_i~\neq~\emptyset\) . Das bedeutet: Wählt man mehr als die Hälfte der Teilmengen aus, dann (und nur dann) ergibt sich immer eine Überdeckung.
Beweis
Es gibt genau \(2^{n-1}-1\) nicht-leere Teilmengen, die \(1 \in [n]\) nicht enthalten. Für \(m~\lt~2^{n-1}\) kann es also vorkommen, dass \(M_{(m)}\) keine Überdeckung ist. – Wählt man mehr Teilmengen aus, muss in einer von diesen die \(1\) enthalten sein. Das Gleiche gilt für alle anderen Elemente von \([n]\) .
2. Überdeckende \(M_{(1)}~...~M_{(m)}\) mit \(M_i~\neq~\emptyset\)
\(c~(n,~\le m)\) Anzahl \(j-\)Überdeckungen mit nicht-leeren Teilmengen für alle \(j~\le~m\)
Partial-Zeilensummen der \(c~(n,m)\) in 1.
\[m~\le~2^n-1\]
\[c~(n,~\le m)~=~\sum_{j~=~1}^m~c~(n,j)~=~\sum_{j~=~1}^m~\sum_{i~=~0}^n~(-1)^{n-i}~\binom{n}{i}~\binom{2^i-1}{j}~=~\sum_{i~=~0}^n~(-1)^{n-i}~\binom{n}{i}~\sum_{j~=~1}^m~\binom{2^i-1}{j}\]
" \(j=1\) " kann überall durch " \(j=0\) " ersetzt werden, wenn man (sinnvollerweise) \(c~(n,0)=0\) setzt.
\[c~(n,~\le m)~=~\sum_{j~=~1}^m~\frac{1}{j!}~\sum_{i~=~0}^j~S_{1~}(j+1,~i+1)\cdot (2^i-1)^n\]
mit \(S_1\) Stirling-Zahl 1. Art.
Die Formeln folgen aus 1.
OEIS A369950
1
1 4 5
1 13 45 80 101 108 109
1 40 361 1586 4505 9482 15931 22348 27353 30356 31721 32176 32281 32296 32297
...
3. Überdeckende \(M_{(1)}~...~M_{(2^n-1)}\) mit \(M_i~\neq~\emptyset\)
\(c~(n,~\le 2^n-1)\) Anzahl aller Überdeckungen mit nicht-leeren Teilmengen
Zeilensummen der \(c~(n,m)\) in 1.
Diagonale (rechter Rand der Tabelle) der \(c~(n,~\le m)\) in 2.
\(c~(n,~\le 2^n-1)~=~c_{~\emptyset}~(n,~\le 2^{~n~})~/~2\) siehe 6.
\[c~(n,~\le 2^n-1)~=~\sum_{i~=~0}^n~(-1)^{n-i}\binom{n}{i} \cdot 2^{~2^{~i}-1}\]
Die untere Formel folgt aus 2. mit \(j=0\).
OEIS A003465
1 5 109 32297 2147321017 9223372023970362989 170141183460469231667123699502996689125 ...
4. Überdeckende \(M_{(m)}\)
\(c_{~\emptyset}~(n,m)\) Anzahl \(m-\)Überdeckungen mit max. einer leeren Menge
\[m~\le~2^n\]
\[c_{~\emptyset}~(n,m)~=~c~(n,m)~+~c~(n,m-1)~=~\sum_{i~=~0}^n~(-1)^{n-i}~\binom{n}{i}~\binom{2^{~i}~}{m}\]
mit \(c~(n,2^n)~=~c~(n,0)~=~0\)
Die Formel folgt aus 1.
OEIS A163353
1 1
1 4 4 1
1 13 44 67 56 28 8 1
1 40 360 1546 4144 7896 11408 12866 11440 8008 4368 1820 560 120 16 1
...
Satz
\[c_{~\emptyset}~(n,m)~=~\binom{2^n}{m}~~~\text{für}~~~m~\gt~2^{n-1}\]
\[c_{~\emptyset}~(n,m)~\lt~\binom{2^n}{m}~~~\text{für}~~~m~\le~2^{n-1}\]
Dabei ist \(\binom{2^n}{m}\) die Anzahl aller möglichen \(M_{(m)}\) . Das bedeutet: Wählt man mehr als die Hälfte der Teilmengen aus, dann (und nur dann) ergibt sich immer eine Überdeckung.
Beweis
Es gibt genau \(2^{n-1}\) Teilmengen, die \(1 \in [n]\) nicht enthalten. Für \(m~\le~2^{n-1}\) kann es also vorkommen, dass \(M_{(m)}\) keine Überdeckung ist. – Wählt man mehr Teilmengen aus, muss in einer von diesen die \(1\) enthalten sein. Das Gleiche gilt für alle anderen Elemente von \([n]\) .
5. Überdeckende \(M_{(1)}~...~M_{(m)}\)
\(c_{~\emptyset}~(n,~\le m)\) Anzahl \(j-\)Überdeckungen mit max. einer leeren Menge für alle \(j~\le~m\)
Partial-Zeilensummen der \(c_{~\emptyset}~(n,m)\) in 4.
\[m~\le~2^n\]
\[c_{~\emptyset}~(n,~\le m)~=~\sum_{j~=~1}^m~\sum_{i~=~0}^n~(-1)^{n-i}~\binom{n}{i}~\binom{2^{~i}~}{j}\]
\[c_{~\emptyset}~(n,~\le m)~=~2\cdot~c(n,~\le m-1)~+~c(n,m)\]
mit \(c~(n,2^n)~=~c~(n,0)~=~0\)
Die Formeln folgen aus 4.
OEIS A381683
1 2
1 5 9 10
1 14 58 125 181 209 217 218
1 41 401 1947 6091 13987 25395 38261 49701 57709 62077 63897 64457 64577 64593 64594
...
6. Überdeckende \(M_{(1)}~...~M_{(2^{~n~})}\)
\(c_{~\emptyset}~(n,~\le 2^{~n~})\) Anzahl aller Überdeckungen mit max. einer leeren Menge
Zeilensummen der \(c_{~\emptyset}~(n,m)\) in 4.
Diagonale (rechter Rand der Tabelle) der \(c_{~\emptyset}~(n,~\le m)\) in 5.
\(c_{~\emptyset}~(n,~\le 2^{~n~})~=~2\cdot c~(n,~\le 2^n-1)\) siehe 3.
\[c_{~\emptyset}~(n,~\le 2^{~n~})~=~\sum_{j~=~1}^{2^{~n}}~\sum_{i~=~0}^n~(-1)^{n-i}~\binom{n}{i}~\binom{2^{~i}~}{j}~=~\sum_{i~=~0}^n~(-1)^{n-i}~\binom{n}{i}~2^{~2^{~i}}\]
Die Formel folgt aus 5. mit \(j=0\).
OEIS A000371
2 10 218 64594 4294642034 18446744047940725978 ...
7. Überdeckende \(M_{(m)}\) mit disjunkten \(M_i~\neq~\emptyset\)
\(c_{~\text{disj}}~(n,m)\) Anzahl \(m-\)Überdeckungen mit disjunkten nicht-leeren Teilmengen
\[m~\le~n\]
\(c_{~\text{disj}}~(n,m)~=~S_{2~}(n,m)\)
mit Stirling-Zahl 2. Art:
\[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~S_{2~}(n,m)~=~\frac{1}{m~!}~\sum_{i~=~1}^m~(-1)^{m-i}\binom{m}{i} \cdot i^n\]
OEIS A008277
1
1 1
1 3 1
1 7 6 1
1 15 25 10 1
1 31 90 65 15 1
...
Einschub: Anzahl aller \(M_{(m)}\) mit disjunkten \(M_i~\neq~\emptyset\)
\(m\) Teilmengen decken \(j\) Elemente von \([n]\) disjunkt ab ( \(j = m~..~n\) ) :
\[\sum_{j~=~m}^n~\binom{n}{j}~S_{2~}(j,m)~=~S_{2~}(n+1,m+1)\]
Die Gleichheit der Summe (welche sich direkt aus der Fragestellung ergibt) mit einer einzigen Stirling-Zahl ist eine bekannte Rekursionsformel für \(S_2\) . In OEIS A008277 steht sie unter Formula "Recurrence" von Thomas Wieder. OEIS zeigt auch die Anwendung auf disjunkte Teilmengen, siehe Comments von Geoffrey Critzer.
In der deutschen Wikipedia ist diese Rekursion nicht aufgeführt. Die englische Wikipedia dagegen enthält sie und gibt noch eine weitere Formel an; in MathWorld findet man nur letztere:
\[\sum_{j~=~m}^n~(m+1)^{n-j}~S_{2~}(j,m)~=~S_{2~}(n+1,m+1)\]
Die Tabelle ist naturgemäß in der obigen Tabelle enthalten:
1
3 1
7 6 1
15 25 10 1
31 90 65 15 1
63 301 350 140 21 1
...
8. Überdeckende \(M_{(1)}~...~M_{(m)}\) mit disjunkten \(M_i~\neq~\emptyset\)
\(c_{~\text{disj}}~(n,~\le m)\) Anzahl \(j-\)Überdeckungen mit disjunkten nicht-leeren Teilmengen für alle \(j~\le~m\)
Partial-Zeilensummen der \(c_{~\text{disj}}~(n,m)\) in 7.
\[m~\le~n\]
\[c_{~\text{disj}}~(n,~\le m)~=~\sum_{j~=~1}^m~c_{~\text{disj}}~(n,j)~=~\sum_{j~=~1}^m~S_{2~}(n,j)\]
\(S_2\) Stirling-Zahl 2. Art.
OEIS A102661
1
1 2
1 4 5
1 8 14 15
1 16 41 51 52
1 32 122 187 202 203
...
9. Überdeckende \(M_{(1)}~...~M_{(n)}\) mit disjunkten \(M_i~\neq~\emptyset\)
\(c_{~\text{disj}}~(n,~\le n)\) Anzahl aller disjunkten Überdeckungen mit nicht-leeren Teilmengen
Zeilensummen der \(c_{~\text{disj}}~(n,m)\) in 7.
Diagonale (rechter Rand der Tabelle) der \(c_{~\text{disj}}~(n,~\le m)\) in 8.
\[c_{~\text{disj}}~(n,~\le n)~=~\sum_{j~=~1}^n~c_{~\text{disj}}~(n,j)~=~\sum_{j~=~1}^n~S_{2~}(n,j)~=~B(n)~=~\sum_{j~=~1}^n~\frac{1}{j~!}~\sum_{i~=~1}^j~(-1)^{j-i}~\binom{j}{i}~i^n~=~1+\left \lfloor e^{-1}~\sum_{j~=~1}^{2~n}~\frac{j^{~n}}{j~!}\right \rfloor\]
\(B\) Bell-Zahl. \(S_2\) Stirling-Zahl 2. Art.
OEIS A000110 – Die Formeln sind von dort. Die vorletzte Formel verwendet die Definition der Stirling-Zahl 2. Art aus 7.
1 2 5 15 52 203 203 877 4140 21147 115975 ...
10. Überdeckende \(M_{(m)}\) mit disjunkten \(M_i\)
\(c_{~disj~\emptyset}~(n,m)\) Anzahl \(m-\)Überdeckungen mit disjunkten Teilmengen und max. einer leeren Menge
\[m~\le~n+1\]
\[c_{~disj~\emptyset}~(n,m)~=~c_{~disj}~(n,m)~+~c_{~disj}~(n,m-1)~=~S_{2~}(n,m)~+~S_{2~}(n,m-1)\]
\(S_2\) Stirling-Zahl 2. Art. Die Formel folgt aus 7.
OEIS A256894 \(c_{~disj~\emptyset}~(n,m+1)~=~T(n,m)~\)
1 1
1 2 1
1 4 4 1
1 8 13 7 1
1 16 40 35 11 1
1 32 121 155 80 16 1
1 64 364 651 490 161 22 1
...
Einschub: Anzahl aller \(M_{(m)}\) mit disjunkten \(M_i\)
Aus 7. folgt, dass es \(S_{2~}(n+1,m+1)\) Möglichkeiten gibt, dass \(M_{(m)}\) aus disjunkten \(M_i~\neq~\emptyset\) besteht. Außerdem gibt es \(S_{2~}(n+1,m)\) Möglichkeiten, dass \(M_{(m)}\) aus disjunkten \(M_i\) besteht, von denen eine die leere Menge ist.
Die gesuchte Anzahl beträgt also \(S_{2~}(n+1,m+1)~+~S_{2~}(n+1,m)\).
Die Tabelle ist naturgemäß in der obigen Tabelle enthalten:
2 1
4 4 1
8 13 7 1
16 40 35 11 1
32 121 155 80 16 1
64 364 651 490 161 22 1
...
11. Überdeckende \(M_{(1)}~...~M_{(m)}\) mit disjunkten \(M_i\)
\(c_{~disj~\emptyset}~(n,~\le m)\) Anzahl \(j-\)Überdeckungen mit disjunkten verschiedenen Teilmengen für alle \(j~\le~m\)
Partial-Zeilensummen der \(c_{~disj~\emptyset}~(n,m)\) in 10.
\[m~\le~n+1\]
\[c_{~disj~\emptyset}~(n,~\le m)~=~\sum_{j~=~1}^m~c_{~disj~\emptyset}~(n,j)~=~2\cdot \sum_{j~=~1}^{m-1}~S_{2~}(n,j)~+~S_{2~}(n,m)\]
\(S_2\) Stirling-Zahl 2. Art. Die Formel folgt aus 10.
OEIS A381682
1 2
1 3 4
1 5 9 10
1 9 22 29 30
1 17 57 92 103 104
1 33 154 309 389 405 406
1 65 429 1080 1570 1731 1753 1754
...
12. Überdeckende \(M_{(1)}~...~M_{(n+1)}\) mit disjunkten \(M_i\)
\(c_{~disj~\emptyset}~(n,~\le n+1)\) Anzahl aller disjunkten Überdeckungen mit verschiedenen Teilmengen
Zeilensummen der \(c_{~disj~\emptyset}~(n,m)\) in 10.
Diagonale (rechter Rand der Tabelle) der \(c_{~disj~\emptyset}~(n,~\le m)\) in 11.
\[c_{~disj~\emptyset}~(n,~\le n+1)~=~\sum_{j~=~1}^{n+1}~c_{~disj~\emptyset}~(n,j)~=~2\cdot \sum_{j~=~1}^{n}~S_{2~}(n,j)~=~2\cdot B(n)\]
\(B\) Bell-Zahl. \(S_2\) Stirling-Zahl 2. Art. Die Formel folgt aus 11; siehe auch 9.
OEIS A186021 , und OEIS A000110 verdoppelt
2 4 10 30 104 406 1754 8280 42294 231950 1357140 8427194 ...
Kommentare sind willkommen.
Stand 2024-04-10
Inhalt Blog | voriger Eintrag | nächster Eintrag