\(\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)
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.
Demnächst werde ich auch die zweite bei Sloane's zitierte Formel, die Rekursion, näher erklären. Siehe Teil 2.
\(\endgroup\)
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
Mathematik: Anzahl surjektiver Abbildung - Teil 1
Printer-friendly version
Get link to this article
Comments
Für diesen Artikel gibt es keine pdf-Datei
Dieser Artikel ist im Verzeichnis der 
