Beweis mit kombinatorischem Argument, Stirling-Zahlen zweiter Art

Question

Aufgabe:

Beweisen Sie mit einem kombinatorischen Argument, dass für alle n ∈ N gilt:

a) Sn,n−1 = ( n über 2 )

b) Sn,2 = 2^n−1 − 1

Sn,k soll Stirling-Zahlen zweiter Art sein

Ich verstehe die Stirling Zahlen auch nach Wikipedia und Co. nicht.

Answer 1

⇒Die Stirling-Zahlen zweiter Art geben die Anzahl Möglichkeiten n Elemente in k nichtleere Teilmengen zu verteilen (geschrieben S(n,k))

Ein Beispiel wäre auf wie viele verschiedene Wege kann ich 6 Kühe auf 3 Gehege verteilen S(6,3)

Die explizite Formel für S(6,3) lautet

$$ S(6, 3)=\frac{1}{3 !} \sum \limits_{i=0}^{3}(-1)^{i}\left(\begin{array}{c}{3} \\ {i}\end{array}\right)(3-i)^{6} =90$$

Es gibt also 90 verschiedene Wege 6 Kühe in 3 Gehege zu verteilen.

a)

S(n,n-1) bedeutet n elemente in n-1 Teilmengen zu verteilen was wiederum bedeutet, dass n-2 Teilmengen jeweils nur 1 Element enthalten und eine Teilmenge 2 Elemente enthält wir müssen also nur diese 2 Elemente auswhälen ⇒ $$\begin{pmatrix} n\\2 \end{pmatrix}$$