Zeige das |A_k|= k! (Permutation)

Question

hey Leute, könnt ihr mir schnell mal helfen.

Aufgabe : Zeige das |A_k | = k!

danke für eure Hilfe.

Comments

Was ist \(A_k\)? Die Menge aller Permutationen einer \(k\)-elementigen Menge?

---

ja A ist die Menge aller Permutationen einer k-elementigen Menge

Answer 1

Für \(A_1\) gilt offensichtlich \(\#A_1 = 1 = 1!\). Sei nun \(\#A_{k-1} = (k-1)!\). Es enthält nun \(A_k\) alle Permutationen (Anordnungen) von \(k\) Elementen. Die Idee ist: Setze das erste Element fest. Dann können noch die restlichen \(k-1\) Elemente angeordnet werden, dafür gibt es per Induktionsvoraussetzung \( (k-1)! \) Möglichkeiten und wir haben insgesamt \(k\) verschiedene Möglichkeiten, das erste Element festzulegen, also insgesamt \(k\cdot (k-1)! = k!\) Anordnungen. Formal geht das wie folgt, dabei sei die Menge, auf der permutiert wird o.B.d.A \( M=\{1,\dots,k\} \) und eine Permutation wird in der Form \( (m_1, \dots, m_k) \) notiert, wobei stets gilt \( \bigcup_{i=1}^{k} m_i = M\). Man kann nun die Menge \(A_k\) umschreiben:

$$ A_k = \{ (m_1,\dots, m_k) :  \bigcup_{i=1}^{k} m_i = M \} = \dot{\bigcup}_{j=1}^{k} \underset{=:A'_{j}}{\underbrace{   \{ (m_1,\dots,m_k): m_1 = j~\text{und}~ \bigcup_{i=1}^{k} m_i = M \}   }}$$

Nach Induktionsvoraussetzung ist \( \#A'_j = (k-1)! \) und da die letzte Vereinigung disjunkt ist, erhält man insgesamt

$$ \# A_k = \sum_{j=1}^{k} \#A'_j  =  \sum_{j=1}^{k} (k-1)! = k\cdot (k-1)! = k! $$

Answer 2

zeigst du am besten durch Induktion über k.

k=1 ist wohl klar

gilt es für k, so kannst du dir nei einer k+1 elementigen Menge, einfach ein Element x
herausnehmen und jetzt eine k-elementige Menge, die also k! Permutationen besitzt.

Bei jeder dieser Permutationen kannst du das x entweder vor dem ersten Element,
oder zwischen dem ersten und dem zweiten oder zwischen dem zweiten
und dem dritten etc..  oder hinter dem letzten einfügen.
Du hast also k+1 Stellen, wo das x hin kann, also gibt es aus jeder
der alten Permutationen k+1 Permutationen mit dem Element x,
also insgesamt k! * (k+1) = (k+1) !

Comments

also wenn wir die Menge A aller Permutationen von { a₁ , ... , a_n+1 }. Für k = 1,...,n+1 sei A_k die Menge mit der a_k beginnenden Permutationen. Es ist also |A| = |A₁ | + |A₂ | + |A_n+1 |

nun besteht A_k aus diejenigen Anordnungen, die a_k an der erstem stelle haben, gefolgt von einer Anordnung der n Elemente  a₁ , ...,a_k , ..a_n+1

Also ist |A_k | = k! für jedes k und somit |A| = (k+1) * k! = (k+1)! und somit ist gezeigt |A_k | = k!