Multinomialkoeffizient/Einführung/Textabschnitt

Der Binomialkoeffizient ${}{\binom {n}{k}}$ beschreibt die Anzahl der ${}k$ -elementigen Teilmengen einer ${}n$ -elementigen Menge. Eine solche Teilmenge kann man auch auffassen als eine Zerlegung einer ${}n$ -elementigen Menge in zwei Teilmengen, von denen die eine ${}k$ und die andere ${}n-k$ Elemente besitzt, und wobei man sich die Rollen der beiden Teilmengen merkt. Man kann sich nun fragen, wie viele Möglichkeiten es gibt, eine ${}n$ -elementigen Menge in ${}k$ Teilmengen aufzuteilen, wobei die Teilmengen vorgegebene Anzahlen haben und wobei die Teilmengen durchnummeriert werden. Dies führt zum Begriff Multinomialkoeffizient.

Definition

Es sei ${}n$ eine natürliche Zahl und ${}r_{1},\ldots ,r_{k}$ natürliche Zahlen mit ${}\sum _{j=1}^{k}r_{j}=n$ . Dann nennt man

{}{\binom {n}{r_{1},\dotsc ,r_{k}}}:={\frac {n!}{r_{1}!\cdots r_{k}!}}\,

den Multinomialkoeffizienten ${}n$ über ${}r_{1},\ldots ,r_{k}$ .

Statt Multinomialkoeffizient sagt man auch Polynomialkoeffizient. Für ${}k=2$ ist dies der Binomialkoeffizient, in diesem Fall legt die erste Zahl ${}r_{1}\leq n$ durch die Bedingung ${}r_{2}=n-r_{1}$ die zweite Zahl fest. Generell legen die Zahlen ${}r_{1},\ldots ,r_{k-1}$ , deren Summe ${}\leq n$ ist, die letzte Zahl ${}r_{k}$ fest. Die Multinomialkoeffizienten besitzen eine Vielzahl an Interpretationen, zentral ist die folgende Interpretation mit Abbildungen.

Lemma

Es sei ${}A$ eine ${}n$ -elementige Menge und seien ${}(r_{1},\ldots ,r_{k})$ mit ${}\sum _{j=1}^{k}r_{j}=n$ vorgegeben.

Dann ist die Anzahl der Abbildungen ${}f$ von ${}A$ nach ${}\{1,\ldots ,k\}$ mit der Eigenschaft, dass ${}{\#\left(f^{-1}(j)\right)}=r_{j}$ für alle ${}j$ ist, gleich

${\binom {n}{r_{1},\dotsc ,r_{k}}}.$

Beweis

Für die Faser über ${}1$ gibt es ${}{\binom {n}{r_{1}}}$ Möglichkeiten, man muss ja die ${}r_{1}$ Elemente auswählen, die auf die ${}1$ gehen sollen. Wenn dies festgelegt ist, so gibt es für die Faser über ${}2$ genau ${}{\binom {n-r_{1}}{r_{2}}}$ Möglichkeiten. In diesem Sinne gibt es für die Faser über ${}j$ genau ${}{\binom {n-r_{1}-\cdots -r_{j-1}}{r_{j}}}$ Möglichkeiten. Wenn man diese Zahlen miteinander multipliziert, so ergibt sich

{}{\begin{aligned}&\,\,\,\,\,\,\,{\binom {n}{r_{1}}}{\binom {n-r_{1}}{r_{2}}}\cdots {\binom {n-r_{1}-\cdots -r_{k-2}}{r_{k-1}}}\cdot {\binom {n-r_{1}-\cdots -r_{k-1}}{r_{k}}}\\&={\frac {n\cdots (n-r_{1}+1)}{r_{1}!}}\cdot {\frac {(n-r_{1})\cdots (n-r_{1}-r_{2}+1)}{r_{2}!}}\cdots {\frac {(n-r_{1}-\cdots -r_{k-2})\cdots (n-r_{1}-\cdots -r_{k-2}-r_{k-1}+1)}{r_{k-1}!}}\cdot {\frac {(n-r_{1}-\cdots -r_{k-2}-r_{k-1})\cdots 1}{r_{k}!}}\\&={\frac {n!}{r_{1}!r_{2}!\cdots r_{k}!}},\,\end{aligned}}

also der Multinomialkoeffizient.

\Box

Durch die Bedingungen ${}r_{j}\geq 1$ für alle ${}j$ sind die surjektiven Abbildungen gekennzeichnet.

Die Multinomialkoeffizienten beschreiben also die Anzahl der Möglichkeiten, ${}n$ Elemente auf ${}k$ Ziele abzubilden, wobei das ${}j$ -te Ziel durch ${}r_{j}$ ELemente getroffen werden. Man sagt auch so: Es gibt ${}{\binom {n}{r_{1},\dotsc ,r_{k}}}$ viele Möglichkeiten, ${}n$ unterscheidbare Kugeln auf ${}k$ unterscheidbare Urnen zu verteilen derart, dass in der ersten Urne ${}r_{1}$ Kugeln, in der zweiten Urne ${}r_{2}$ Kugeln u.s.w. landen. Die entsprechende Abbildung aus Fakt ordnet jeder Kugel die Urne zu, in die sie reinkommt (Elemente in einer Menge sind stets unterscheidbar; bei Verteilungen von Kugeln auf Urnen gibt es auch nicht unterscheidbare Szenarien). Man kann auch umgekehrt aus unterscheidbaren Urnen, die jeweils eine hinreichend große Anzahl von urnenspezifischen Objekten beinhalten, eine geordnete Ziehung der Länge ${}n$ vornehmen, derart, dass aus der ${}j$ -ten Urne (also der ${}j$ -te Objekttyp) genau ${}r_{j}$ Elemente gezogen werden. Die Objekte aus der gleichen Urne müssen nicht unterschiedbar sein, dies wird durch die Ziehreihenfolge übernommen. Die entsprechende Abbildung aus Fakt ordnet der Nummer von ${}1$ bis ${}n$ die Urne bzw. den Objekttyp zu, der für diese Nummer gezogen wird. Beispielsweise ist die Anzahl der Möglichkeiten, aus einer vorgegebenen Buchstabenansammlung mit ${}k$ Buchstaben, die ${}r_{j}$ -fach vorkommen, ${}1\leq j\leq k$ , Wörter zu bilden, die genau diese Buchstaben verbrauchen, durch den Multinomialkoeffizienten ${}{\binom {n}{r_{1},\dotsc ,r_{k}}}$ gegeben. Ein Wort der Länge ${}n$ kann man direkt als eine Wertetabelle einer Abbildung von ${}{\{1,\ldots ,n\}}$ in die Buchstabenmenge auffassen.

Beispiel

Wir wollen wissen, wie viele Wörter (im Sinne von Buchstabenketten) man aus dem Wort „Homomorphismus“ bilden kann, derart, dass genau die vorgegebenen Buchstaben verwendet werden. Das Wort hat insgesamt ${}14$ Buchstaben, dabei kommen ${}m$ und ${}o$ dreimal, ${}h$ und ${}s$ zweimal und ${}r,p,i,u$ einmal vor. Somit gibt es