2018-11-05 22:30:26 +01:00
|
|
|
---
|
|
|
|
|
title: Bälle und Urnen
|
|
|
|
|
date: 2018-10-23
|
|
|
|
|
---
|
|
|
|
|
|
|
|
|
|
**Gegeben**: $n$ Bälle, $m$ Urnen
|
|
|
|
|
|
|
|
|
|
**Frage**: Wie viele Möglichkeiten gib es, diese Bälle auf die Urnen zu verteilen?
|
|
|
|
|
|
|
|
|
|
Antwort ist abhängig davon, was man genau möchte.
|
|
|
|
|
|
|
|
|
|
* Bälle/Urnen (nicht) unterscheidbar
|
|
|
|
|
* In jeder Urne höchstens ein Ball (injektiv) $\Rightarrow m \geq n$
|
|
|
|
|
* In jeder Urne mindestens ein Ball (surjektiv) $\Rightarrow n \geq m$
|
|
|
|
|
* In jeder Urne genau ein Ball (bijektiv) $\Rightarrow n = m$
|
|
|
|
|
|
|
|
|
|
Notation:
|
|
|
|
|
* $U \widehat{=}$ unterscheidbar
|
|
|
|
|
* $N \widehat{=}$ nicht unterscheidbar
|
|
|
|
|
|
|
|
|
|
| ... | beliebig | injektiv | surjektiv | bijektiv |
|
|
|
|
|
| --- | --- | --- | --- | --- |
|
|
|
|
|
| B: $U$, U: $U$ | A: $m^n$ | B: $n^{\underline{m}}$ | F: $m!s_{n,m}$ | $n! = m!$ |
|
|
|
|
|
| B: $N$, U: $U$ | D: $\binom{m+n-1}{n}$ | C: $\binom{m}{n}$ | H: $\binom{n-1}{m-1}$ | 1 |
|
|
|
|
|
| B: $U$, U: $N$ | I: $\sum\limits_{k=1}^m S_{n,k}$ | 1 | E: $S_{n,m}$ | 1 |
|
|
|
|
|
| B: $N$, U: $N$ | J: $\sum\limits_{k=1}^m P_{n,k}$ | 1 | G: $P_{n,m}$ | 1 |
|
|
|
|
|
|
|
|
|
|
Die Fälle A-D entsprechen genau den Fällen A-D beim ziehen von $n$ Elementen aus einer $m$-elementingen Menge (gezogen
|
|
|
|
|
werden Urnen für die Bälle).
|
2018-12-04 14:56:17 +01:00
|
|
|
|
|
|
|
|
**Fall E**: Betrachte die Menge der Bälle. Aufteilen auf $m$ Urnen entspricht einer (ungeordneten) $m$-Mengenpartition.
|
|
|
|
|
Also $S_{n,m}$ Möglichkeiten.
|
|
|
|
|
|
|
|
|
|
**Fall F**: Entspricht der geordneten Mengenpartition (analog zu Fall E). Davon gibt es $m! * S_{n,m}$ Möglichkeiten, da
|
|
|
|
|
es $m!$ Möglichkeiten gibt, eine ungeordnete Partition anzuordnen
|
|
|
|
|
|
|
|
|
|
**Fall G**: Es kommt nur auf die Anzahl der Bälle in den Urnen an. Damit entspricht jede Möglichkeit einer ungeordneten
|
|
|
|
|
Zahlpartition von $n$. Surjektivität bedeutet alle Summanden mindestens $1$.
|
|
|
|
|
|
|
|
|
|
**Fall H**: Entspricht den geordneten Zahlpartitionen.
|
|
|
|
|
|
|
|
|
|
**Fall I und J**: Im Gegensatz zu Fall E und G können hier Urnen leer bleiben. Wir betrachten die disjunkten Fälle, dass
|
|
|
|
|
in $k \in \{1,...,m\}$ Urnen Bälle landen.
|
