Aufgabe:
Es gilt
\( \left(\begin{array}{l} n \\ k \end{array}\right)=\frac{n^{\underline{k}}}{k !} . \)
Beweis. Induktionsanfang: \( \left(\begin{array}{l}n \\ 0\end{array}\right)=1 \) für \( n \geq 0 \).
Angenommen, \( \left(\begin{array}{c}n-1 \\ k-1\end{array}\right)=\frac{(n-1) \leq-1}{(k-1) !} \).
Es gibt \( n \) Möglichkeiten, das erste Element e zu wählen.
Es gibt \( \left(\begin{array}{c}n-1 \\ k-1\end{array}\right) \) Möglichkeiten, Menge \( S \) der restlichen \( k-1 \) Elemente zu wählen.
Es gibt \( k \) Möglichkeiten, \( S \cup\{e\} \) zu bilden: Tausche e mit \( f \in S \) Insgesamt:
\( n \cdot\left(\begin{array}{l} n-1 \\ k-1 \end{array}\right) / k=\frac{n \cdot(n-1) \frac{k-1}{2}}{k \cdot(k-1) !}=\frac{n \underline{k}}{k !} \)
Problem/Ansatz:
ich verstehe den Beweis einfach nicht. Was ist hier die Induktionsvoraussetzung was der Induktionsschritt und was macht man dann? Ich bitte um ausführliche Antwort
