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}ⁿ | 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}ⁿ | 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)ⁿ =

$\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)