Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 13

Aus Wikiversity
Zur Navigation springen Zur Suche springen
In ihrer Freizeit tobt Vorli gerne mit dem Nachbarshund Jurek rum. Der arbeitet auch als Vorlesungshund, allerdings bei den Juristen. Vorli stellt sich das unglaublich langweilig vor.


In dieser Vorlesung besprechen wir Zahlen, die mit der Anzahl von Abbildungen von in eine -elementige Menge zusammenhängen, und insbesondere die Anzahl von surjektiven Abbildungen.



Die Multinomialkoeffizienten

Der Binomialkoeffizient beschreibt die Anzahl der -elementigen Teilmengen einer -elementigen Menge. Eine solche Teilmenge kann man auch auffassen als eine Zerlegung einer -elementigen Menge in zwei Teilmengen, von denen die eine und die andere Elemente besitzt, und wobei man sich die Rollen der beiden Teilmengen merkt. Man kann sich nun fragen, wie viele Möglichkeiten es gibt, eine -elementigen Menge in Teilmengen aufzuteilen, wobei die Teilmengen vorgegebene Anzahlen haben und wobei die Teilmengen durchnummeriert werden. Dies führt zum Begriff Multinomialkoeffizient.


Definition  

Es sei eine natürliche Zahl und natürliche Zahlen mit . Dann nennt man

den Multinomialkoeffizienten über .

Statt Multinomialkoeffizient sagt man auch Polynomialkoeffizient. Für ist dies der Binomialkoeffizient, in diesem Fall legt die erste Zahl durch die Bedingung die zweite Zahl fest. Generell legen die Zahlen , deren Summe ist, die letzte Zahl fest. Die Multinomialkoeffizienten besitzen eine Vielzahl an Interpretationen, zentral ist die folgende Interpretation mit Abbildungen.



Lemma  

Es sei eine -elementige Menge und seien mit vorgegeben.

Dann ist die Anzahl der Abbildungen von nach mit der Eigenschaft, dass für alle ist, gleich

Beweis  

Für die Faser über gibt es Möglichkeiten, man muss ja die Elemente auswählen, die auf die gehen sollen. Wenn dies festgelegt ist, so gibt es für die Faser über genau Möglichkeiten. In diesem Sinne gibt es für die Faser über genau Möglichkeiten. Wenn man diese Zahlen miteinander multipliziert, so ergibt sich

also der Multinomialkoeffizient.


Durch die Bedingungen für alle sind die surjektiven Abbildungen gekennzeichnet.

Die Multinomialkoeffizienten beschreiben also die Anzahl der Möglichkeiten, Elemente auf Ziele abzubilden, wobei das -te Ziel durch ELemente getroffen werden. Man sagt auch so: Es gibt viele Möglichkeiten, unterscheidbare Kugeln auf unterscheidbare Urnen zu verteilen derart, dass in der ersten Urne Kugeln, in der zweiten Urne Kugeln u.s.w. landen. Die entsprechende Abbildung aus Lemma 13.2 ordnet jeder Kugel die Urne zu, in die sie reinkommt (Elemente in einer Menge sind stets unterscheidbar; bei Verteilungen von Kugeln auf Urnen gibt es auch nicht unterscheidbare Szenarien). Man kann auch umgekehrt aus unterscheidbaren Urnen, die jeweils eine hinreichend große Anzahl von urnenspezifischen Objekten beinhalten, eine geordnete Ziehung der Länge vornehmen, derart, dass aus der -ten Urne (also der -te Objekttyp) genau Elemente gezogen werden. Die Objekte aus der gleichen Urne müssen nicht unterschiedbar sein, dies wird durch die Ziehreihenfolge übernommen. Die entsprechende Abbildung aus Lemma 13.2 ordnet der Nummer von bis die Urne bzw. den Objekttyp zu, der für diese Nummer gezogen wird. Beispielsweise ist die Anzahl der Möglichkeiten, aus einer vorgegebenen Buchstabenansammlung mit Buchstaben, die -fach vorkommen, , Wörter zu bilden, die genau diese Buchstaben verbrauchen, durch den Multinomialkoeffizienten gegeben. Ein Wort der Länge kann man direkt als eine Wertetabelle einer Abbildung von in die Buchstabenmenge auffassen.


Beispiel  

Wir wollen wissen, wie viele Wörter (im Sinne von Buchstabenketten) man aus dem Wort „Homomorphismus“ bilden kann, derart, dass genau die vorgegebenen Buchstaben verwendet werden. Das Wort hat insgesamt Buchstaben, dabei kommen und dreimal, und zweimal und einmal vor. Somit gibt es

