Endliche Mengen/Surjektive Abbildungen/Anzahl/Einführung/Textabschnitt

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 Fakt, 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 Fakt ü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 Fakt 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 Fakt, Fakt und Fakt. Zur Bestimmung der Summe aus Fakt 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 Fakt 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 Fakt 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 Fakt 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.

Dann gilt die Rekursionsformel

${}\operatorname {Surj} (n+1,k)=k\cdot \operatorname {Surj} (n,k)+k\cdot \operatorname {Surj} (n,k-1)\,.$

Beweis

Siehe Aufgabe.

$\Box$