Beweis der Multinomialformel
Hier geht es, ergänzend zum Artikel über die Binomial- und die Multinomialformel, um den Beweis der Multinomialkoeffizientenrekursion und der Multinomialformel. Um die Rekursionsformel zu beweisen, werden wir zunächst eine Aussage über den Zusammenhang von Binomial- und Multinomialkoeffizienten beweisen.
Binomial- und Multinomialkoeffizienten
Wir zeigen zunächst, das zwischen Binomial- und Multinomialkoeffizienten folgender
Zusammenhang besteht:
Für natürliche Zahlen k1, ..., km,
n mit k1 + ... + km = n gilt
stets
was man durch Nachrechnen leicht bestätigt, denn man hat:
\[ \begin{eqnarray*} \prod \limits_{j=2}^m {\sum_{\nu = 1}^j k_\nu \choose \sum_{\nu = 1}^{j-1} k_\nu} &=& \prod \limits_{j=2}^m \frac{\left(\sum_{\nu = 1}^j k_\nu\right)!} {k_j!\left(\sum_{\nu = 1}^{j-1} k_\nu\right)!}\\ &=& \prod \limits_{j=2}^m \frac 1{k_j!} \cdot \prod \limits_{j=2}^m \left({\textstyle\sum_{\nu=1}^j k_\nu}\right)! \cdot \prod \limits_{j=2}^m \frac 1{\left(\sum_{\nu=1}^{j-1} k_\nu\right)!}\\ &=& \prod \limits_{j=2}^m \frac 1{k_j!} \cdot \prod \limits_{j=2}^m \left({\textstyle\sum_{\nu=1}^j k_\nu}\right)! \cdot \prod \limits_{j=1}^{m-1} \frac 1{\left(\sum_{\nu=1}^{j} k_\nu\right)!}\\ &=& \prod \limits_{j=2}^{m} \frac{1}{k_j!} \cdot \underbrace{\left(\sum_{\nu=1}^{m} k_\nu\right)!}_{=n!} \cdot \frac{1}{\left( \sum_{\nu=1}^{1}k_\nu \right)} \\ &=& \prod \limits_{j=2}^m \frac{1}{k_j!} \cdot n! \cdot \frac{1}{k_1!}\\ &=& \frac{n!}{k_1!\cdots k_m!}\\ &=& {n \choose k_1; \ldots; k_m} \end{eqnarray*} \]und das wollten wir zeigen.
zurück zum Artikel über die Multinomialformel
Multinomialkoeffizientenrekursion
Nun können wir die Rekursionsformel für Multinomialkoeffizienten beweisen. Sie besagt, dass für natürliche Zahlen n und kj, 1 <= j <= m mit 0 < kj < n und k1 + ... + km = n stets
gilt. Diese
Formel beweisen wir durch Einsetzen der Definition der Multinomialkoeffizienten und Nachrechnen:
Es seien n, kj natürliche Zahlen mit
0 < kj < n und k1 + ... + km = n,
dann gilt:
Das war aber zu zeigen.
zurück zum Artikel über die Multinomialformel
Multinomialformel
Mit Hilfe der Binomialformel, vollständiger Induktion und des Zusammenhangs von Binomial- und Multinomialkoeffizienten können wir nun die Multinomialformel beweisen, d.h. wir zeigen, dass für reelle Zahlen ai und und natürliches n stets
gilt. Seien also n und die ai für i = 1, ..., m gegeben. Wir machen Induktion nach m:
- Induktionsanfang:
Für m = 1 ist die Behauptung wahr, denn
was zu zeigen war.
- Induktionsvoraussetzung:
Es sei nun m > 1 und die Behauptung sei für m-1 bereits bewiesen, d.h. es gelte
für beliebige reelle Zahlen ai und natürliche Zahlen n.
- Induktionsschluss:
Wir erhalten unter Anwendung der Induktionsvoraussetzung, der Binomialformel und des Koeffizientenzusammenhangs, dass \[ \begin{eqnarray*} \left(\sum_{i=1}^m a_i\right)^n &=& \left(\sum_{i=1}^{m-1} a_i + a_m\right)^n\\ &=& \sum_{\kappa = 0}^n {n \choose \kappa}\left(\sum_{i=1}^{m-1} a_i \right)^\kappa a_m^{n-\kappa}\quad \mbox{Binomialformel}\\ &=& \sum_{\kappa = 0}^n {n\choose \kappa} \left(\sum_{0 \le k_1, \ldots, k_{m-1} \le \kappa \atop k_1 + \cdots + k_{m-1} = \kappa} {\kappa\choose k_1; \ldots; k_{m-1}} a_1^{k_1} \cdots a_{m-1}^{k_{m-1}}\right)a_m^{n-\kappa}\quad\mbox{Induktionsvoraussetzung}\\ &=& \sum_{\kappa = 0}^n \sum_{0 \le k_1, \ldots, k_{m-1} \le \kappa \atop k_1 + \cdots + k_{m-1} = \kappa} {n\choose \kappa} \cdot {\kappa\choose k_1; \ldots; k_{m-1}} a_1^{k_1} \cdots a_{m-1}^{k_{m-1}} a_m^{n-\kappa} \end{eqnarray*} \] Nun gilt mit dem Koeffizientenzusammenhang: \[ \begin{eqnarray*} {n \choose \kappa} \cdot {\kappa \choose k_1; \ldots ; k_{m-1}} &=& {n \choose \kappa} \cdot \prod \limits_{j=2}^{m-1} { \sum_{\nu=1}^{j} k_\nu \choose \sum_{\nu=1}^{j-1} k_\nu}\\ & & {\rm Sei} \ k_m=n-\kappa \ \ \Rightarrow \ \ n = n-\kappa+\underbrace{\sum_{i=1}^{m-1} k_i}_{=\kappa} = k_m + \sum_{i=1}^{m-1} k_i = \sum_{i=1}^{m} k_i \\ &=& { \sum_{i=1}^{m} k_i \choose \sum_{i=1}^{m-1} k_i} \cdot \prod \limits_{j=2}^{m-1} { \sum_{\nu=1}^{j} k_\nu \choose \sum_{\nu=1}^{j-1} k_\nu}\\ &=& \prod \limits_{j=2}^{m} { \sum_{\nu=1}^{j} k_\nu \choose \sum_{\nu=1}^{j-1} k_\nu}\\ &=& {n \choose k_1; \ldots ; k_{m-1} ; k_m}\\ &=& {n \choose k_1; \ldots ; k_{m-1} ; n-\kappa} \end{eqnarray*} \] Damit können wir unseren Induktionsschluss wie folgt vollenden \[ \begin{eqnarray*} \left(\sum_{i=1}^m a_i\right)^n &=& \sum_{\kappa = 0}^n \sum_{0 \le k_1, \ldots, k_{m-1} \le \kappa \atop k_1 + \cdots + k_{m-1} = \kappa} {n\choose \kappa} \cdot {\kappa\choose k_1; \ldots; k_{m-1}} a_1^{k_1} \cdots a_{m-1}^{k_{m-1}} a_m^{n-\kappa}\\ &=& \sum_{\kappa = 0}^n \sum_{0 \le k_1,\ldots, k_{m-1} \le \kappa \atop k_1 + \cdots + k_{m-1} = \kappa} {n\choose k_1; \ldots; k_{m-1}; n-\kappa} a_1^{k_1} \cdots a_{m-1}^{k_{m-1}}a_m^{n-\kappa} \quad\mbox{obige Nebenrechnung}\\ &=& \sum_{n-k_m = 0}^n \sum_{0 \le k_1,\ldots, k_{m-1} \le n-k_m \atop k_1 + \cdots + k_{m-1} = n-k_m} {n\choose k_1; \ldots; k_{m-1}; k_m} a_1^{k_1} \cdots a_{m-1}^{k_{m-1}}a_m^{k_m} \quad \mbox{mit $k_m = n-\kappa$ bzw. $\kappa = n-k_m$}\\ &=& \sum_{0 \le k_1,\ldots, k_m \le n\atop k_1 + \cdots + k_m = n} {n\choose k_1; \ldots; k_m} a_1^{k_1} \cdots a_m^{k_m} \end{eqnarray*} \] was zu zeigen war.
Den Zwischenschritt kann man auch ohne den Koeffizientenzusammenhang durch direktes Nachrechnen unter Anwendung der Definitionen zeigen: \[ \begin{eqnarray*} {n \choose \kappa} \cdot {\kappa \choose k_1; \ldots ; k_{m-1}} &=& \frac{n!}{(n-\kappa)!\cdot \kappa!} \cdot \frac{\kappa!}{k_1! \cdot k_2! \cdot \ldots \cdot k_{m-2}! \cdot k_{m-1}!}\\ &=& \frac{n!}{k_1! \cdot k_2! \cdot \ldots \cdot k_{m-1}! \cdot (n-\kappa)!}\\ &=& {n \choose k_1; \ldots ; k_{m-1}; n-\kappa} \quad \mbox{da $\kappa = \sum \limits_{i=1}^{m-1} k_i$ und $n-\kappa+\kappa=n$} \end{eqnarray*} \]
zurück zum Artikel über die Multinomialformel
