Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 13/latex
\setcounter{section}{13}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Waeller11.jpg} }
\end{center}
\bildtext {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.} }
\bildlizenz { Waeller11.jpg } {} {Odatrulle} {Commons} {CC-by-sa 4.0} {}
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.
\zwischenueberschrift{Die Multinomialkoeffizienten}
Der
\definitionsverweis {Binomialkoeffizient}{}{}
\mathl{\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.
\inputdefinition
{}
{
Es sei $n$ eine natürliche Zahl und
\mathl{r_1 , \ldots , r_k}{} natürliche Zahlen mit
\mavergleichskette
{\vergleichskette
{ \sum_{j = 1}^k r_j
}
{ = }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann nennt man
\mavergleichskettedisp
{\vergleichskette
{ { \binom { n } { r_1 , \dotsc, r_k } }
}
{ \defeq} { { \frac{ n! }{ r_1! \cdots r_k! } }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
den
\definitionswort {Multinomialkoeffizienten}{}
$n$ über
\mathl{r_1 , \ldots , r_k}{.}
}
Statt Multinomialkoeffizient sagt man auch \stichwort {Polynomialkoeffizient} {.} Für
\mavergleichskette
{\vergleichskette
{k
}
{ = }{2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist dies der Binomialkoeffizient, in diesem Fall legt die erste Zahl
\mavergleichskette
{\vergleichskette
{r_1
}
{ \leq }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
durch die Bedingung
\mavergleichskette
{\vergleichskette
{r_2
}
{ = }{n-r_1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die zweite Zahl fest. Generell legen die Zahlen
\mathl{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.
\inputfaktbeweis
{Endliche Mengen/Abbildung/Faseranzahl/Multinomialkoeffizienten/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $A$ eine $n$-elementige Menge und seien
\mathl{(r_1 , \ldots , r_k)}{} mit
\mavergleichskette
{\vergleichskette
{\sum_{j = 1}^k r_j
}
{ = }{ n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
vorgegeben.}
\faktfolgerung {Dann ist die Anzahl der Abbildungen $f$ von $A$ nach
\mathl{\{ 1 , \ldots , k \}}{} mit der Eigenschaft, dass
\mavergleichskette
{\vergleichskette
{ { \# \left( f^{-1} (j) \right) }
}
{ = }{r_j
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für alle $j$ ist, gleich
\mathdisp {{ \binom { n } { r_1 , \dotsc, r_k } }} { . }
}
\faktzusatz {}
\faktzusatz {}
}
{
Für die Faser über $1$ gibt es
\mathl{\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
\mathl{\binom { n-r_1 } { r_2 }}{} Möglichkeiten. In diesem Sinne gibt es für die Faser über $j$ genau
\mathl{\binom { n-r_1- \cdots - r_{j-1} } { r_j }}{} Möglichkeiten. Wenn man diese Zahlen miteinander multipliziert, so ergibt sich
\mavergleichskettealigndrucklinks
{\vergleichskettealigndrucklinks
{ \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! } }
}
{ } {
}
{ } {
}
}
{}{}{,}
also der Multinomialkoeffizient.
Durch die Bedingungen
\mavergleichskette
{\vergleichskette
{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
\mathl{{ \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
\zusatzklammer {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
\zusatzklammer {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
\mathkor {} {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,
\mavergleichskette
{\vergleichskette
{1
}
{ \leq }{j
}
{ \leq }{k
}
{ }{
}
{ }{
}
}
{}{}{,}
Wörter zu bilden, die genau diese Buchstaben verbrauchen, durch den Multinomialkoeffizienten
\mathl{{ \binom { n } { r_1 , \dotsc, r_k } }}{} gegeben. Ein Wort der Länge $n$ kann man direkt als eine Wertetabelle einer Abbildung von
\mathl{{ \{ 1 , \ldots , n \} }}{} in die Buchstabenmenge auffassen.
\inputbeispiel{}
{
Wir wollen wissen, wie viele Wörter
\zusatzklammer {im Sinne von Buchstabenketten} {} {}
man aus dem Wort \anfuehrung{Homomorphismus}{} bilden kann, derart, dass genau die vorgegebenen Buchstaben verwendet werden. Das Wort hat insgesamt $14$ Buchstaben, dabei kommen $m$ und $o$ dreimal,
\mathkor {} {h} {und} {s} {}
zweimal und
\mathl{r,p,i,u}{} einmal vor. Somit gibt es
\mavergleichskettedisp
{\vergleichskette
{{ \frac{ 14! }{ 3! 3! 2! 2! } }
}
{ =} { { \frac{ 14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot7 \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 \stichwort {Multinomialsatz} {} oder \stichwort {Polynomialsatz} {} und ist eine direkte Verallgemeinerung des binomischen Lehrsatzes.
{Kommutativer Halbring/Multinomialsatz/Fakt}
{Satz}
{}
{
\faktsituation {Es sei $R$ ein
\definitionsverweis {kommutativer Halbring}{}{}
und seien
\mavergleichskette
{\vergleichskette
{x_1 , \ldots , x_k
}
{ \in }{R
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
Elemente und
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}}
\faktfolgerung {Dann ist
\mavergleichskettedisp
{\vergleichskette
{ { \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}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}}
\faktzusatz {}
\faktzusatz {}
{ Siehe Aufgabe 13.7. }
\zwischenueberschrift{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.
\inputfaktbeweis
{Endliche Mengen/Surjektive Abbildungen/Summe der Multinomialkoeffizienten/Nichtleer/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $A$ eine $n$-elementige Menge und $B$ eine $k$-elementige Menge.}
\faktfolgerung {Dann ist die Anzahl der
\definitionsverweis {surjektiven Abbildungen}{}{}
von $A$ nach $B$ gleich
\mathdisp {\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 } }} { . }
}
\faktzusatz {}
\faktzusatz {}
}
{
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
\mavergleichskette
{\vergleichskette
{r_j
}
{ \geq }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
niederschlägt.
\inputfaktbeweis
{Endliche Mengen/Surjektive Abbildungen/Produktpotenzen/Summe/Fakt}
{Satz}
{}
{
\faktsituation {Es sei $A$ eine $n$-elementige Menge und $B$ eine $k$-elementige Menge.}
\faktfolgerung {Dann ist die Anzahl der
\definitionsverweis {surjektiven Abbildungen}{}{}
von $A$ nach $B$ gleich
\mathdisp {\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}} { . }
}
\faktzusatz {}
\faktzusatz {}
}
{
Wir führen Induktion über $k$ und bei fixiertem $k$ Induktion nach $n$. Bei
\mavergleichskette
{\vergleichskette
{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
\mavergleichskette
{\vergleichskette
{n
}
{ < }{k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist der Summenausdruck gleich $0$, und es gibt auch keine surjektive Abbildung einer $n$-elementigen Menge in eine größere Menge. Bei
\mavergleichskette
{\vergleichskette
{n
}
{ = }{k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist das einzige Indextupel gleich
\mathl{(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
\mavergleichskette
{\vergleichskette
{n
}
{ \geq }{k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
bewiesen und betrachten wir eine surjektive Abbildung $f$ von
\mathl{{\{ 1 , \ldots , n +1 \} }}{} nach
\mathl{\{ 1 , \ldots , k \}}{.} Dabei ist entweder schon die Einschränkung $g$ auf
\mathl{{ \{ 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
\mathl{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
\mathl{{\{ 1 , \ldots , n +1 \} }}{} nach
\mathl{\{ 1 , \ldots , k \}}{} gleich
\mavergleichskettealignhandlinks
{\vergleichskettealignhandlinks
{ \,
}
{ =} { { \# \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}
}
}
{
\vergleichskettefortsetzungalign
{ =} { \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}
}
{ } {}
{ } {}
{ } {}
}
{}{.}
\inputfaktbeweis
{Endliche Mengen/Surjektive Abbildungen/Siebformel/Fakt}
{Satz}
{}
{
\faktsituation {Es sei $A$ eine $n$-elementige Menge und $B$ eine $k$-elementige Menge.}
\faktfolgerung {Dann ist die Anzahl der
\definitionsverweis {surjektiven Abbildungen}{}{}
von $A$ nach $B$ gleich
\mathdisp {\sum_{j = 0}^k (-1)^{k-j} \binom { k } { j } j^n} { . }
}
\faktzusatz {}
\faktzusatz {}
}
{
Wir setzen
\mavergleichskette
{\vergleichskette
{B
}
{ = }{ \{ 1 , \ldots , k \}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Zu
\mavergleichskette
{\vergleichskette
{j
}
{ = }{ 1 , \ldots , k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
setzen wir
\mavergleichskettedisp
{\vergleichskette
{F_j
}
{ =} { { \left\{ f:A \rightarrow B \mid j \text{ wird nicht getroffen unter } f \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Die Menge der nichtsurjektiven Abbildungen ist somit
\mavergleichskette
{\vergleichskette
{ F
}
{ = }{ \bigcup_{j = 1}^k F_j
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Zu
\mavergleichskette
{\vergleichskette
{C
}
{ \subseteq }{B
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
haben die Durchschnitte
\mavergleichskettedisp
{\vergleichskette
{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
\mathl{(k-j)^n}{.} Nach
der Siebformel
ist somit
\mavergleichskettealign
{\vergleichskettealign
{ { \# \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
}
{ } {
}
}
{}
{}{.}
Die Anzahl der surjektiven Abbildungen ist daher gleich
\mavergleichskettealignhandlinks
{\vergleichskettealignhandlinks
{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
}
{ } {
}
{ } {
}
}
{}
{}{.}
\inputbeispiel{}
{
Wir bestimmen die Anzahl der
\definitionsverweis {surjektiven Abbildungen}{}{}
der fünfelementigen Menge
\mathl{\{a,b,c,d,e\}}{} in die dreielementige Menge
\mathl{\{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
\mathkor {} {(1,1,3)} {und} {(1,2,2)} {,}
jeweils mit drei Permutationen. Deshalb ist die Summe gleich
\mavergleichskettealignhandlinks
{\vergleichskettealignhandlinks
{ \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
}
{ } {
}
}
{}
{}{.}
Zur Bestimmung der Summe in
Satz 13.6
betrachten wir wieder die Indextupel, wobei ähnlich wie soeben bis auf Permutationen die Summen
\mavergleichskette
{\vergleichskette
{5
}
{ = }{1+1+3
}
{ = }{ 1+2+2
}
{ }{
}
{ }{
}
}
{}{}{}
möglich sind. Die zugehörigen Summanden hängen aber von den Permutationen ab. Es ist
\mavergleichskettealignhandlinks
{\vergleichskettealignhandlinks
{\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
}
{ } {
}
}
{}
{}{.}
Die Summe aus
Satz 13.7
ist
\mavergleichskettedisp
{\vergleichskette
{ \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.
{Endliche Mengen/Surjektive Abbildungen/Rekursionsformel/Fakt}
{Lemma}
{}
{
\faktsituation {Zu
\mavergleichskette
{\vergleichskette
{n,k
}
{ \in }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
bezeichne
\mathl{\operatorname{Surj}(n,k)}{} die Anzahl der
\definitionsverweis {surjektiven Abbildungen}{}{}
einer $n$-elementigen Menge in eine $k$-elementige Menge.}
\faktfolgerung {Dann gilt die Rekursionsformel
\mavergleichskettedisp
{\vergleichskette
{ \operatorname{Surj}(n+1,k)
}
{ =} {k \cdot \operatorname{Surj}(n,k) + k \cdot \operatorname{Surj}(n,k-1)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}}
\faktzusatz {}
\faktzusatz {}
{ Siehe Aufgabe 13.16. }