Stirling-Zahlen zweiter Art. Beweis mit kombinatorischen Argumenten

Question

Aufgabe:

Beweisen Sie mit kombinatorischen Argumenten, dass:

S_n,2 = 2^n-1 −1

Hinweis: Bei S_n,k handelt es sich um die Stirling-Zahlen zweiter Art.

Problem:

Ich habe leider keine Ahnung wie ich an diese Aufgabe rangehen soll. Ich hoffe es kann mir jemand helfen und schon mal

Answer 1

Ansatz:

bei Wikipedia nach schauen

https://de.m.wikipedia.org/wiki/Stirling-Zahl

Da steht eig. schon die Lösung.

Answer 2

Ich hoffe die Erklärung ist halbwegs verständlich:

Also... wir wollen n Elemente auf zwei Schubfächer verteilen. Diese Schubfächer sind nicht nummeriert oder sonstiges...

Es interessieren uns also nur die möglichen Kombinationen in einem Schubfach. Da das andere Schubfach aber nicht leer sein kann, gibt es nur n-1 Elemente die wir in dieses Schubfach packen können. Für jedes dieser Elemente gibt es 2 Optionen, entweder es ist in unseren Schubfach, oder nicht ... 2^n-1 .

Zum Schluss schließen wir noch aus, dass keines der n-1 Elemente in unserem Schubfach landet, indem wir diese Möglichkeit von allen möglichen Kombinationen abziehen... 2^n-1-1

q.e.d.