Aufgabe:
Wir nennen eine Permutation \( \sigma=a_{1} \ldots a_{n} \in S_{n} \) unzerlegbar, falls \( a_{l}, \ldots a_{j} \neq[j] \quad \forall j<n . \) Sei \( f(n) \) die Anzahl der unzerlegbaren Permutationen in \( S_{n} \).
Zeigen Sie:
i) \( \sum \limits_{j=1}^{n} f(j)(n-j) !^{\prime}=n ! \) für \( n \geq 1 \)
ii) \( \left(\sum \limits_{n \geq=1} f(n) t^{n}\right)\left(\sum \limits_{n \geq=0} n ! t^{n}\right)=\left(\sum \limits_{n \geq=1} n ! t^{n}\right)-1 \)
Ansatz/Problem:
Ich habe es mit Induktion versucht aber ich bin nicht weiter gekommen.
