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!