Benutzer:Bocardodarapti/Arbeitsseite/Diskrete Mathematik

Aus Wikiversity
Zur Navigation springen Zur Suche springen




Kugel und Urnen

unterscheidbar, ununterscheidbar.

unterscheidbar durchnummeriert ; Vorgang hintereinander


Abbildungsanzahl


Lemma

Es seien und endliche Mengen mit bzw. Elementen.

Dann gibt es Abbildungen von nach .

Diese Anzahl entspricht der Anzahl der Möglichkeiten, unterscheidbare Kugeln (die Elemente aus ) auf unterscheidbare Urnen zu verteilen.

Dies entspricht auch dem -fachen geordneten Ziehen von Elementen aus einer -elementigen Menge mit Zurücklegen.


Lemma

Es seien und endliche Mengen mit bzw. Elementen mit .

Dann gibt es injektive Abbildungen von nach .

Diese Anzahl entspricht der Anzahl der Möglichkeiten, unterscheidbare Kugeln (die Elemente aus ) auf unterscheidbare Urnen zu verteilen, wobei jede Urne nur einfach belegt werden darf.

Dies entspricht auch dem -fachen geordneten Ziehen von Elementen aus einer -elementigen Menge ohne Zurücklegen.


Lemma

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

Dann ist die Anzahl der surjektiven Abbildungen von nach gleich .

Diese Anzahl entspricht der Anzahl der Möglichkeiten, unterscheidbare Kugeln (die Elemente aus ) auf unterscheidbare Urnen zu verteilen, wobei jede Urne belegt werden muss.


Dies entspricht auch dem -fachen geordneten Ziehen von Elementen aus einer -elementigen Menge mit Zurücklegen und mit Trefferzwang (jedes Element muss mindestens einmal gezogen werden).



Lemma

Die Stirlingsche Zahl zweiter Art

beschreibt die Anzahl an Möglichkeiten, unterscheidbare Kugeln auf ununterscheidbare Urnen so zu verteilen, dass keine Urne leer bleibt.




Lemma

Die Anzahl der -elementigen Teilmengen in einer -elementigen Menge ist


Diese Anzahl entspricht der Anzahl der Möglichkeiten, ununterscheidbare Kugeln (die Elemente aus ) auf unterscheidbare Urnen zu verteilen, wobei jede Urne nur einfach belegt werden darf (welche Urnen werden getroffen)?


Dies entspricht auch dem -fachen ungeordneten Ziehen von Elementen aus einer -elementigen Menge ohne Zurücklegen.



Zu einer Abbildung

kann man sich für die Anzahl interessieren, mit der jedes Element aus getroffen wird. Dies ist die Abbildung

Wertverteilung oder Stimmenverteilung. Wenn die Anzahl von gleich ist, so ist dabei

Abbildungen von nach mit einer bestimmten Summenanzahl





Lemma  

Es sei eine Menge mit Elementen und sei .

Dann ist die Anzahl der Abbildungen mit der Gesamtvielfachheit

gleich

Beweis  

Sei und sei die Menge aller Abbildungen von nach mit Gesamtvielfachheit . Wir behaupten, dass die Abbildung

bijektiv ist. Die Umkehrabbildung ist folgendermaßen gegeben: Zu jeder Teilmenge -elementigen Teilmenge gehört über die induzierte Ordnung eine natürliche Bijektion

( ist das kleinste Element von , u.s.w.) Damit definieren wir eine Abbildung

wobei bei die Bedingung für und gegenstandslos ist.




Wahlausgang, Treffertupel, Monome,

Dies entspricht auch dem -fachen ungeordneten Ziehen von Elementen aus einer -elementigen Menge mit Zurücklegen.









Methan Lewis.svg



Budapest-metro.png


Copenhagen Metro with City Circle Line map.svg


Planskizze Blauhöhlensystem.jpg


Plan Sophienhöhle.png



disjunkte kantenfreie Vereinigung, disjunkte vollkantige Vereinigung, Vereinigung, Durchschnitt