Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 13

In ihrer Freizeit tobt Vorli gerne mit dem Nachbarshund Jurek rum. Der arbeitet auch als Vorlesungshund, allerdings bei den Juristen. Vorli stellt sich das unglaublich langweilig vor.

In dieser Vorlesung besprechen wir Zahlen, die mit der Anzahl von Abbildungen von ${}M$ in eine ${}k$ -elementige Menge zusammenhängen, und insbesondere die Anzahl von surjektiven Abbildungen.

Die Multinomialkoeffizienten

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 Lemma 13.2 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 Lemma 13.2 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

{}{\frac {14!}{3!3!2!2!}}={\frac {14\cdot 13\cdot 12\cdot 11\cdot 10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4}{6\cdot 2\cdot 2}}=14\cdot 13\cdot 12\cdot 11\cdot 10\cdot 9\cdot 8\cdot 7\cdot 5\,

Möglichkeiten.

Die folgende Aussage heißt Multinomialsatz oder Polynomialsatz und ist eine direkte Verallgemeinerung des binomischen Lehrsatzes.

Satz

Es sei ${}R$ ein kommutativer Halbring und seien ${}x_{1},\ldots ,x_{k}\in R$ Elemente und ${}n\in \mathbb {N}$ .

Dann ist

${}{\left(x_{1}+\cdots +x_{k}\right)}^{n}=\sum _{r_{1}+\cdots +r_{k}=n}{\binom {n}{r_{1},\dotsc ,r_{k}}}x_{1}^{r_{1}}\cdots x_{k}^{r_{k}}\,.$

Beweis

Siehe Aufgabe 13.7.

\Box

Surjektive Abbildungen

Im Gegensatz zur Anzahl von injektiven oder bijektiven Abbildung zwischen endlichen Mengen ist die Anzahl von surjektiven Abbildungen nicht so einfach zu bestimmen. Es gibt mehrere Formeln bzw. Ansätze dafür, wobei weder die Beziehung untereinander unmittelbar klar ist noch, welche Formel für Berechnungen besonders geeignet sind. Es besteht aber ein unmittelbarer Zusammenhang mit der Anzahl von Partitionen, auf die wir in der nächsten Vorlesung eingehen.

Lemma

Es sei ${}A$ eine ${}n$ -elementige Menge und ${}B$ eine ${}k$ -elementige Menge.

Dann ist die Anzahl der surjektiven Abbildungen von ${}A$ nach ${}B$ gleich

$\sum _{(r_{1},\ldots ,r_{k}):\,r_{1}+r_{2}+\cdots +r_{k}=n,\,r_{j}\geq 1}{\binom {n}{r_{1},\dotsc ,r_{k}}}.$

Beweis

Dies folgt unmittelbar aus Lemma 13.2, da ja eine Abbildung genau dann surjektiv ist, wenn alle Fasern nicht leer sind, was sich in der Bedingung ${}r_{j}\geq 1$ niederschlägt.

\Box

Satz

Es sei ${}A$ eine ${}n$ -elementige Menge und ${}B$ eine ${}k$ -elementige Menge.

Dann ist die Anzahl der surjektiven Abbildungen von ${}A$ nach ${}B$ gleich

$\sum _{(a_{1},\ldots ,a_{k}):\,a_{1}+a_{2}+\cdots +a_{k}=n,\,a_{j}\geq 1}1^{a_{1}}2^{a_{2}}\cdots k^{a_{k}}.$

Beweis

