| |
| Autor |
 Beweis durch Induktion |
|
Anonymous
Unregistrierter Benutzer
|  Themenstart: 2002-04-20
|
Eine m-Menge M wird auf eine n-Menge N abgebildet. Die Anzahl der Mengenglieder der Abbildung beträgt n^m.
Wie kann man das durch Induktion beweisen?
|
|
matroid
Senior 
Dabei seit: 12.03.2001
Mitteilungen: 14571
Wohnort: Solingen
 |  Beitrag No.1, eingetragen 2002-04-21
|
Hi,
da zwei Zahlen, n und m, beteiligt sind, muß man zwei Induktionen machen.
Bezeichne mit B(n,m) die zu beweisende Aussage.
Zeige
[1] B(m,n) => B(m+1,n) und
[2] B(m,n) => B(m,n+1)
Erfolgreicher Induktionsanfang sei vorausgesetzt.
Zu [1]:
Sei M eine Menge mit m+1 Elementen. Sei N eine Menge mit n Elementen.
Sei x aus M.
Das Element x aus M kann auf jedes der n Elemente aus N abgebildet werden.
Jede Abbildung von M\{x}->N kann durch Festlegung eines Bildes für x in N zu einer Abbildung von M->N fortgesetzt werden. Für diese Festlegung gibt es n verschiedene Möglichkeiten. Es gibt also n*nm verschiedene Fortsetzungen.
Umgekehrt wird jede Abbildung von M->N durch Beschränkung auf die Werte aus M\{x} zu einer Abbildung von M\{x}->N. Zwei verschiedene Abbildungen von M->N haben genau dann die gleiche Beschränkung, wenn sie sich nur mit dem Bild von x unterscheiden. Für x gibt es - wie schon gesagt - n verschiedene Bilder in N.
Das bedeutet:
Die Anzahl der Abbildungen von M->N ist n mal die Anzahl der Abbildungen von M\{x}->N.
Die Anzahl der Abbildungen von M\{x}->N ist
nach Induktionsvoraussetzung gleich nm.
Zu [2]: Ein Irrweg
Sei M eine Menge mit m Elementen. Sei N eine Menge mit n+1 Elementen.
Sei y aus N.
Das Element y aus N hat ein Urbild in M, möglicherweise aber auch mehrere oder keines.
Die Abbildungen von M->N kann man disjunkt aufteilen, je nach der Anzahl der Elemente aus M, die auf y abgebildet werden.
Bezeichne die Menge der Abbildungen von M->N, die k Elemente aus M auf das ausgewählte y abbilden mit A(k) und deren Anzahl mit a(k).
Zwischenbehauptung:
Es ist a(k) = binomial(m,k)*nk
Beweis der Zwischenbehauptung.
Für k=0 gilt, daß a(k) gleich der Anzahl der Abbildungen von M->N\{y} ist. Diese ist nach Induktionsvoraussetzung gleich nm.
In A(1) sind die Abbildungen, die genau ein x aus M auf y abbilden, alle anderen Abbildungsvorschriften sind beliebig. Das x kann auf m verschiedene Weisen ausgewählt werden. Zu jeder Abbildung von M->N aus A(1) gehört also genau eine Abbildung von M\{x}->N\{y}. Deren Anzahl ist gleich nm-1.
Multipliziert mit den Wahlmöglichkeiten für x ergibt das m*nm-1.
Mist! Das ist zwar alles richtig bisher, aber es führt auf die Binomialkoeffizienten. Und damit führt der Beweis quasi von Hölzchen auch Stöckchen.
Ich versuche es anders.
Sei A(M,N) die Menge der Abbildungen einer Menge M in eine Menge N. Setze voraus, daß |M|>0 und |N|>0.
Behauptung: |A(M,N)| = |N||M|
Induktion über k = |M|+|N|.
Induktionsanfang für k = 2. M und N sind nichtleer, also hat bei k=2 jede Menge genau ein Element.
Es gibt genau eine Abbildung einer 1-elementigen Menge in eine 1-elementige. Die Anzahl ist auch gleich 11.
Seien nun Mengen M und N gegeben mit |M|+|N| = k+1. Sei |M|>0 und |N|>0.
Falls |M|>1, also M mindestens 2 Elemente hat, dann wähle eines der Elemente von M, das sei x. Es ist (siehe [1]) die Anzahl der Abbildungen von M\{x}->N gleich |N||M|-1. Das Element x aus M kann auf |N| verschiedene Weisen abgebildet werden. Folgt: Die Anzahl der Abbildungen von M->N ist |N|*|N||M|-1 = |N||M|.
Wenn aber M nur 1 Element enthält, dann gibt es |N| Möglichkeiten dieses auf ein Element aus N abzubilden. Auch in diesem Fall ergibt das die Formel |N||M|.
qed.
Wegen des Umwegs, den ich gemacht habe, muß ich jetzt mal zusammenfassen.
[1] B(m,n) => B(m+1,n)
[2'] C(k) => C(k+1)
B(m,n) ist die Behauptung: Die Anzahl der Abbildungen von M->N ist nm, mit |M|=m und |N|=n
C(k) ist die Behauptung: Die Anzahl der Abbildungen von M->N, M und N nicht leer und |M|+|N| = k ist |N||M|.
Etwas aufwendig das ganze. Aber was soll man machen, wenn für so eine einfache Aussage ein Beweis gefragt wird.
Gruß
Matroid
|
 Profil
|
Anonymous
Unregistrierter Benutzer
| Beitrag No.2, vom Themenstarter, eingetragen 2002-04-21
|
|
matroid
Senior
Dabei seit: 12.03.2001
Mitteilungen: 14571
Wohnort: Solingen
| Beitrag No.3, eingetragen 2002-04-21
|
Hi,
wenn ich mir das nochmal ansehe, stelle ich fest, der Beweis von [2'] enthält eigentlich keine Argumente, die nicht schon in [1] verwendet worden sind.
Man hätte also [1] und [2'] auch als [1'] formulieren können:
[1'] Für beliebiges N mit |N| > 0 und M mit m Elemente gilt A(M,N) = |N|m. Und dann Induktion über m. Das reicht.
Gruß
Matroid
|
Profil
|
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
