Mathematik: Anzahl surjektiver Abbildung - Teil 2
Released by matroid on Fr. 11. Januar 2002 00:00:00 [Statistics]
Written by matroid - 4672 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)\(\newcommand{\IX}{\mathbb{X}} \newcommand{\IW}{\mathbb{M}} \newcommand{\politician}[1]{\text{Ich habe die Frage nicht verstanden. #1}} \newcommand{\ba}{\begin{aligned}} \newcommand{\ea}{\end{aligned}} \newcommand{\bpm}{\begin{pmatrix}} \newcommand{\epm}{\end{pmatrix}} \newcommand{\bc}{\begin{cases}} \newcommand{\ec}{\end{cases}} \newcommand{\on}{\operatorname} \newcommand{\ds}{\displaystyle}\) Im Teil 1 hatte ich eine Summenformel für die Anzahl der surjektiven Abbildungen einer endlichen Menge M auf eine endliche Menge N hergeleitet.

Für diese Aufgabenstellung gibt es eine schöne Rekursionsgleichung:

Für die Anzahl A(n,k) der surjektiven Abbildungen einer n-elementigen Menge auf eine k-elementige Menge gilt:

A(n,k) = k*A(n-1,k-1) + k*A(n-1,k)

   mit A(0,0) = 1 [oder A(1,1) = 1]
   und A(n,k) = 0 für n < k.

Es folgt der Beweis dieser Beziehung mit vollständiger Induktion
über d := k-n.

Zunächst sei festgestellt, daß A(n,k) = 0 für n < k richtig ist. Es gibt keine surjektiven Abbildungen aus einer endlichen Menge auf eine andere endliche Menge, die mehr Elemente hat.

Induktionsanfang: Ist d = k-n = 0, dann haben beide Mengen gleich viele Elemente. Die Anzahl der surjektiven Abbildungen ist gleich k!, denn dem ersten Element aus M wird eines von k Elementen aus N zugeordnet, dem nächsten Element aus M wird eines der verbliebenen k-1 Elemente zugeordnet. Dies wird forgesetzt, bis schließlich dem letzten Element aus M das einzig noch verbliebene Element aus N zugeordnet wird.

Für k! =: fak(k) gilt die Rekursion fak(k) = k*fak(k-1) und weil A(n-1,k) = 0 ist für n=k, erweist sich die Rekursionsformel

A(n,k) = k*A(n-1,k-1) + k*A(n-1,k)
im Fall d = n-k = 0 als richtig.

Nun ist der Induktionsschritt auszuführen. Ich werde zeigen, daß aus der Gültigkeit der Rekursionsgleichung für d³0 die Gültigkeit für d+1 folgt.

Um das zu tun, muß die Aussage für Mengen M und N mit |N|-|M|=d+1 auf Mengen N' und M' mit |N'|-|M'| < d+1 zurückgeführt werden können.

Es enthalte also N genau d+1 Elemente mehr als die Menge M.
Betrachte nun die Menge F aller surjektiven Abbildungen von M nach N.
Diese Menge kann man in 2 Teilmengen U und V disjunkt aufteilen. Dazu wähle ich ein beliebiges xÎM aus und unterscheide danach, ob diese x für die Surjektivität der Abbildungen wirklich notwendig ist oder nicht.
Nämlich:

U := { f Î F | f(M-{x}) = N }
V := { f Î F | f(M-{x}) ¹ N }
Also - entweder hat das eine, beliebig aber fest ausgewählte x ein Bild in N, auf das auch mindestens ein anderes Element aus M abgebildet wird - oder nicht.

Die Menge U enthält genau die surjektiven Abbildungen f von M auf N, die eingeschränkt auf die Menge M-{x} auch eine surjektive Abbildung von M-{x} auf N ergeben.
Die Anzahl der surjektiven Abbildungen von M-{x} -> N ist A(n-1,k). Aus jeder dieser surjektiven Abbildungen kann man eine surjektive Abbildung von M -> N machen, indem man für das zuvor ausgewählte xÎM ein beliebiges von k möglichen Elementen aus N als Bild festlegt.

Die Menge V enthält genau die surjektiven Abbildungen f von M auf N, die eingeschränkt auf die Menge M-{x} nicht mehr surjektiv sind. Da F aber nur surjektive Abbildungen enthält und wir nur das eine Element x aus M entfernt haben, kann auch nur genau ein Element y aus N nun ohne Urbild sein.
Insofern ist f als Abbildung von M-{x} -> N-{y} wieder surjektiv.
Die Anzahl der surjektiven Abbildungen von M-{x} auf N-{y} ist A(n-1,k-1).
Jede surjektive Abbildung von M-{x} auf N-{y} kann zu einer surjektive Abbildung von M auf N ergänzt werden, indem man dem fest gewählten x ein weiteres Element yÎN zuordnet.
Sofern dieses yÎN feststeht, macht man also aus A(n-1,k-1) surjektiven Abbildungen von M-{x} auf N-{y} genau A(n-1,k-1) surjektive Abbildungen von M auf N.
Aber das yÎN steht nicht fest, es ist beliebig aus N, denn V enthält die Abbildungen fÎF für die f(M-{x}) ¹ N ist, also irgendeines der Elemente aus N im Bild von M-{x} fehlt.

Für die Wahl des 'fehlenden' Elements aus N gibt es k Möglichkeiten. Darum ist |V| = k * A(n-1,k-1)

Wem das zu schnell war, dem zeige ich es noch einmal genau, indem ich V weiter disjunkt zerlege.
Es ist V gleich der Vereinigung der Mengen
   Vy := { f Î V | f(M-{x}) = N-{y} } für alle yÎN.
Jedes Vy hat A(n-1,k-1) Elemente. Es gibt k verschiedene solche Mengen Vy.


Damit ist die Anzahl der surjektiven Abbildungen von M auf N mit |N|-|M| = d+1 zurückgeführt auf diese Anzahl für Mengen, die sich um weniger als d+1 Elemente unterscheiden.

Es wurde die Menge F aller surjektiven Abbildungen disjunkt zerlegt.

F = U È ÈyÎN Vy
Für die Teilmengen U und Vy gilt die Rekursionsformel, denn diese Mengen haben ein kleineres d.
Und weil die Zerlegung disjunkt ist, erhält man:
|F| = |U| + SyÎN |Vy|
und mit |U| = k*A(n-1,k) und |Vy| = A(n-1,k-1) sowie |N| = k schließlich:
A(n,k) = |F| = k*A(n-1,k) + k*A(n-1,k-1)
Da die Formel für d=0 gezeigt wurde, können wir abschließend den Induktionsschluß vollziehen:
Für A(n,k) mit d+1 = n-k gilt die Rekursionsgleichung ebenso, wie für alle Mengen M und N mit |N|-|M| < d+1.
Eine interessante Art der Induktion - quasi Induktion im Nebensatz, denn die wesentliche Arbeit bestand in der disjunkten Zerlegung. Der Schluß selbst ist dann selbstverständlich.

 
Dieser Artikel ist enthalten in unserem Buch
Mathematisch für fortgeschrittene Anfänger
Mathematisch für fortgeschrittene Anfänger

\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Mathematik :: Kombinatorik :: Abbildungen :: Leicht verständlich :
Anzahl surjektiver Abbildung - Teil 2 [von matroid]  
Im Teil 1 hatte ich eine Summenformel für die Anzahl der surjektiven Abbildungen einer endlichen Menge M auf eine endliche Menge N hergeleitet. Für diese Aufgabenstellung gibt es eine schöne Rekursionsgleichung: Für die Anzahl A(n,k) der surjektiven Abbildungen einer n-elementigen Menge auf eine
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 4672
 
Aufrufstatistik des Artikels
Insgesamt 305 externe Seitenaufrufe zwischen 2012.01 und 2022.01 [Anzeigen]
DomainAnzahlProz
https://www.ecosia.org72.3%2.3 %
https://matheplanet.com51.6%1.6 %
https://duckduckgo.com237.5%7.5 %
https://google.com72.3%2.3 %
http://google.de12440.7%40.7 %
http://google.lu5919.3%19.3 %
http://www.mathelounge.de3210.5%10.5 %
https://www.bing.com175.6%5.6 %
http://www.gute-mathe-fragen.de72.3%2.3 %
http://de.yhs4.search.yahoo.com20.7%0.7 %
http://www.ecosia.org41.3%1.3 %
http://google.ch20.7%0.7 %
https://www.qwant.com20.7%0.7 %
http://de.search.yahoo.com41.3%1.3 %
http://www.bing.com62%2 %
http://suche.t-online.de10.3%0.3 %
http://www.amazon.com10.3%0.3 %
http://google.com10.3%0.3 %
https://google.de10.3%0.3 %

Häufige Aufrufer in früheren Monaten
Insgesamt 255 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2013-2017 (63x)http://google.de/url?sa=t&rct=j&q=
201310-10 (51x)http://google.lu/url?sa=t&rct=j&q=
2015-2016 (32x)http://www.mathelounge.de/201018/wie-viele-surjektive-abbildungen-von-a-b-gib...
2020-2021 (18x)https://duckduckgo.com/
2020-2021 (17x)https://www.bing.com/
201212-12 (11x)http://google.de/url?sa=t&rct=j&q=rekursionsformel anzahl surjektiver abbildu...
201211-11 (11x)http://google.de/url?sa=t&rct=j&q=rekursion anzahl surjektive abbildungen
201210-10 (8x)http://google.lu/url?sa=t&rct=j&q=anzahl der abbildungen von m nach n
201305-05 (8x)http://google.de/url?sa=t&rct=j&q=induktion surjektive abbildungen
201306-06 (6x)http://google.de/url?sa=t&rct=j&q=die menge aller surjektiven abbildungen
201206-06 (6x)http://google.de/url?sa=t&rct=j&q=surjektive funktionen von n nach m
2020-2021 (5x)https://google.com/
201501-01 (5x)http://www.gute-mathe-fragen.de/201018/wie-viele-surjektive-abbildungen-von-a...
201301-01 (5x)http://google.de/url?sa=t&rct=j&q=surjektiv rekursionsformel anzahl der menge...
2020-2021 (5x)https://www.ecosia.org/
201203-03 (4x)http://google.de/url?sa=t&rct=j&q=anzahl surjektiver abbildungen

[Top of page]

"Mathematik: Anzahl surjektiver Abbildung - Teil 2" | 0 Comments
The authors of the comments are responsible for the content.

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 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]