Übersicht zu einigen kombinatorischen Grundformeln

Erläuterungen zur Terminologie:

(K) Kombinatorische Terminologie (U) Urnenmodell: s Ziehungen aus einer Urne mit u unterscheidbaren Kugeln (S) Ziehung einer Stichprobe vom Umfang s aus einer u-elementigen Grundgesamtheit (C) Besetzungsmodell: s Chips werden auf u unterscheidbare Boxen verteilt. M = {1, ..., u} S = {1, ..., s} x ˙≡y ⇔ ∃ Permutation π auf S mit x_{i} = y_{π(i)}, i = 1, ..., s.

(K) Variationen

(S) ”geordnete” Stichprobe (C) Chips unterscheidbar (K) Kombinationen (S) ”ungeordnete Stichprobe”

(3) Chips nicht unterscheidbar

(K,S) mit Wiederholungen

(U) mit Zurücklegen

(C) beliebig viele Chips je Box

\begin{aligned}Ω_{I} & = & M^{s} \\ & = & \{(x_{1}, …, x_{s}) : ∀i x_{i} ∈ M\} \\ & ≅ & M^{S} = \{f : S → M\} \\ |Ω_{I}| & = & u^{s} \end{aligned} \begin{aligned}Ω_{IV} & = & M^{s}/ ˙≡ \\ & ≅ & \{x ∈ M^{s} : x_{1} ≤ ... ≤ x_{s}\} \\ & ≅ & \{φ : M → \{0, …, s\} : \\ & & ∑_{x∈M} φ(x) = s\} \\ |Ω_{IV}| & = & \binom{s + u − 1}{s} \end{aligned}

(K,S) ohne Wiederholungen

(U) ohne Zurücklegen

(C) ≤ 1 Chip je Box

Ω_{II} = M̃^{s}
:= {x ∈ M^{s} : i ≠ j → x_{i} ≠ x_{j}}
≅ {f ∈ M^{S} : f injektiv}

|Ω_{II}| = (u)_{s}

\begin{aligned}Ω_{III} & = & M̃^{s}/ ˙≡ \\ & ≅ & \{x ∈ M^{s} : x_{1} < ... < x_{s}\} \\ & ≅ & \{φ : M → \{0, 1\} : \\ & & ∑_{x∈M} φ(x) = s\} \\ |Ω_{III}| & = & \binom{u}{s} \end{aligned}