Wir führen Induktion über ${}k$ und bei fixiertem ${}k$ Induktion nach ${}n$ . Bei ${}k=0$ ist die Aussage richtig. Es sei also ${}k$ fixiert und sei die Aussage für alle kleineren ${}k$ und alle ${}n$ bereits bewiesen. Für ${}n<k$ ist der Summenausdruck gleich ${}0$ , und es gibt auch keine surjektive Abbildung einer ${}n$ -elementigen Menge in eine größere Menge. Bei ${}n=k$ ist das einzige Indextupel gleich ${}(1,\ldots ,1)$ und der Summenausdruck ist gleich ${}k!$ , was mit der Anzahl der surjektiven bzw. bijektiven Abbildungen nach Satz 2.4 übereinstimmt. Es sei also die Aussage für ${}n\geq k$ bewiesen und betrachten wir eine surjektive Abbildung ${}f$ von ${}{\{1,\ldots ,n+1\}}$ nach ${}\{1,\ldots ,k\}$ . Dabei ist entweder schon die Einschränkung ${}g$ auf ${}{\{1,\ldots ,n\}}$ surjektiv oder nicht. Im ersten Fall gibt es bei gegebenem ${}g$ genau ${}k$ Möglichkeiten für ${}f$ , da ja ${}n+1$ auf eines der ${}k$ Elemente abgebildet werden kann. Im zweiten Fall, wenn ${}g$ nicht surjektiv ist, so wird durch ${}g$ genau ein Element der Bildmenge nicht getroffen, und ${}f$ muss ${}n+1$ auf dieses nicht getroffene Element abbilden, um die Surjektivität sicherzustellen. Es gibt hierbei ${}k$ Möglichkeiten, welches Element von ${}g$ nicht getroffen wird. Ferner ist ${}g$ eine surjektive Abbildung auf eine ${}k-1$ -elementige Teilmenge. Somit ist unter Verwendung der Induktionsvoraussetzung die Anzahl der surjektiven Abbildungen von ${}{\{1,\ldots ,n+1\}}$ nach ${}\{1,\ldots ,k\}$ gleich

