Stern Mathematik: Anzahl surjektiver Abbildung - Teil 1
Released by matroid on Sa. 05. Januar 2002 01:15:30 [Statistics]
Written by matroid - 47470 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}\) Eine Abbildung einer Menge M in eine Menge N heißt surjektiv, wenn jedes Element n\in\IN in der Menge der Bilder von Elementen aus M unter dieser Abbildung vorkommt. Kurz geschrieben: \ f: M -> N heißt surjektiv \:<=> \forall n \in N \exists m \in M : f(m) = n. Wieviele verschiedene surjektive Abbildungen gibt es, wenn M und N endliche Mengen sind? Im folgenden beweise ich mit dem Prinzip von Inklusion-Exklusion die Formel: \ S(n,k) = sum((-1)^i (k;i) (k-i)^n,0<=i<=k)

Hier im Forum war diese Frage auch schon diskutiert worden. Nach einigem Hin und Her hatte ich schließlich auf einen Eintrag in Sloane's On-Line Encyclopedia of Integer Sequences verwiesen. Die Folge ist dort verzeichnet unter der A-Nummer A019538. Da heißt es (u.a).:
Number of onto functions from an n-element set to a k-element set. a(n,k) = Sum_{j=0..k} (-1)^j*C(k,j)*(k-j)^n. a(n,k) = k*(a(n-1,k-1)+a(n-1,k))    with a(0,0) = 1 [or a(1,1) = 1]    - Henry Bottomley, Mar 02 2001    [Anm.: C(n,k) steht für den Binomialkoeffizienten "n über k".]
Die angegebene Rekursionsgleichung beweise ich in Teil II. Die erste Identität sagt, daß die gesuchte Anzahl surjektiver Abbildung von M -> N gleich der Anzahl der k-Partitionen einer n-elementigen Menge ist (sagen wir m:=#M und k:=#N).
Eine Partition ist eine Äquivalenzrelation auf einer Menge M. Eine k-Partition ist eine Partition mit der Mächtigkeit k, also mit genau k Äquivalenzklassen. Wieviele k-Partitionen einer n-elementigen Menge gibt es? Diese Anzahlen werden Stirling-Zahlen zweiter Art genannt und üblicherweise S(n,k) abgekürzt.
Für die Stirling Zahlen zweiter Art gilt: \big\ S(n,k)=1/k!*sum((-1)^i*(k;i)\.(k-i)^n,0<=i<=k) In dieser Formel teilt man durch k!, weil es nicht auf die Reihenfolge der k Äquivalenzklassen ankommt. Bei der Frage nach verschiedenen surjektiven Abbildungen, macht es aber schon einen Unterschied, welche Äquivalenzklasse auf welches Element aus {1,...,n} abgebildet wird. Darum übersehen wir vorausschauend den Faktor 1/k!. Das (-1)i deutet auf den Ursprung dieser Formel hin. Sie wurde mit dem Prinzip der Inklusion-Exklusion gefunden. Mit dem Prinzip von Inklusion und Exklusion lassen sich diejenigen Elemente einer gegebenen Menge zählen, die mindestens eine von mehreren vorgegebenen Eigenschaften aufweisen.
Beispiel: Wieviele natürliche Zahlen zwischen 1 und 1000 werden von mindestens einer der Zahlen 2, 3 oder 5 geteilt? Wenn nun A die Menge der durch zwei teilbaren Zahlen, B die der durch 3 und C die der durch 5 teilbaren Zahlen bezeichnet, dann gilt: abs(A\union\ B\union\ C)=abs(A)+abs(B)+abs(C)-abs(A\cut\ B)-abs(A\cut\ C)-abs(B\cut\ C) + abs(A\cut\ B\cut\ C)
Venn Diagramm
Dies ist eine sehr nützliche Formel für viele Abzählprobleme. Sie ist in der Kombinatorik bekannt als Prinzip von Inklusion und Exklusion, zu deutsch: Prinzip der Einschließung und Ausschließung, weil die Elemente des Durchschnitts von A und B bzw. A und C usw. zunächst doppelt gezählt und dann wieder abgezogen werden. Was für 3 Mengen gilt, kann man allgemein auch für n Mengen formulieren: \ |abs(union(A_i,0<=i<=n))=sum((-1)^(abs(I)+1)*abs(cut(A_i,i\el\ I)),\0!=I\subsetequal\ menge(1,2,...,n)) Mit diesem Prinzip zeigt man nun:

Satz: Die Anzahl der surjektiven Abbildungen von {1,...,n} -> {1,...,k} ist gleich \big\ T(n,k)=sum((-1)^i*(k;i)\.(k-i)^n,0<=i<=k) Beweis:__ Für jedes j\el\ {1,...,k} sei A_j die Menge aller Abbildungen f von {1,2,...,n} nach {1,2,...,k}, die j nicht treffen, d.h. für kein i\el {1,...,n} ist f(i) = j. A_j hat so viele Elemente, wie es Abbildungen von {1,2,...,n} nach {1,2,...,j-1,j+1,...,k} gibt, also (k-1)^n. Für den Durchschnitt zweier Mengen A_j_1 und A_j_2 gilt, daß dies die Anzahl aller Abbildungen ist, die j_1 und j_2 nicht treffen. Das sind (k-2)^n Stück. Man erkennt, daß der Durchschnitt von r dieser Mengen genau (k-r)^n verschiedene Abbildungen enthält, die bestimmte r Elemente nicht als Bild haben. \small\ Anm.: Die Anzahlen (k-r)^n sind für r>0 durchweg nicht gewünscht, wenn man surjektive Abbildungen sucht. Diese Formel zählt also erstaunlicherweise das Gegenteil__ von dem, was wir wollten, nämlich sie zählt die array(nicht surjektiven)__ Abbildungen. Aber das hat Methode, denn zum Schluß werden wird das Komplement bilden! \frameon\Die Menge der surjektiven Abbildungen ist gleich der Menge aller__ Abbildungen abzüglich__ der nicht surjektiven Abbildungen. Wie groß ist die Anzahl aller Abbildungen von {1,...,n}->{1,...,k}?
Es sind kn, oder - um in der Systematik zu bleiben - es sind (k-0)n. Den Summanden (k-0)n enthält die zu beweisende Summenformel für i=0. Bleibt zu zeigen, daß die übrigen Terme (für i>0) gerade die Anzahl der nicht surjektiven Abbildungen ergeben. Zurück zu Inklusion-Exklusion: In der Summe der Mächtigkeiten der Aj sind alle die Abbildungen doppelt gezählt, die mehr als 1 Element aus {1,...,m} nicht als Bild (irgend)-eines Elements aus {1,...,n} haben. Dieser Fehler muß durch Addition der Mächtigkeiten der Schnittmengen von jeweils zweien der Aj wieder wettgemacht werden.
Allerdings haben wir damit zuviel des Guten getan. Die Abbildungen, die mindestens 3 Elemente aus {1,...,n} nicht zum Bild haben, sind nun mehrfach subtrahiert worden. Dieser Fehler wird ausgeglichen durch Addition der Mächtigkeiten der Durchschnitte von jeweils dreien der Aj. Nun darf ich "usw." sagen, ok? Danke. Was fehlt denn noch? Ach ja, "k über i", was hat es denn damit auf sich? Aber der Weg ist nicht mehr weit. Lies noch mal einige Zeilen zurück: ich sagte: "von jeweils zweien der Aj" und "von jeweils dreien der Aj".
Man kann auf "n über 2" Weisen zwei verschiedene der Aj aussuchen, um sie zu schneiden. Man kann auf "n über 3" Weisen drei verschiedene der Aj aussuchen, um sie zu schneiden.

Ich erlaube mir ein letztes "usw." und bitte Dich zur Kontrolle noch einmal auf die Formel zu blicken. Nun alles klar? Für diesen Artikel habe ich Gesamtheiten von Elke Wilkeit (Link ex.nicht mehr) und Anzahlen von Erich Prisner zu Rate gezogen.
Trennlinie

Demnächst werde ich auch die zweite bei Sloane's zitierte Formel, die Rekursion, näher erklären. Siehe Teil 2.


 
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 1 [von matroid]  
Eine Abbildung einer Menge M in eine Menge N heißt surjektiv, wenn jedes Element n Î N in der Menge der Bilder von Elementen aus M unter dieser Abbildung vorkommt. Kurz geschrieben: f: M -> N heißt surjektiv : " nÎN $ m ÎM: f(m) = n. Wieviele verschiedene surjektive Abbildungen gibt es, wenn
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 47470
 
Aufrufstatistik des Artikels
Insgesamt 2268 externe Seitenaufrufe zwischen 2012.01 und 2022.01 [Anzeigen]
DomainAnzahlProz
https://matheplanet.com100.4%0.4 %
https://google.com301.3%1.3 %
https://duckduckgo.com1376%6 %
https://www.ecosia.org502.2%2.2 %
https://www.bing.com823.6%3.6 %
https://google.de31313.8%13.8 %
http://google.lu25511.2%11.2 %
http://google.de102345.1%45.1 %
http://matheraum.de1074.7%4.7 %
http://google.ru1054.6%4.6 %
https://google.lu472.1%2.1 %
http://google.it291.3%1.3 %
https://www.qwant.com90.4%0.4 %
https://www.startpage.com50.2%0.2 %
http://google.pt40.2%0.2 %
http://www.bing.com221%1 %
https://uk.search.yahoo.com30.1%0.1 %
http://www.matheraum.de40.2%0.2 %
http://de.search.yahoo.com60.3%0.3 %
http://search.genieo.com40.2%0.2 %
http://google.at20.1%0.1 %
http://math-www.upb.de20.1%0.1 %
https://cn.bing.com10%0 %
http://www.amazon.com10%0 %
http://suche.t-online.de20.1%0.1 %
http://www.math.upb.de10%0 %
http://www.amazon.de10%0 %
http://google.ch10%0 %
http://suche.aol.de10%0 %
http://yandex.ru10%0 %
http://www.ecosia.org10%0 %
https://at.search.yahoo.com10%0 %
http://search.certified-toolbar.com10%0 %
http://de.yhs4.search.yahoo.com10%0 %
http://isearch.avg.com10%0 %
https://de.search.yahoo.com10%0 %
http://avira-int.ask.com10%0 %
http://ecosia.org10%0 %
http://matheforum.net10%0 %
http://blackle.com10%0 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 48 Aufrufe in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2022.01.17-2022.01.24 (9x)viewtopic.php?topic=180
2022.01.04-2022.01.23 (22x)https://google.com/
2022.01.07-2022.01.20 (17x)https://duckduckgo.com/

Häufige Aufrufer in früheren Monaten
Insgesamt 2131 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2020-2021 (274x)https://google.de/
2012-2013 (255x)http://google.lu/url?sa=t&rct=j&q=
2012-2013 (250x)http://google.de/url?sa=t&rct=j&q=wieviele surjektive abbildungen gibt es
2013-2018 (144x)http://google.de/url?sa=t&rct=j&q=
2020-2021 (113x)https://duckduckgo.com/
201210-10 (102x)http://google.de/url?sa=t&rct=j&q=wie viele surjektive abbildungen gibt es
2012-2016 (102x)http://matheraum.de/forum/Wuerfelspiel/t861986
2020-2021 (80x)https://www.bing.com/
2013-2014 (78x)http://google.de/url?sa=t&rct=j&q=anzahl surjektiver funktionen
201205-05 (62x)http://google.de/url?sa=t&rct=j&q=wieviel verschiedenen abbildungen gibt es?
201301-01 (56x)http://google.ru/url?sa=t&rct=j&q=anzahl surjektiver abbildungen
201302-02 (49x)http://google.ru/url?sa=t&rct=j&q=menge surjektiver abbildungen
202111-11 (47x)https://google.lu
2020-2021 (40x)https://www.ecosia.org/
201212-12 (39x)http://google.de/url?sa=t&rct=j&q=surjektive abbildung anzahl
201201-01 (39x)http://google.de/url?sa=t&rct=j&q=wieviele surjektive abbildungen von m nach ...
201304-04 (38x)http://google.de/url?sa=t&rct=j&q=surjektiven abbildungen von einer n-element...
2020-2021 (38x)https://google.de
201402-02 (29x)http://google.it/url?sa=t&rct=j&q=
201411-11 (28x)http://google.de/url?sa=t&source=web&cd=9&ved=0CDgQFjAI
201206-06 (27x)http://google.de/url?sa=t&rct=j&q=surjektive abbildungen kombinatorik formel
201204-04 (25x)http://google.de/url?sa=t&rct=j&q=wie zeigt man surjektivität bei abbildun...
201405-05 (24x)http://google.de/url?sa=t&source=web&cd=1&ved=0CCoQFjAA
201306-06 (23x)http://google.de/url?sa=t&rct=j&q=wie viele surjektive abbildungen m ! n gibt...
201404-04 (21x)http://google.de/url?sa=t&rct=j&q=wie viele verschiedene abbildungen gibt es ...
201412-12 (18x)http://google.de/url?sa=t&source=web&cd=2&ved=0CCUQFjAB
201501-01 (17x)http://google.de/url?sa=t&source=web&cd=1&ved=0CB0QFjAA
201312-12 (16x)http://google.de/url?sa=t&rct=j&q=stirling zahlen surjektiv beweis
201207-07 (16x)http://google.de/url?sa=t&rct=j&q=wieviele surjektive funktionen gibt es
201208-08 (15x)http://google.de/url?sa=t&rct=j&q=surjektive abbildungen anzahl
201307-07 (14x)http://google.de/url?sa=t&rct=j&q=zwei mengen anzahl von surjektiven abbildun...
201309-09 (12x)http://google.de/url?sa=t&rct=j&q=gib alle bijektiven abbildungen an
2020-2021 (9x)https://www.qwant.com/
2020-2021 (8x)https://google.com/
2020-2021 (7x)https://duckduckgo.com
2014-2017 (7x)http://google.de/
2020-2021 (5x)https://www.startpage.com/
201504-04 (4x)http://google.pt/url?sa=t&rct=j&q=

[Top of page]

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

Re: Anzahl surjektiver Abbildung - Teil 1
von: Ex_Mitglied_40174 am: Di. 23. September 2003 15:17:55
\(\begingroup\)Dieser Fehler muß durch Addition der Mächtigkeiten der Schnittmengen von jeweils zweien der Aj wieder wettgemacht werden.

sollte wohl heissen:

Dieser Fehler muß durch SUBTRAKTION der Mächtigkeiten der Schnittmengen von jeweils zweien der Aj wieder wettgemacht werden.

ansonsten danke :)\(\endgroup\)
 

Re: Anzahl surjektiver Abbildung - Teil 1
von: Hanno am: Sa. 18. Juni 2005 10:37:27
\(\begingroup\)Hallo! Bei mir (ich benutze FreeBSD, als Browser den Firefox) werden die Formeln nicht korrekt angezeigt. Kannst du sie vielleicht nochmals generieren lassen oder sie mit dem Formeleditor schreiben? Danke! Liebe Grüße, Hanno\(\endgroup\)
 

 
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]