Die Mathe-Redaktion - 26.02.2018 04:46 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt1 im Schwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 303 Gäste und 3 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Stern Mathematik: Anzahl surjektiver Abbildung - Teil 1
Freigegeben von matroid am Sa. 05. Januar 2002 01:15:30
Verfasst von matroid -   41703 x gelesen [Gliederung] [Statistik] Druckbare Version Druckerfreundliche Version
Mathematik

\(\begingroup\)
Eine Abbildung einer Menge M in eine Menge N heißt surjektiv, wenn jedes Element fed-Code einblenden in der Menge der Bilder von Elementen aus M unter dieser Abbildung vorkommt.
Kurz geschrieben:

fed-Code einblenden

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:

fed-Code einblenden



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:

fed-Code einblenden

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:

fed-Code einblenden

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:

fed-Code einblenden

Mit diesem Prinzip zeigt man nun:


Satz: Die Anzahl der surjektiven Abbildungen von {1,...,n} -> {1,...,k} ist gleich

fed-Code einblenden

fed-Code einblenden
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\)

Link auf diesen Artikel Link auf diesen Artikel  Druckbare Version Druckerfreundliche Version  Einen Freund auf diesen Artikel aufmerksam machen Weitersagen Kommentare zeigen Kommentare  
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]

 
Verwandte Links
 
Besucherzähler 41703
 
Aufrufstatistik des Artikels
Insgesamt 1597 externe Besuche zwischen 2018.02 und 2018.02 [Anzeigen]
DomainAnzahlProz
http://matheplanet.com181.1%1.1 %
http://google.lu25516%16 %
http://google.de102364.1%64.1 %
http://matheraum.de1076.7%6.7 %
http://google.ru1056.6%6.6 %
http://google.it291.8%1.8 %
http://google.pt40.3%0.3 %
http://www.matheraum.de40.3%0.3 %
http://www.bing.com221.4%1.4 %
http://math-www.upb.de20.1%0.1 %
http://de.search.yahoo.com60.4%0.4 %
http://search.genieo.com40.3%0.3 %
http://google.at20.1%0.1 %
http://suche.t-online.de20.1%0.1 %
http://suche.aol.de10.1%0.1 %
http://de.yhs4.search.yahoo.com10.1%0.1 %
http://www.amazon.de10.1%0.1 %
http://google.ch10.1%0.1 %
http://yandex.ru10.1%0.1 %
http://isearch.avg.com10.1%0.1 %
http://ecosia.org10.1%0.1 %
http://search.certified-toolbar.com10.1%0.1 %
http://avira-int.ask.com10.1%0.1 %
http://www.amazon.com10.1%0.1 %
http://www.math.upb.de10.1%0.1 %
http://www.ecosia.org10.1%0.1 %
http://matheforum.net10.1%0.1 %
http://blackle.com10.1%0.1 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 3 Aufrufe in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2018.02.20-2018.02.23 (3x)https://www.google.ru/

Häufige Aufrufer in früheren Monaten
Insgesamt 1510 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
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=
2012-2016 (102x)http://matheraum.de/forum/Wuerfelspiel/t861986
2012.10 (102x)http://google.de/url?sa=t&rct=j&q=wie viele surjektive abbildungen gibt es
2013-2014 (78x)http://google.de/url?sa=t&rct=j&q=anzahl surjektiver funktionen
2012.05 (62x)http://google.de/url?sa=t&rct=j&q=wieviel verschiedenen abbildungen gibt es?
2013.01 (56x)http://google.ru/url?sa=t&rct=j&q=anzahl surjektiver abbildungen
2013.02 (49x)http://google.ru/url?sa=t&rct=j&q=menge surjektiver abbildungen
2012.01 (39x)http://google.de/url?sa=t&rct=j&q=wieviele surjektive abbildungen von m nach ...
2012.12 (39x)http://google.de/url?sa=t&rct=j&q=surjektive abbildung anzahl
2013.04 (38x)http://google.de/url?sa=t&rct=j&q=surjektiven abbildungen von einer n-element...
2014.02 (29x)http://google.it/url?sa=t&rct=j&q=
2014.11 (28x)http://google.de/url?sa=t&source=web&cd=9&ved=0CDgQFjAI
2012.06 (27x)http://google.de/url?sa=t&rct=j&q=surjektive abbildungen kombinatorik formel
2012.04 (25x)http://google.de/url?sa=t&rct=j&q=wie zeigt man surjektivität bei abbildunge...
2014.05 (24x)http://google.de/url?sa=t&source=web&cd=1&ved=0CCoQFjAA
2013.06 (23x)http://google.de/url?sa=t&rct=j&q=wie viele surjektive abbildungen m ! n gibt...
2014.04 (21x)http://google.de/url?sa=t&rct=j&q=wie viele verschiedene abbildungen gibt es ...
2014.12 (18x)http://google.de/url?sa=t&source=web&cd=2&ved=0CCUQFjAB
2015.01 (17x)http://google.de/url?sa=t&source=web&cd=1&ved=0CB0QFjAA
2012.07 (16x)http://google.de/url?sa=t&rct=j&q=wieviele surjektive funktionen gibt es
2013.12 (16x)http://google.de/url?sa=t&rct=j&q=stirling zahlen surjektiv beweis
2012.08 (15x)http://google.de/url?sa=t&rct=j&q=surjektive abbildungen anzahl
2013.07 (14x)http://google.de/url?sa=t&rct=j&q=zwei mengen anzahl von surjektiven abbildun...
2013.09 (12x)http://google.de/url?sa=t&rct=j&q=gib alle bijektiven abbildungen an
2014-2017 (7x)http://google.de/
2015.04 (4x)http://google.pt/url?sa=t&rct=j&q=

[Seitenanfang]

" Stern Mathematik: Anzahl surjektiver Abbildung - Teil 1" | 2 Kommentare
 
Für den Inhalt der Kommentare sind die Verfasser verantwortlich.

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 smile\(\endgroup\)

 [Bearbeiten]

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\)

 [Bearbeiten]

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2018 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. 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]