Möglichkeiten.


Die folgende Aussage heißt Multinomialsatz oder Polynomialsatz und ist eine direkte Verallgemeinerung des binomischen Lehrsatzes.


Satz

Es sei ein kommutativer Halbring und seien Elemente und .

Dann ist

Beweis

Siehe Aufgabe 13.7.



Surjektive Abbildungen

Im Gegensatz zur Anzahl von injektiven oder bijektiven Abbildung zwischen endlichen Mengen ist die Anzahl von surjektiven Abbildungen nicht so einfach zu bestimmen. Es gibt mehrere Formeln bzw. Ansätze dafür, wobei weder die Beziehung untereinander unmittelbar klar ist noch, welche Formel für Berechnungen besonders geeignet sind. Es besteht aber ein unmittelbarer Zusammenhang mit der Anzahl von Partitionen, auf die wir in der nächsten Vorlesung eingehen.



Lemma  

Es sei eine -elementige Menge und eine -elementige Menge.

Dann ist die Anzahl der surjektiven Abbildungen von nach gleich

Beweis  

Dies folgt unmittelbar aus Lemma 13.2, da ja eine Abbildung genau dann surjektiv ist, wenn alle Fasern nicht leer sind, was sich in der Bedingung niederschlägt.




Satz  

Es sei eine -elementige Menge und eine -elementige Menge.

Dann ist die Anzahl der surjektiven Abbildungen von nach gleich

Beweis  

Wir führen Induktion über und bei fixiertem Induktion nach . Bei ist die Aussage richtig. Sei also fixiert und sei die Aussage für alle kleineren und alle bereits bewiesen. Für ist der Summenausdruck gleich , und es gibt auch keine surjektive Abbildung einer -elementigen Menge in eine größere Menge. Bei ist das einzige Indextupel gleich und der Summenausdruck ist gleich , was mit der Anzahl der surjektiven bzw. bijektiven Abbildungen nach Satz 2.4 übereinstimmt. Sei also die Aussage für bewiesen und betrachten wir eine surjektive Abbildung von nach . Dabei ist entweder schon die Einschränkung auf surjektiv oder nicht. Im ersten Fall gibt es bei gegebenem genau Möglichkeiten für , da ja auf eines der Elemente abgebildet werden kann. Im zweiten Fall, wenn nicht surjektiv ist, so wird durch genau ein Element der Bildmenge nicht getroffen, und muss auf dieses nicht getroffene Element abbilden, um die Surjektivität sicherzustellen. Es gibt hierbei Möglichkeiten, welches Element von nicht getroffen wird. Ferner ist eine surjektive Abbildung auf eine -elementige Teilmenge. Somit ist unter Verwendung der Induktionsvoraussetzung die Anzahl der surjektiven Abbildungen von nach gleich




Satz  

Es sei eine -elementige Menge und eine -elementige Menge.

Dann ist die Anzahl der surjektiven Abbildungen von nach gleich

Beweis  

Wir setzen . Zu setzen wir

Die Menge der nichtsurjektiven Abbildungen ist somit . Zu haben die Durchschnitte

eine inhaltliche Bedeutung: Es handelt sich um alle Funktionen von nach . Deren Anzahl ist nach Satz 2.2 gleich . Nach der Siebformel ist somit

Die Anzahl der surjektiven Abbildungen ist daher gleich



Beispiel  

Wir bestimmen die Anzahl der surjektiven Abbildungen der fünfelementigen Menge in die dreielementige Menge mit Hilfe von Lemma 13.5, Satz 13.6 und Satz 13.7. Zur Bestimmung der Summe aus Lemma 13.5 betrachten wir zuerst die Indexmenge. Die möglichen Indextupel sind und , jeweils mit drei Permutationen. Deshalb ist die Summe gleich

Zur Bestimmung der Summe in Satz 13.6 betrachten wir wieder die Indextupel, wobei ähnlich wie soeben bis auf Permutationen die Summen möglich sind. Die zugehörigen Summanden hängen aber von den Permutationen ab. Es ist

Die Summe aus Satz 13.7 ist


Als Alternative zu den oben angegebenen expliziten Formeln, hinter denen jeweils eine aufwändige Summation steht, kann man mit der folgenden Rekursionsformel für die Anzahl von surjektiven Abbildugnen arbeiten. Die Grundidee hierzu wurde schon im Beweis zu Satz 13.6 verwendet.


Lemma

Zu bezeichne die Anzahl der surjektiven Abbildungen einer -elementigen Menge in eine -elementige Menge.

Dann gilt die Rekursionsformel

Beweis

Siehe Aufgabe 13.16.


<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)