Die Anzahl ist |M| |N| . Beweis durch doppelte vollst. Induktion über die Anzahlen der Elemente
n=|N| und m = |M|.
Sei n=1 , also N einelementig. Dann gibt es m verschiedene Abbildungen; denn
dem einzigen El. von N kann wahlweise eines der m Elemente von M zugeordnet
werden. Also gibt es m = m1 Abbildungen.
Ist m=1 , gibt es nur die konstante Abbildung mit dem Wert dieses einzigen Elementes von M,
also ist die Anzahl 1 = 1n .
Gilt die Formel nun für ein n aus ℕ und für alle m. Dann sei N nun eine n+1 elementige
Menge. Und x ein Element aus N.
Jede Abbildung f von N nach M besitzt dann eine Einschränkung auf N\{x} , das ist eine
n-elementige Menge , also gibt es mn solcher Einschränkungen. Und f(x) kann einen der
Werte von M annehmen, dafü gibt es m Möglichkeiten, also hat man m* mn
= mn+1 mögliche Abbildungen von N nach M.
Induktion über m:
Gilt die Formel nun für ein m aus ℕ und für alle n. Dann sei M nun eine m+1 elementige
Menge. Und y ein Element aus M.
Von den Abbildungen von N nach M gibt es dann solche, in deren Bildbereich das y nicht
vorkommt, das sind soviele, wie es Abbildungen von N in eine m-elementige Menge gibt,
also mn . Dann gibt es Abbildungen, bei denen genau ein x aus N auf y abgebildet wird.
Für das x gibt ( n über 1 ) Möglichkeiten und für jedes solche x gibt es mn-1 Abbildungen, die
sich je durch f(x)=y zu einer Abbildung von N nach M ergänzen lassen. Also gibt es von dieser
Art (n über 1) * mn-1 Abbildungen.
Wenn 2 Elemente von N auf das y abgebildet werden, gibt es dafür so viele Möglichkeiten
wie es 2-elementige Teilmengen von N gibt, also ( n über 2) . Und mn-2 Abbildungen , bei denen
nichts auf das y abgebildet wird. Also hier ( n über 2) * mn-2 Abbildungen .
In der Art erhält man für die Gesamtzahl der Abbildungen von N nach M
(n über 1) * mn-1 + ( n über 2) * mn-2 +( n über 3) * mn-3 +....+( n über n) * mn-n = (m+1)n .