{}{\begin{aligned}\,&={\#\left({\left\{f:{\{1,\ldots ,n+1\}}\rightarrow \{1,\ldots ,k\}\mid f{|}_{\{1,\ldots ,n\}}{\text{ surjektiv}}\right\}}\right)}+{\#\left({\left\{f:{\{1,\ldots ,n+1\}}\rightarrow \{1,\ldots ,k\}\mid f{|}_{\{1,\ldots ,n\}}{\text{ nicht surjektiv}}\right\}}\right)}\\&=k\cdot \sum _{(a_{1},\ldots ,a_{k}):\,a_{1}+a_{2}+\cdots +a_{k}=n,\,a_{j}\geq 1}1^{a_{1}}2^{a_{2}}\cdots k^{a_{k}}+k\cdot \sum _{(b_{1},\ldots ,b_{k-1}):\,b_{1}+b_{2}+\cdots +b_{k-1}=n,\,b_{j}\geq 1}1^{b_{1}}2^{b_{2}}\cdots (k-1)^{b_{k-1}}\\&=\sum _{(a_{1},\ldots ,a_{k}):\,a_{1}+a_{2}+\cdots +a_{k-1}+a_{k}+1=n+1,\,a_{j}\geq 1}1^{a_{1}}2^{a_{2}}\cdots k^{a_{k}+1}+\sum _{(b_{1},\ldots ,b_{k-1}):\,b_{1}+b_{2}+\cdots +b_{k-1}+1=n+1,\,b_{j}\geq 1}1^{b_{1}}2^{b_{2}}\cdots (k-1)^{b_{k-1}}\cdot k^{1}\\&=\sum _{(c_{1},\ldots ,c_{k}):\,c_{1}+c_{2}+\cdots +c_{k}=n+1,\,c_{j}\geq 1,\,c_{k}\geq 2}1^{c_{1}}2^{c_{2}}\cdots k^{c_{k}}+\sum _{(c_{1},\ldots ,c_{k}):\,c_{1}+c_{2}+\cdots +c_{k}=n+1,\,c_{j}\geq 1,\,c_{k}=1}1^{c_{1}}2^{c_{2}}\cdots k^{c_{k}}\\&=\sum _{(c_{1},\ldots ,c_{k}):\,c_{1}+c_{2}+\cdots +c_{k}=n+1,\,c_{j}\geq 1}1^{c_{1}}2^{c_{2}}\cdots k^{c_{k}}.\end{aligned}}

\Box

Satz

Es sei ${}A$ eine ${}n$ -elementige Menge und ${}B$ eine ${}k$ -elementige Menge.

Dann ist die Anzahl der surjektiven Abbildungen von ${}A$ nach ${}B$ gleich

$\sum _{j=0}^{k}(-1)^{k-j}{\binom {k}{j}}j^{n}.$

Beweis

Wir setzen ${}B=\{1,\ldots ,k\}$ . Zu ${}j=1,\ldots ,k$ setzen wir

{}F_{j}={\left\{f:A\rightarrow B\mid j{\text{ wird nicht getroffen unter }}f\right\}}\,.

Die Menge der nichtsurjektiven Abbildungen ist somit ${}F=\bigcup _{j=1}^{k}F_{j}$ . Zu ${}C\subseteq B$ haben die Durchschnitte

{}F_{C}=\bigcap _{j\in C}F_{j}\,

eine inhaltliche Bedeutung: Es handelt sich um alle Funktionen von ${}A$ nach ${}B\setminus C$ . Deren Anzahl ist nach Satz 2.2 gleich ${}(k-j)^{n}$ . Nach der Siebformel ist somit

{}{\begin{aligned}{\#\left(F\right)}&=\sum _{j=1}^{k}(-1)^{j+1}{\left(\sum _{C\subseteq \{1,\ldots ,k\},\,{\#\left(C\right)}=j}{\#\left(F_{C}\right)}\right)}\\&=\sum _{j=1}^{k}(-1)^{j+1}{\binom {k}{j}}(k-j)^{n}\\&=\sum _{\ell =0}^{k-1}(-1)^{k-\ell +1}{\binom {k}{\ell }}\ell ^{n}.\end{aligned}}

Die Anzahl der surjektiven Abbildungen ist daher gleich

{}{\begin{aligned}k^{n}-{\left(\sum _{\ell =0}^{k-1}(-1)^{k-\ell +1}{\binom {k}{\ell }}\ell ^{n}\right)}&=k^{n}+\sum _{\ell =0}^{k-1}(-1)^{k-\ell }{\binom {k}{\ell }}\ell ^{n}\\&=\sum _{\ell =0}^{k}(-1)^{k-\ell }{\binom {k}{\ell }}\ell ^{n}.\end{aligned}}

\Box

Beispiel

Wir bestimmen die Anzahl der surjektiven Abbildungen der fünfelementigen Menge ${}\{a,b,c,d,e\}$ in die dreielementige Menge ${}\{1,2,3\}$ mit Hilfe von Lemma 13.5, Satz 13.6 und Satz 13.7. Zur Bestimmung der Summe aus Lemma 13.5 betrachten wir zuerst die Indexmenge. Die möglichen Indextupel sind ${}(1,1,3)$ und ${}(1,2,2)$ , jeweils mit drei Permutationen. Deshalb ist die Summe gleich

{}{\begin{aligned}\sum _{(r_{1},r_{2},r_{3}):\,r_{1}+r_{2}+r_{3}=n,\,r_{j}\geq 1}{\binom {5}{r_{1},r_{2},r_{3}}}&=3\cdot {\binom {5}{3,1,1}}+3\cdot {\binom {5}{1,2,2}}\\&=3\cdot 20+3\cdot 30\\&=150.\end{aligned}}

Zur Bestimmung der Summe in Satz 13.6 betrachten wir wieder die Indextupel, wobei ähnlich wie soeben bis auf Permutationen die Summen ${}5=1+1+3=1+2+2$ möglich sind. Die zugehörigen Summanden hängen aber von den Permutationen ab. Es ist

{}{\begin{aligned}\sum _{(a_{1},a_{2},a_{3}):\,a_{1}+a_{2}+a_{3}=n,\,a_{j}\geq 1}1^{a_{1}}2^{a_{2}}3^{a_{3}}&=1^{1}\cdot 2^{1}\cdot 3^{3}+1^{1}\cdot 2^{3}\cdot 3^{1}+1^{3}\cdot 2^{1}\cdot 3^{1}+1^{1}\cdot 2^{2}\cdot 3^{2}+1^{2}\cdot 2^{1}\cdot 3^{2}+1^{2}\cdot 2^{2}\cdot 3^{1}\\&=54+24+6+36+18+12\\&=150.\end{aligned}}

Die Summe aus Satz 13.7 ist

{}\sum _{j=0}^{3}(-1)^{3-j}{\binom {3}{j}}j^{5}=-1\cdot 0^{5}+3\cdot 1^{5}-3\cdot 2^{5}+3^{5}=3-96+243=150\,.

Als Alternative zu den oben angegebenen expliziten Formeln, hinter denen jeweils eine aufwändige Summation steht, kann man mit der folgenden Rekursionsformel für die Anzahl von surjektiven Abbildugnen arbeiten. Die Grundidee hierzu wurde schon im Beweis zu Satz 13.6 verwendet.

Lemma

Zu ${}n,k\in \mathbb {N}$ bezeichne ${}\operatorname {Surj} (n,k)$ die Anzahl der surjektiven Abbildungen einer ${}n$ -elementigen Menge in eine ${}k$ -elementige Menge.