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

$h_{T}\colon \{1,\ldots ,m-1\}\longrightarrow T$

(${}h_{T}(1)$ ist das kleinste Element von ${}T$, u.s.w.) Damit definieren wir eine Abbildung

$\Theta \colon {\mathfrak {P}}_{m-1}\,(\{1,\ldots ,m+\ell -1\})\longrightarrow A,\,T\longmapsto {\left(y\mapsto {\#\left({\left\{z\in \{1,\ldots ,m+\ell -1\}\mid h_{T}(y-1)<z<h_{T}(y)\right\}}\right)}\right)}.$

wobei bei die Bedingung für ${}h_{T}(0)$ und ${}h_{T}(m)$ gegenstandslos ist.

$\Box$

Wahlausgang, Treffertupel, Monome,

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

disjunkte kantenfreie Vereinigung, disjunkte vollkantige Vereinigung, Vereinigung, Durchschnitt