Totale Anzahl an Kombinationen (Hypergeometrische Verteilung)

01.02.2023, 13:30	Namenloser324	Auf diesen Beitrag antworten »
Totale Anzahl an Kombinationen (Hypergeometrische Verteilung) Hallo, ich habe in einer Urne Kugeln mit acht verschiedenen Farben $\begin{eqnarray} F_i \end{eqnarray}$ mit jeweils $\begin{eqnarray} n_i \end{eqnarray}$ Kugeln pro Farbe. Wenn ich nun N mal ohne zurücklegen aus der Urne ziehe, wobei die Reihenfolge der Kugeln egal ist, wie viele unterscheidbare Ziehungen gibt es? Für eine gegebene Zahl $\begin{eqnarray} k_i \end{eqnarray}$ von Ziehungen je Farbe kann ich die Kombinationsmöglichkeiten mittels der von der multivarianten hypergeometrischen Verteilung bekannten Formel $\begin{eqnarray} \binom{n_1}{k_1}\cdot \binom{n_2}{k_2}\cdot \ldots \cdot \binom{n_8}{k_8} \end{eqnarray}$ bestimmen. Jedoch habe ich trotz einiger Recherche keine Aussage über die totale der Kombinationsmöglichkeiten gefunden, d.h. keine geschlossene Form für den Ausdruck $\begin{eqnarray} \sum_{k_1,\dots, k_8 = 0, k_1+\ldots +k_8 = N}^{N} \binom{n_1}{k_1}\cdot \binom{n_2}{k_2}\cdot \ldots \cdot \binom{n_8}{k_8} \end{eqnarray}$ Kennt dafür jemand eine geschlossene Form? Das wäre super
01.02.2023, 14:58	Namenloser324	Auf diesen Beitrag antworten »
Kann erstmal gelöscht werden, muss nochmal über mein Problem nachdenken.
01.02.2023, 15:47	HAL 9000	Auf diesen Beitrag antworten »
Ich denke mal, du suchst die Anzahl der Auswahlen ohne Reihenfolge, wobei Kugeln gleicher Farbe ununterscheidbar sind. Betrachten wir daher bei insgesamt $\begin{eqnarray} r \end{eqnarray}$ verschiedenen Farben die Menge $\begin{eqnarray} M_N = \left\{ \left(k_1,\ldots,k_r\right) \mid 0\leq k_i\leq n_i~\forall i=1,\ldots,r~\wedge~ \sum_{i=1}^r k_i = N \right\} \end{eqnarray}$ so suchst du just $\begin{eqnarray} \left\|M_N\right\| \end{eqnarray}$ . Was übrigens deutlich schwerer zu berechnen ist als die von dir oben hingeschriebene Summe, denn die ist einfach $\begin{eqnarray} \sum_{ \left(k_1,\ldots,k_r\right)\in M_N} \prod_{i=1}^r \binom{n_i}{k_i} = \binom{n}{N}\qquad () \end{eqnarray}$ , dabei meine ich natürlich $\begin{eqnarray} \sum_{i=1}^r n_i = n \end{eqnarray}$ . Denn () ist nichts anderes als die Anzahl der Auswahlen, wenn man auch die Kugeln gleicher Farbe als unterscheidbar ansieht. Womit es nichts weiter ist als das Basisproblem der Auswahl von $\begin{eqnarray} N \end{eqnarray}$ aus $\begin{eqnarray} n \end{eqnarray}$ unterscheidbaren Kugeln. ----------------------------------------------------------------------------------------------- Ok, wie berechnet man das gesuchte $\begin{eqnarray} \left\| M_N\right\| \end{eqnarray}$ bei fest vorgegebenen $\begin{eqnarray} n_1,\ldots,n_r \end{eqnarray}$ und $\begin{eqnarray} N \end{eqnarray}$ ? Man betrachtet zunächst mit $\begin{eqnarray} \Omega = \left\{ \left(k_1,\ldots,k_r\right)\in\mathbb{N}_0^r ~\Bigm\|~ \sum_{i=1}^r k_i = N \right\} \end{eqnarray}$ die Menge aller solchen Anzahltupel OHNE Berücksichtigung der Restriktion $\begin{eqnarray} k_i\leq n_i \end{eqnarray}$ , und dann davon die Teilmenge $\begin{eqnarray} A_i = \left\{ \left(k_1,\ldots,k_r\right)\in\Omega ~\Bigm\|~ k_i\geq n_i+1 \right\} \end{eqnarray}$ , welche kennzeichnet, dass Anzahl $\begin{eqnarray} k_i \end{eqnarray}$ die Restriktion $\begin{eqnarray} k_i\leq n_i \end{eqnarray}$ NICHT einhält. Dann ist $\begin{eqnarray} M_N = \Omega\setminus \left( \bigcup_{i=1}^r A_i\right) \end{eqnarray}$ , und es folgt laut Siebformel $\begin{eqnarray} \left\| M_N\right\| = \sum_{J\subseteq\{1,\ldots r\}} (-1)^{\|J\|} \left\| \bigcap_{j\in J} A_j \right\|\qquad () \end{eqnarray}$ . Die Summe läuft über wirklich alle Teilmengen $\begin{eqnarray} J \end{eqnarray}$ von $\begin{eqnarray} \{1,\ldots r\} \end{eqnarray}$ , wobei vereinbarungsgemäß für die leere Indexmenge $\begin{eqnarray} J \end{eqnarray}$ dann Durchscnitt $\begin{eqnarray} \bigcap_{j\in \{\}} A_j = \Omega \end{eqnarray}$ zu setzen ist. Warum bringt einen das weiter? Nun, mit "Kombinationen mit Wiederholung" bekommt man sofort die Anzahlformel $\begin{eqnarray} \left\| \bigcap_{j\in J} A_j \right\| = \begin{cases} \binom{r-1+N-\sum\limits_{j\in J} (n_j+1)}{r-1} & \mbox{ falls }\sum\limits_{j\in J} (n_j+1)\leq N\\[2ex] 0 & \mbox{ sonst }\end{cases} \end{eqnarray}$ Insgesamt sind also in (*) maximal $\begin{eqnarray} 2^r \end{eqnarray}$ Binomialkoeffizienten zu bestimmen und einzusetzen. Sind alle $\begin{eqnarray} n_i \end{eqnarray}$ einander gleich, so vereinfacht sich Formel () zu $\begin{eqnarray} \left\| M_N\right\| = \sum_{k=0}^{\min\left\{r,\left\lfloor \frac{N}{n_1+1}\right\rfloor\right\}} (-1)^k \binom{r}{k} \binom{r-1+N-k(n_1+1)}{r-1} \end{eqnarray*}$ .

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »