Induktion in Kombination mit Permutation

Question

Aufgabe:

(a) Permutation: Zeige mit vollständiger Induktion nach \( n \), dass es genau \( n \) ! Möglichkeiten gibt, die Zahlen \( 1,2,3, \ldots n \) anzuordnen (Reihenfolge wird berücksichtigt, ohne Wiederholungen).
Anleitung: Argumentiere im Induktionsschritt, wie viele neue Anordnungen dazukommen, wenn zu den Zahlen \( 1,2,3, \ldots n \) die nächste Zahl \( n+1 \) dazu kommt.

Problem/Ansatz:

Wie genau kann man das mit Induktion lösen, den Induktionsstart hab ich bereits gemacht mit 1 = 1! -> korrekt

Answer 1

Wir nehmen also an, dass wir die Zahlen \( 1,2, \ldots, n \) in \( n \) ! verschiedenen Weisen ordnen können. Für den Induktionsschritt betrachten wir nun also jetzt die Anzahl an Möglichkeiten, die Zahlen \( 1,2, \ldots, n+1 \) zu Ordnen, bezeichne diese mit \( f(n+1) \). Diese setzt sich aus \( n+1 \) verschiedenen Ereignissen zusammen, welche alle disjunkt sind: Zuerst die Anzahl an möglichen Ordnungen, wenn die Zahl \( n+1 \) immer an der ersten Stelle ist. Das bedeutet, wir fixieren \( n+1 \) und permutieren lediglich die restlichen Zahlen \( 1,2, \ldots, n \), und das geht ja nach Induktionsannahme in \( n \) ! verschiedenen Wegen. Nun setzen wir \( n+1 \) and die zweite Stelle und permutieren wieder die anderen Zahlen in \( n \) ! möglichen Wegen. Da es \( n+1 \) verschiedene Stellen gibt, an welchen wir die Zahl \( n+1 \) platzieren können, erhalten wir also
\( f(n+1)=(n+1) n !=(n+1) ! \)