Beweis: Anzahl bijektiver Abbildungen in endlichen Mengen

12.02.2011, 09:53	Jens_358	Auf diesen Beitrag antworten »
Beweis: Anzahl bijektiver Abbildungen in endlichen Mengen Guten Morgen Mathe ! Folgendes ist mir gegeben: Sei f eine Abbildung auf einer Menge mit $\begin{eqnarray} n \in \mathbb{N} \text{ (ohne 0)} \end{eqnarray}$ . Zeigen Sie: Nur für n=1 gibt es mehr bijektive als nicht bijektive Abbildungen. Aus meiner Vorlesung weiß ich dass für eine Menge A mit n Elementen $\begin{eqnarray} n^n \end{eqnarray}$ Abbildungen existieren. Darüberhinaus weiß ich auch das es n! bijektive Abbildungen gibt. Nun haben wir die Aufgabe folgendermaßen bewiesen: n=1 Für n = 1 gibt es n = 1 bijektive Abbildungen und damit 1-1 = 0 (wegen $\begin{eqnarray} n^n - n! \end{eqnarray}$ ) nicht bijektive Abbildungen. $\begin{eqnarray} n\geq 2 \end{eqnarray}$ Es gilt: $\begin{eqnarray} n^n - 2n! = n\cdot n \cdot n \cdot ... \cdot n \text{[n-mal]} - 2\cdot n \cdot (n-1) \cdot ... \cdot 2 \cdot 1 \end{eqnarray}$ $\begin{eqnarray} n^n \end{eqnarray}$ hat also n Faktoren, 2n! ebenfalls. Dabei gilt für jeden Faktor f von 2n! $\begin{eqnarray} f \leq n \end{eqnarray}$ und daher auch $\begin{eqnarray} n^n -2n! \geq 0 \end{eqnarray}$ . Ich verstehe den größten Teil des Beweises, was ich allerdings nicht weiß ist, wie man auf die Behauptung $\begin{eqnarray} n^n - 2n! \end{eqnarray}$ kommt. Woher kommt 2n!, per Defintion haben wir doch nur n! bijektive Abbildungen? Vielen Dank für eure Hilfe. Jens
12.02.2011, 10:03	kiste	Auf diesen Beitrag antworten »
Das nennt man hier die Beweisidee ;-) Wenn du zeigen kannst, dass $\begin{eqnarray} n^n-2n! \geq 0 \end{eqnarray}$ gilt, so gilt auch $\begin{eqnarray} n^n-n!>0 \end{eqnarray}$
12.02.2011, 10:10	Jens_358	Auf diesen Beitrag antworten »
Vielen Dank! Darauf wäre ich jetzt niemals gekommen . Hätte man so etwas bei der Beweisführung nicht hinschreiben müssen, oder ist das nur optional, in der Annahme, dass der Leser so etwas normalerweise auch selbst verwendet? Danke ! Jens

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »