TU Wien:Diskrete Mathematik für Informatik UE (Drmota)/Übungen WS10/Beispiel 10

Nach einsetzten erhält man

$s_{n,n-1}=s_{n-1,n-2}+(n-1)*s_{n-1,n-1}$

und

$S_{n,n-1}=S_{n-1,n-2}+(n-1)*S_{n-1,n-1}$

da s und S die selben Anfangsbedingungen haben muss $S_{n,n-1}=s_{n,n-1}$

$S_{x,x}=1$

$S_{n,n-1}=S_{n-1,n-2}+(n-1)*S_{n-1,n-1}$

$S_{n,n-1}=S_{n-1,n-2}+(n-1)$

$S_{n,n-1}=\sum _{j=1}^{n-1}j={\frac {n*(n-1)}{2}}={\binom {n}{2}}$

Alternative Lösung

Nachdem "begründen Sie" dortsteht habe ich es eher mit kombinatorischer Interpretation zu begründen versucht:

$s_{n,n-1}$ ist die Anzahl der Permutationen die in n-1 Zyklen zerfallen. Dh. es gibt genau einen Zyklus der 2 Elemente hat. Das ist aber das selbe wie 2 Elemente aus einer n Elementigen Menge auszuwählen, also ${\binom {n}{2}}$

$S_{n,n-1}$ ist die Anzahl der Zerlegungen in k Teile. Genau eine Zerlegung muss 2 Teile haben -> wieder ist es das selbe wie 2 Elemente aus einer n Elementigen Menge auszuwählen, also ${\binom {n}{2}}$. q.e.d.