Potenzmenge und Partitionen

Anzahl der Elemente der Potenzmenge

Die Potenzmenge P(M) einer Menge M ist die Menge, die alle Teilmengen der Menge als ihre Elemente enthält, einschließlich der leeren Menge und der Menge M.

Hat eine Menge M genau n Elemente, so ist die Anzahl der Elemente der Potenzmenge |P(M)| = 2ⁿ.

Beispiele:

M = {1, 2, 3}

P(M) = {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}, |P(M)| = 2³ = 8

M = {a, b, c, d}

P(M) = {{}, {a}, {b}, {c}, {d}, {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}}, |P(M)| = 2⁴ = 16

Anzahl der Partitionen einer Menge

Die Anzahl der Möglichkeiten, eine Menge M mit n Elementen zu partitionieren (zerlegen), wird durch die n-te Bell-Zahl (B_n) bestimmt. Sie gibt an, wie viele verschiedene Möglichkeiten es gibt, eine Menge in nicht-leere, paarweise verschiedene Teilmengen zu zerlegen, deren Vereinigung die Menge M ergibt.

Beispiel:

5 Partitionen der Menge M = {1, 2, 3}:

{{{1}, {2}, {3}}, {{1, 3}, {2}}, {{1}, {2, 3}}, {{1, 2}, {3}}, {{1, 2, 3}}}

Tabelle der Partitionen B_n der n-Menge M,  n ∊{1,2, ... 9}

Die Partitionen B_n können mit Hilfe der Bell-Zahl bestimmt werden.

Berechnung der Bell-Zahlen durch Rekursion:

Dobiński-Formel (1877) zur Berechnung der Bell-Zahl:

Anzahl der Partitionen einer Zahl n

Die Partitionsfunktion P(n) gibt die Anzahl der Möglichkeiten an, eine natürliche Zahl n in positive natürliche Summanden zu zerlegen. Die Reihenfolge der Summanden wird nicht berücksichtigt. Die Summanden werden meist der Größe nach geordnet.

Beispiel:

7 Partitionen der Zahl 5:

(1+1+1+1+1), (1+1+1+2), (1+2+2), (1+1+3), (2+3), (1+4), (5)

Tabelle der Partitionsfunktion P(n) der Zahl n

Python-Programm dazu:

# Anzahl der Partitionen einer Zahl n

def p(n):

    partitions = [1] + [0] * n

    for i in range(1, n + 1):

        for j in range(i, n + 1):

            partitions[j] += partitions[j - i]

    return partitions[n]

n = 15

for i in range(n):

    print i,p(i)

Folgende Kongruenzen (Beziehungen) gehen auf den indischen Mathematiker S. Ramanujan (1887 – 1920) zurück:

P(5m + 4) ≡ 0 mod 5  (bedeutet: „Die Division von P(5m + 4) durch 5 geht auf, d.h. Rest 0.“)

P(7m + 5) ≡ 0 mod 7

P(11m + 6) ≡ 0 mod 11

Tabelle für P(5m + 4):

Anzahl der k-Partitionen einer Zahl n

Die Funktion P(n,k), k ≤ n,  gibt die Anzahl der Möglichkeiten an, eine natürliche Zahl n in positive ganze k Summanden zu zerlegen. Die Reihenfolge der Summanden wird nicht berücksichtigt. Die Summanden werden meist der Größe nach geordnet.
P(n,k) = 0 für k > n.

Beispiel:

Es gibt 4 Partitionen für 7 in 3 Teile:

(1+1+5), (1+2+4), (1+3+3), (2+2+3)

Tabelle für die Anzahl der Partitionen P(n, k) von n in k Summanden:

Es gilt folgende Rekursionsformel:

P(n,k) = P(n–k,k) + P(n–1,k–1)

Beispiele:

P(8,3) = P(5,3) + P(7,2)

      5     =     2        +    3

P(8,5) = P(3,5) + P(7,4)

   3      =     0    +    3