Kombinatorisches Argument durch doppeltes Abzählen bei Stirlingzahlen

Question

Beweisen Sie mit einem kombinatorischen Argument, dass:

a) \( S_{n, n-1}=\left(\begin{array}{c}n \\ 2\end{array}\right) \)

b) \( S_{n, 2}=2^{n-1}-1 \)

(Bei S n,k handelt es sich um die Stirling-Zahlen zweiter Art.)

Answer 1

S_n,n-1 ist eine n-elemintige Menge ,die auf (n-1) nichtleere Mengen verteilt wird

=> man verteilt n Elemente auf (n-1) Menge => (n ueber n-1)

=> man verteilt  das Übrige Elemente (n-(n-1) =1) auf die (n-1) Teilmengen => (n-1  über 1)

=>Sn,n-1 = (n ueber n-1) . (n-1 ueber 1) = (n ueber 1) . (n-1 ueber n-2 ) =

n!/((n-1)! . 1!)  . (n-1)!/((n-1)- (n-2))! .(n-2)!  = n!/ 1! .(n-2)! = n!/(n-2)!

darausfolgt eine teilmenge mit zwei Elementen sind identisch

Ordnung ist nicht wichtig

Es gibt 2! Möglichkeiten zwei Elemente anzuordnen

=> n!/((n-2)! .2! )  = (n ueber 2)

b)

S_n,_{2 = 2}^n-1 -1

Es werden n verscheidbare Elemente  in 2 nicht geordnete Teilmengen aufgeteilt .wobei in jedermindestens ein Element enthalten sein muss . Man betrachte die Zugehörigkeit des Element zu einer beliebigen der beiden teiilmengen und sagt ,dass sie nicht bei zugehörigkeit zur anderen gehört .

=> n-Elemente  können zu K1 gehörern  und wenn nicht dann zu K2

Annhame : k-Teilmengen geordnent => Ziehen mit zurücklegen geordnent  => N = 2ⁿ  Möglichkeiten .

Es gibt 2 Fälle ,die man nicht zählen darf

- k1 darf nicht leere Menge sein also nicht  k1={empty set }

=> Ziehen non 1 möglichkeiten

-k1 darf nicht wie N sein  also nicht die gleiche Menge wie N => ziehen  von nooh 1 Möglichkeiten  => N=2ⁿ -2

und  weil die Teilmengen ungeordnet sind  => (2n -2)/2!   = 2^n-1 -1