2025-05-15
Paare von Teilmengen Kommentare sind willkommen.
M sei eine nicht-leere Menge mit |M| = n Elementen. P(M) sei die Potenzmenge von M mit |P(M)| = 2n Elementen. A, B seien Teilmengen von M , also (A,B) ∈ (P(M))2.
Ist A Teilmenge von B , so schreiben wir A ⊆ B .
Ist A echte Teilmenge von B , so schreiben wir A ⊂ B .
(A,B) lässt sich darstellen als (2×n)-Schema. Zunächst schreibt man M = {m1, m2, ... , mn} . C ⊆ M ist eindeutig definiert durch das n-Tupel c ∈ {0,1}n mit ci = 1 ⇔ mi ∈ C .
Ist z.B. n = 5 , so steht das (2×n)-Schema
A 1 1 0 1 1
B 0 1 0 0 1
für A = {m1, m2, m4, m5} und B = {m2, m5} . – Es gibt 22n Möglichkeiten für ein solches Schema, also ebensoviele Auswahlen für (A,B) .
Im Folgenden soll die Anzahl m.,n der (A,B) angegeben werden, für die eine bestimmte Teilmengenbeziehung (von insgesamt acht möglichen) besteht. Diese Anzahlen wurden teilweise bereits in Problem # 71 bestimmt.
I. Wieviele Paare (A,B) mit A ⊆ B gibt es?
(2×n)-Schema: In den Spalten darf nicht eine 0 über einer 1 stehen, also bleiben noch 3 Möglichkeiten für die Ausfüllung jeder Spalte.
mI,n = 3n
OEIS: A000244
Wahrscheinlichkeit bei zufälliger Auswahl der A, B : pI,n = 3n/22n
II. Wieviele Paare (A,B) mit A ⊂ B gibt es?
(2×n)-Schema: Von den 3n Paaren in I. scheiden diejenigen aus, bei denen die beiden Zeilen im Schema identisch sind; deren Anzahl beträgt 2n .
mII,n = 3n - 2n
OEIS: A001047
Wahrscheinlichkeit bei zufälliger Auswahl der A, B : pII,n = (3n - 2n)/22n
III. Wieviele Paare (A,B) mit A ≠ Ø, B ≠ Ø und A ⊆ B gibt es?
(2×n)-Schema: Von den 3n Paaren in I. scheiden diejenigen aus, bei denen die obere Zeile nur aus Nullen besteht; deren Anzahl beträgt 2n .
mIII,n = 3n - 2n
OEIS: A001047
Wahrscheinlichkeit bei zufälliger Auswahl der A, B aus den nichtleeren Teilmengen: pIII,n = (3n - 2n)/(2n - 1)2
IV. Wieviele Paare (A,B) mit A ≠ Ø, B ≠ Ø und A ⊂ B gibt es?
(2×n)-Schema: Von den 3n Paaren in I. scheiden zunächst diejenigen aus, bei denen die beiden Zeilen im Schema identisch sind; deren Anzahl beträgt 2n. Außerdem scheiden diejenigen aus, bei denen die obere Zeile nur aus Nullen besteht, die untere aber nicht; deren Anzahl beträgt 2n - 1 .
mIV,n = 3n - 2n+1 + 1
OEIS: a(n+1) in A028243
Wahrscheinlichkeit bei zufälliger Auswahl der A, B aus den nichtleeren Teilmengen: pIV,n = (3n - 2n+1 + 1)/(2n - 1)2
V. Wieviele Paare (A,B) mit A ⊆ B oder B ⊆ A gibt es?
(2×n)-Schema: Wir verdoppeln zunächst die 3n Paare in I. ; diejenigen davon, bei denen die beiden Zeilen im Schema identisch sind, wurden dabei doppelt gezählt; deren Anzahl 2n ist somit zu subtrahieren.
mV,n = 2·3n - 2n
OEIS: A027649
Wahrscheinlichkeit bei zufälliger Auswahl der A, B : pV,n = (2·3n - 2n)/22n
VI. Wieviele Paare (A,B) mit A ⊂ B oder B ⊂ A gibt es?
(2×n)-Schema: Die Anzahl der Paare in II. ist zu verdoppeln.
mVI,n = 2·(3n - 2n)
OEIS: A056182
Wahrscheinlichkeit bei zufälliger Auswahl der A, B : pVI,n = (3n - 2n)/22n-1
VII. Wieviele Paare (A,B) mit A ⊆ B oder B ⊆ A gibt es, falls A ≠ Ø, B ≠ Ø ?
(2×n)-Schema: Wir verdoppeln die in III. gefundenen Möglichkeiten und subtrahieren davon 2n - 1 für die Fälle A = B ≠ Ø , da diese doppelt gerechnet wurden.
mVII,n = 2·3n - 3·2n + 1
OEIS: A091344
Wahrscheinlichkeit bei zufälliger Auswahl der A, B aus den nichtleeren Teilmengen: pVII,n = (2·3n - 3·2n + 1)/(2n - 1)2
VIII. Wieviele Paare (A,B) mit A ⊂ B oder B ⊂ A gibt es, falls A ≠ Ø, B ≠ Ø ?
(2×n)-Schema: Die Anzahl der Paare in IV. ist zu verdoppeln.
mVIII,n = 2·(3n - 2n+1 + 1)
OEIS: a(n+1) in A260217
Wahrscheinlichkeit bei zufälliger Auswahl der A, B aus den nichtleeren Teilmengen: pVIII,n = 2·(3n - 2n+1 + 1)/(2n - 1)2
Stand 2023-03-30
Inhalt Blog | voriger Eintrag
Manfred Börgens | Zur Leitseite
MB Matheblog # 41