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)\ast s_{n-1,n-1}$

und

$S_{n,n-1}=S_{n-1,n-2}+(n-1)\ast 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)\ast 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\ast (n-1)}{2}=(\genfrac{}{}{0ex}{}{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 $(\genfrac{}{}{0ex}{}{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 $(\genfrac{}{}{0ex}{}{n}{2})$. q.e.d.