zu zeigen S(n,2) = 2^(n−1) − 1 für n ≥ 2 ohne Rekursionsformel

Question

Aufgabe:

Zeigen Sie: Für alle natürliche Zahlen n ≥ 2 gilt
S(n,2) = 2^(n−1) − 1

Problem/Ansatz:

Das Problem dabei ist, dass ich die Rekursionsformel für die Stirlingzahlen zweiter Art nicht verwenden darf und wir auch sonst keine Formel für die Stirlingzahlen eingeführt haben die ich für eine Induktion verwenden könnte. Laut Tutor muss man eine Induktion machen um das zu beweisen. Ich weiß einfach nicht wo ich da ansetzen kann um diese Formel ohne Rekursionsformel zu beweisen. Ich weiß nur, dass das die Anzahl möglicher 2-Mengen Partitionen ist.

Comments

Hallo,

ob man da eine Induktion machen muss / soll, hängt davon ab, ob Ihr wisst, wieviele Teilmengen eine Menge mit n Elementen hat, das sind 2^n. Daraus folgt die angegeben Formel direkt.

Gruß Mathhilf

---

Also ich weiß dass (n über 2) die Mächtigkeit der 2-elementigen Teilmengen ist wenn es n Elemente in der Ursprünglichen Menge gibt.

---

Die Frage war, ob Ihr wisst, dass die Anzahl aller Teilmengen eine Menge mit n-Elementen gleich 2^n ist.

Wenn Ihr einen Induktionsbeweis machen sollt, brauchst Du doch nur den Induktionsbeweis für die Rekursionsformel auf den Fall von 2er-Partitionen spezialisieren, also vereinfachen.

Gruß Mathhilf

---

Ja ich weiß dass die Anzahl aller Teilmengen einer Menge mit n-Elementen gleich 2^n ist. Die Rekursionsformel darf ich im Beweis nicht verwenden, da diese noch nicht eingeführt wurde. Wie komme ich jetzt von der Anzahl aller Teilmengen 2^n auf die angegebene Formel S(n,2) = 2^(n-1) - 1

Answer 1

Wie komme ich jetzt von der Anzahl aller Teilmengen 2n auf die angegebene Formel

So: Jede Teilmenge A der Grundmenge M liefert eine 2er-Partition: \(\{A,M \setminus A\}\). Macht \(2^n\)

ABER: Der Fall \(A= \emptyset\) und der Fall \(A=M\) liefert keine Partition, also \(2^n-2\)

ABER: Wir haben jede Partition doppelt gezählt, nämlich als : \(\{A,M \setminus A\}\) und  \(\{M \setminus A,A\}\), also

\(\frac{1}{2}(2^n-1)\)

Gruß Mathhilf

Comments

Vielen Dank schon mal. War sehr hilfreich! Aber muss in der letzten Klammer nicht (2^n - 2) stehen damit ich am Ende durch multiplizieren mit 1/2 auf 2^(n-1) -1 komme?

---

Ja, das ist ein Druckfehler