Zeigen Sei: Es gibt n! Permutationen von M.

Question

Aufgabe:

Text erkannt:

Aufgabe \( 6(3+4+3 \) Punkte). Sei \( M \) eine endliche Menge mit \( n \) Elementen. Eine Permutation von \( M \) ist eine Bijektion von \( M \) nach \( M \). Zeigen Sei:
(a) Es gibt \( n \) ! Permutationen von \( M \).
Hinweis: Überlegen Sie sich zunächst, dass jede Permutation genau einer Anordnung der Elemente von \( M \) entspricht.
(b) Die Anzahl der \( k \)-elementigen Teilmengen von \( M \) ist \( \left(\begin{array}{l}n \\ k\end{array}\right) \).
(c) Es gilt \( |\operatorname{Pot}(M)|=2^{n} \), wobei \( \operatorname{Pot}(M):=\{A \mid A \subseteq M\} \) (vgl. Präsenzübung). Hinweis: \( 2=1+1 \).

Comments

Hello, betrachte ein Element M1. Für dieses gibt es die Elemente M1,....,Mn, auf die es abbilden kann. Also n Möglichkeiten für M2 gibt es die Elemente M1,...,Mi-1,Mi+1,...Mn auf die M2 abbilden kann also n-1 Möglichkeiten (weil injektiv). Dies geht soweit bis zu Mn für das nur noch eine Möglichkeit offen bleibt. Damit gibt es aber insgesamt n(n-1)....1 Möglichkeiten eine Bijektion zu konstruieren.

---

b) Wir betrachten {A⊂{m1,...,mn} | card A =k} und {(w1,...,wn) ∈ {m1,...,mn}^n | wi≠wj mit i≠j}. Die zweite Menge ist gerade die Menge, die die Permutationen aus i) beschreibt und damit n! groß ist.

Wir betrachten φ: {(w1,...,wn) ∈ {m1,...,mn}^n | wi≠wj mit i≠j} -> {A⊂{m1,...,mn} | card A =k} mit (w1,...,wn) -> {m1,...,mk}

φ ist surjektiv, aber natürlich nicht injektiv, denn ab wk+1 bis wn spielen die Elemente keine Rolle mehr. Für wk+1 hast du noch (n-k) Elemente zur Auswahl. Für wk+2 noch (n-k-1) ... und für wn nur noch 1 Element zur Auswahl -> Es könne maximal n! / (n-k)! k-elementige Teilmengen geben.

aber (w1,...,wk,......,wm) bildet auf das gleiche ab wie z.B. (wk,....,w1, wk+1,...,wn). Das heißt die Reihenfolge von (w1,...,wk) ist auch nicht entscheiden. Für die erste Komponente hast w1,.., wk also k Möglichkeiten diesen zu füllen, für die zweite k-1 und für die k-te Komponente eine Möglichkeite -> Wir müssen also noch durch k! teilen ->  Es gibt n! / (n-k)! k! Möglichkeiten eine k-elementige Menge zu wählen

---

c) 2 = 1+1 bedeutet du sollst den binomischen Lehrsatz anwenden also (1+1)^n =

\( \sum\limits_{k=0}^{n}{(n über k)*1^{k}}*1^{n-k} \) = \( \sum\limits_{k=0}^{n}{(n über k)} \) und benutze die b)