Vollst. Induktion - Bijektion < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:09 Mi 17.11.2004 | | Autor: | michael7 |
Hallo,
ich soll zeigen, wenn $X$ und $Y$ zwei $n$-elementige Mengen sind, dass es dann genau $n!$ bijektive Abbildungen von $X$ nach $Y$ gibt.
Das koennte man ja relativ leicht mittels Kombinatorik beweisen, indem man das ganze als eine Permutation auffasst. Ich wuerde aber gerne ueber vollstaendige Induktion beweisen. Wie aber kann ich die Induktionsvoraussetzung und die Induktionsbehauptung mathematisch korrekt formulieren?
Ich habe z.B. folgendes probiert (hier mal die Behauptungen):
[mm] $\textup{Abb}(\{a_1, \ldots, a_n, a_{n+1}\} \rightarrow \{b_1, \ldots, b_n, b_{n+1}\}) [/mm] = (n+1)!$
Wie aber kann ich dann die linke Seite vom Gleichheitszeichen "zerlegen", um die Voraussetzung zu verwenden?
Ein weiterer Ansatz:
Da man weiss, dass es bei $n$ Elementen $n!$ bijektive Abbildungen gibt, kann man die Fakultaet so schreiben (wieder direkt die Behauptung):
[mm] $1\cdot 2\cdot \ldots\cdot n\cdot [/mm] (n+1) = (n+1)!$
Aber ich befuerchte, dass ich dann gar nicht das eigentlich Gesuchte zeige.
Ein Tipp zum korrekten Ansatz wuerde mir schon weiterhelfen.
Michael
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:18 So 21.11.2004 | | Autor: | Marc |
Hallo michael7,
> ich soll zeigen, wenn [mm]X[/mm] und [mm]Y[/mm] zwei [mm]n[/mm]-elementige Mengen
> sind, dass es dann genau [mm]n![/mm] bijektive Abbildungen von [mm]X[/mm]
> nach [mm]Y[/mm] gibt.
>
> Das koennte man ja relativ leicht mittels Kombinatorik
> beweisen, indem man das ganze als eine Permutation
> auffasst. Ich wuerde aber gerne ueber vollstaendige
> Induktion beweisen. Wie aber kann ich die
> Induktionsvoraussetzung und die Induktionsbehauptung
> mathematisch korrekt formulieren?
>
> Ich habe z.B. folgendes probiert (hier mal die
> Behauptungen):
>
> [mm]\textup{Abb}(\{a_1, \ldots, a_n, a_{n+1}\} \rightarrow \{b_1, \ldots, b_n, b_{n+1}\}) = (n+1)![/mm]
Hier meinst du [mm]\red{|}\textup{Abb}(\{a_1, \ldots, a_n, a_{n+1}\} \rightarrow \{b_1, \ldots, b_n, b_{n+1}\})\red{|} = (n+1)![/mm].
> Wie aber kann ich dann die linke Seite vom
> Gleichheitszeichen "zerlegen", um die Voraussetzung zu
> verwenden?
Meine Idee (für den Induktionsschritt) wäre folgende:
Es gilt also
[mm]|\textup{Abb}(\{a_1, \ldots, a_n\} \rightarrow \{b_1, \ldots, b_n \})| = n![/mm]
Die Menge [mm] $A:=\textup{Abb}(\{a_1, \ldots, a_n,a_{n+1}\} \rightarrow \{b_1, \ldots, b_n,b_{n+1} \})$ [/mm] spalte ich nun in n+1 Mengen auf:
[mm] $A_1=\left\{ f\in \textup{Abb}(\{a_1, \ldots, a_n,a_{n+1}\} \rightarrow \{b_1, \ldots, b_n,b_{n+1} \})\ [/mm] |\ [mm] f(a_{n+1})=b_1\right\}$ [/mm]
[mm] $A_2=\left\{ f\in \textup{Abb}(\{a_1, \ldots, a_n,a_{n+1}\} \rightarrow \{b_1, \ldots, b_n,b_{n+1} \})\ [/mm] |\ [mm] f(a_{n+1})=b_2\right\}$ [/mm]
[mm] $\vdots$
[/mm]
[mm] $A_{n+1}=\left\{ f\in \textup{Abb}(\{a_1, \ldots, a_n,a_{n+1}\} \rightarrow \{b_1, \ldots, b_n,b_{n+1} \})\ [/mm] |\ [mm] f(a_{n+1})=b_{n+1}\right\}$ [/mm]
Die Abbildungen in jeder dieser Mengen läßt sich nun auffassen als eine Abbildung [mm] $\{a_1, \ldots, a_n\} \rightarrow \{b'_1, \ldots, b'_n \}$ [/mm] (mit [mm] $b'_1,\ldots,b'_n\in\{b_1,\ldots,b_{n+1}\}$ [/mm] (das kann man für jede Abb. aus einer Menge ja noch schöner hinschreiben)).
Insegesamt haben wir die Menge A in n+1 Mengen mit n! Elementen partitioniert, also insgesamt (n+1)*n! Elemente.
Viele Grüße,
Marc
|
|
|
|
