Benutzer:Bocardodarapti/Arbeitsseite/Diskrete Mathematik

Kugel und Urnen

unterscheidbar, ununterscheidbar.

unterscheidbar durchnummeriert ; Vorgang hintereinander

Abbildungsanzahl

Lemma

Es seien ${}L$ und ${}M$ endliche Mengen mit ${}\ell$ bzw. ${}m$ Elementen.

Dann gibt es ${}m^{\ell }$ Abbildungen von ${}L$ nach ${}M$ .

Diese Anzahl entspricht der Anzahl der Möglichkeiten, ${}\ell$ unterscheidbare Kugeln (die Elemente aus ${}L$ ) auf ${}m$ unterscheidbare Urnen zu verteilen.

Dies entspricht auch dem ${}\ell$ -fachen geordneten Ziehen von Elementen aus einer ${}m$ -elementigen Menge mit Zurücklegen.

Lemma

Es seien ${}L$ und ${}M$ endliche Mengen mit ${}\ell$ bzw. ${}m$ Elementen mit ${}\ell \leq m$ .

Dann gibt es ${}m(m-1)(m-2)\cdots (m-\ell +1)$ injektive Abbildungen von ${}L$ nach ${}M$ .

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

Dies entspricht auch dem ${}\ell$ -fachen geordneten Ziehen von Elementen aus einer ${}m$ -elementigen Menge ohne Zurücklegen.

Lemma

Es sei ${}L$ eine ${}\ell$ -elementige Menge und ${}M$ eine ${}m$ -elementige Menge.

Dann ist die Anzahl der surjektiven Abbildungen von ${}L$ nach ${}M$ gleich ${}m!S({\ell },{m})$ .

Diese Anzahl entspricht der Anzahl der Möglichkeiten, ${}\ell$ unterscheidbare Kugeln (die Elemente aus ${}L$ ) auf ${}m$ unterscheidbare Urnen zu verteilen, wobei jede Urne belegt werden muss.

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

Lemma

Die Stirlingsche Zahl zweiter Art ${}S({n},{k})$

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

Lemma

Die Anzahl der ${}\ell$ -elementigen Teilmengen in einer ${}m$ -elementigen Menge ist

${\frac {m!}{\ell !(m-\ell )!}}.$

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

Dies entspricht auch dem ${}\ell$ -fachen ungeordneten Ziehen von Elementen aus einer ${}m$ -elementigen Menge ohne Zurücklegen.

Zu einer Abbildung

f\colon L\longrightarrow M

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

\theta \colon M\longrightarrow \mathbb {N} ,\,y\longmapsto {\#\left(f^{-1}(y)\right)}.

Wertverteilung oder Stimmenverteilung. Wenn die Anzahl von ${}L$ gleich ${}\ell$ ist, so ist dabei

{}\sum _{y\in M}{\#\left(f^{-1}(y)\right)}=\ell \,.

Abbildungen von ${}M$ nach ${}\mathbb {N}$ mit einer bestimmten Summenanzahl

Lemma

Es sei ${}M$ eine Menge mit ${}m$ Elementen und sei ${}\ell \in \mathbb {N}$ .

Dann ist die Anzahl der Abbildungen ${}g\colon M\rightarrow \mathbb {N}$ mit der Gesamtvielfachheit

${}\sum _{y\in M}g(y)=\ell \,$

gleich

{}{\binom {m+\ell -1}{m}}={\binom {m+\ell -1}{\ell -1}}\,.

Beweis

Sei ${}M=\{1,2,\ldots ,m\}$ und sei ${}A$ die Menge aller Abbildungen von ${}M$ nach ${}\mathbb {N}$ mit Gesamtvielfachheit ${}\ell$ . Wir behaupten, dass die Abbildung

\Psi \colon A\longrightarrow {\mathfrak {P}}_{m-1}\,(\{1,\ldots ,m+\ell -1\}),\,g\longmapsto \{(g(1)+1,g(1)+g(2)+2,g(1)+g(2)+g(3)+3,\ldots ,g(1)+g(2)+g(3)+\cdots +g(m-1)+m-1\}

bijektiv ist. Die Umkehrabbildung ist folgendermaßen gegeben: Zu jeder Teilmenge ${}m-1$ -elementigen Teilmenge ${}T\subseteq \{1,\ldots ,m+\ell -1\}$ gehört über die induzierte Ordnung eine natürliche Bijektion