MB Matheblog # 40

Inhalt Blog voriger Eintrag

zur Leitseite Index der gesamten Website

Nicht-leere endliche Mengen werden hier der Einfachheit halber als  \([n] = \{1,~...,~n\}\)  dargestellt. Wir betrachten  \(m-\)tupel  \(T_{(m)}~=~(M_1,~...,~M_m)\)  von  \(m\)  Teilmengen  \(M_i\)  von   \([n]\) ,  also  \(T_{(m)}~\in~P([n])^m\) .  Eine solche Menge heißt "geordnete  \(m-\)Überdeckung" oder kürzer "(geordnete) Überdeckung", falls die Vereinigung  \(\bigcup M_i = [n]\)  ist. Die Anzahl solcher geordneten Überdeckungen wird mit  \(h.(n,m)\)  bezeichnet; der Punkt wird ggfs. durch Symbole ersetzt, die für verschiedene Bedingungen an die Überdeckungen stehen. Werden die  \(h.(n,m)\)  tabellarisch dargestellt, steht  \(n\)  für die Zeilen.

Eine Besonderheit geordneter Überdeckungen ist die Darstellung durch binäre Matrizen.

Dieser Beitrag greift die Ausführungen in Blog # 10 wieder auf  –  insbesondere die Matrix-Darstellung  –  und stellt sie in einen allgemeineren Zusammenhang. Blog # 11 zeigt eine Anwendung geordneter Überdeckungen im Quality Management.


1.   Überdeckende  \(T_{(m)}\)  mit  \(M_i~\neq~\emptyset\)

\(h~(n,m)\)  Anzahl geordneter  \(m-\)Überdeckungen mit nicht-leeren Teilmengen \[m~\in~N\] \[h~(n,m)~=~\sum_{j~=~1}^m~(-1)^{m-j}~\binom{m}{j}~(2^j-1)^n\] \(h~(n,m)\)  ist die Anzahl binärer \((n\times m)\)-Matrizen ohne Nullzeilen und ohne Nullspalten.  –  Beweise in Blog # 10.

Symmetrie (siehe Matrixdarstellung):  \(h~(n,m)~=~h~(m,n)\)

OEIS A218695        OEIS A183109 nur Dreieck (ausreichend wegen Symmetrie)

1  1    1     1      1 ...
1  7   25    79    241 ...
1 25  265  2161  16081 ...
1 79 2161 41503 693601 ...
...


2.   Überdeckende  \(T_{(m)}\)

\(h_{~\emptyset}~(n,m)\)  Anzahl geordneter  \(m-\)Überdeckungen (\(M_i\)  dürfen leer sein) \[m~\in~N\] \[h_{~\emptyset}~(n,m)~=~(2^m-1)^n\] \(h_{~\emptyset}~(n,m)\)  ist die Anzahl binärer \((n\times m)\)-Matrizen ohne Nullzeilen, daher ist der Beweis offensichtlich.

OEIS A329943 unschön, da transponiert       OEIS A092477 unzureichend, nur Dreieck

1  3    7    15     31 ...
1  9   49   225    961 ...
1 27  343  3375  29791 ...
1 81 2401 50625 923521 ...
...


3.   Überdeckende  \(T_{(m)}\)  mit  \(M_i~\neq~\emptyset\)  paarweise verschieden

\(h_{~\text{diff}}~(n,m)\)  Anzahl geordneter  \(m-\)Überdeckungen mit paarweise verschiedenen nicht-leeren Teilmengen \[m~\le~2^n-1\] \[h_{~\text{diff}}~(n,m)~=~\sum_{i~=~0}^n~(-1)^{n-i}~\binom{n}{i}~\frac{(2^i-1)!}{(2^i-1-m)!}~=~\sum_{j~=~0}^m~S_1(m+1,~j+1)~(2^j-1)^n\]                        \(=~m!~c(n,m)\)   siehe Blog # 39, Abschnitt 1;  \(S_1\) Stirling-Zahl 1. Art

\(h_{~\text{diff}}~(n,m)\)  ist die Anzahl binärer \((n\times m)\)-Matrizen ohne Nullzeilen und ohne Nullspalten, mit paarweise verschiedenen Spalten.

keine OEIS-Folge

1
1  6   6
1 24 192 840 2520 5040 5040
...

Satz \[h_{~\text{diff}}~(n,m)~=~\frac{(2^n-1)!}{(2^n-1-m)!}~~~\text{für}~~~m~\ge~2^{n-1}\] \[h_{~\text{diff}}~(n,m)~\lt~\frac{(2^n-1)!}{(2^n-1-m)!}~~~\text{für}~~~m~\lt~2^{n-1}\] Dabei ist  \((2^n-1)!~/~(2^n-1-m)!\)  die Anzahl aller möglichen  \(T_{(m)}\)  mit  \(M_i~\neq~\emptyset\)  paarweise verschieden.  Das bedeutet: Wählt man mehr als die Hälfte der Teilmengen aus, dann (und nur dann) ergibt sich immer eine Überdeckung.  –  Beweis wie in Blog # 39, Abschnitt 1.


4.   Überdeckende  \(T_{(m)}\)  mit  \(M_i\)  paarweise verschieden

\(h_{~\text{diff},~\emptyset}~(n,m)\)  Anzahl geordneter  \(m-\)Überdeckungen mit paarweise verschiedenen Teilmengen (es kann also keine oder genau eine leere Menge in  \(T_{(m)}\)  enthalten sein) \[m~\le~2^n\] \[h_{~\text{diff},~\emptyset}~(n,m)~=~\sum_{i~=~0}^n~(-1)^{n-i}~\binom{n}{i}~\frac{2^{i~}!}{(2^i-m)!}\]                        \(=~m!~c_{~\emptyset}(n,m)\)   siehe Blog # 39, Abschnitt 4

\(h_{~\text{diff},~\emptyset}~(n,m)\)  ist die Anzahl binärer \((n\times m)\)-Matrizen ohne Nullzeilen mit paarweise verschiedenen Spalten.

keine OEIS-Folge

1  2
1  8  24   24
1 26 264 1608 6720 20160 40320 40320
...

Satz \[h_{~\text{diff},~\emptyset}~(n,m)~=~\frac{(2^n)!}{(2^n-m)!}~~~\text{für}~~~m~\gt~2^{n-1}\] \[h_{~\text{diff},~\emptyset}~(n,m)~\lt~\frac{(2^n)!}{(2^n-m)!}~~~\text{für}~~~m~\le~2^{n-1}\] Dabei ist  \((2^n)!~/~(2^n-m)!\)  die Anzahl aller möglichen  \(T_{(m)}\)  mit  \(M_i\)  paarweise verschieden.  Das bedeutet: Wählt man mehr als die Hälfte der Teilmengen aus, dann (und nur dann) ergibt sich immer eine Überdeckung.  –  Beweis wie in Blog # 39, Abschnitt 4.


5.   Überdeckende  \(T_{(m)}\)  mit disjunkten  \(M_i~\neq~\emptyset\)

\(h_{~\text{disj}}~(n,m)\)  Anzahl  \(m-\)Überdeckungen mit disjunkten nicht-leeren Teilmengen \[m~\le~n\] \(h_{~\text{disj}}~(n,m)~=~m!~c_{~\text{disj}}~(n,m)~=~m!~S_{2~}(n,m)\)   siehe Blog # 39, Abschnitt 7;  \(S_2\) Stirling-Zahl 2. Art

\(h_{~\text{disj}}~(n,m)\)  ist die Anzahl binärer \((n\times m)\)-Matrizen mit Zeilensummen  \(1\)  und ohne Nullspalten.

OEIS A019538

1
1   2
1   6     6
1  14    36     24
1  30   150    240    120
1  62   540   1560   1800     720
1 126  1806   8400  16800   15120    5040
1 254  5796  40824 126000  191520  141120   40320
1 510 18150 186480 834120 1905120 2328480 1451520 362880
...


6.   Überdeckende  \(T_{(m)}\)  mit disjunkten  \(M_i\)

\(h_{~\text{disj},~\emptyset}~(n,m)\)  Anzahl  \(m-\)Überdeckungen mit disjunkten Teilmengen (es können also beliebig viele leere Mengen in  \(T_{(m)}\)  enthalten sein) \[m~\in~N\] \(h_{~\text{disj},~\emptyset}~(n,m)~=~m^n\)

\(h_{~\text{disj},~\emptyset}~(n,m)\)  ist die Anzahl binärer \((n\times m)\)-Matrizen mit Zeilensummen  \(1\) .

OEIS A089072 unzureichend, nur Dreieck

1  2   3    4    5    6     7
1  4   9   16   25   36    49
1  8  27   64  125  216   343
1 16  81  256  625 1296  2401
1 32 243 1024 3125 7776 16807
...


7.   Überdeckende  \(T_{(m)}\)  mit disjunkten und verschiedenen  \(M_i\)

\(h_{~\text{disj},~\text{diff}}~(n,m)\)  Anzahl  \(m-\)Überdeckungen mit disjunkten Teilmengen, von denen maximal eine leer sein darf \[m~\le~n+1\] \(h_{~\text{disj},~\text{diff}}~(n,m)~=~h_{~\text{disj}}~(n,m)~+~m\cdot h_{~\text{disj}}~(n,m-1)~=~m!~S_{2~}(n,m)~+~m!~S_{2~}(n,m-1)\)

      mit \(S_2\) Stirling-Zahl 2. Art

\(h_{~\text{disj},~\text{diff}}~(n,m)\)  ist die Anzahl binärer \((n\times m)\)-Matrizen mit Zeilensummen  \(1\)  und maximal einer Nullspalte.

keine OEIS-Folge, aber  \(=~m!\cdot T(n,m-1)\)_OEIS A256894

1   2
1   4    6
1   8   24    24
1  16   78   168   120
1  32  240   840  1320    720
1  64  726  3720  9600  11520   5040
1 128 2184 15624 58800 115920 110880 40320
...

Stand 2024-05-28

Inhalt Blog   |    voriger Eintrag

Manfred Börgens   |   Zur Leitseite