Kurs:Grundkurs Mathematik (Osnabrück 2018-2019)/Teil I/Vorlesung 13/latex
\setcounter{section}{13}
\zwischenueberschrift{Elementare Kombinatorik}
In dieser Vorlesung beschäftigen wir uns mit elementarer Kombinatorik, dabei ist ein wichtiges Ziel, die Binomialkoeffizienten einzuführen, um die allgemeine binomische Formel formulieren und beweisen zu können. Die Kombinatorik beschäftigt sich mit dem systematischen Abzählen
\zusatzklammer {Anzahl bestimmen} {} {}
von endlichen Mengen. Zwei wichtige Prinzipien haben wir schon kennengelernt, nämlich das Additivitätsprinzip für disjunkte Mengen
\zusatzklammer {Satz 8.14} {} {}
und das Multiplikativitätsprinzip für Produktmengen
\zusatzklammer {Satz 9.6} {} {.}
In der folgenden Aussage bezeichnen wir zu einer Abbildung
\maabbdisp {f} {L} {M
} {}
zu
\mavergleichskette
{\vergleichskette
{ y
}
{ \in }{ M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Menge
\mavergleichskettedisp
{\vergleichskette
{ f^{-1} (y)
}
{ \defeq} { { \left\{ x \in L \mid f(x) = y \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
als \stichwort {Urbildmenge} {} zu $y$.
\inputfaktbeweis
{Endliche Mengen/Abbildung/Faseranzahl/Fakt}
{Satz}
{}
{
\faktsituation {Es seien
\mathkor {} {L} {und} {M} {}
\definitionsverweis {endliche Mengen}{}{}
und es sei
\maabbdisp {f} {L} {M
} {}
eine
\definitionsverweis {Abbildung}{}{.}}
\faktfolgerung {Dann gilt
\mavergleichskettedisp
{\vergleichskette
{ { \# \left( L \right) }
}
{ =} { \sum_{ y \in M} { \# \left( f^{-1} (y) \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Da jedes Element
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{L
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
auf genau ein Element aus $M$ abgebildet wird, liegt eine disjunkte Vereinigung
\mavergleichskettedisp
{\vergleichskette
{L
}
{ =} { \biguplus_{y \in M} f^{-1} (y)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
vor. Nach
Satz 8.14
ist daher die Gesamtanzahl der Menge gleich der Summe der Anzahlen der disjunkten Teilmengen.
\zwischenueberschrift{Die Fakultät}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {E L Kirchner Variete.jpg} }
\end{center}
\bildtext {Dieses Tanzpaar hat sich schon gefunden. Für die verbliebenen Personen gibt es insgesamt noch
\mathl{(n-1)!}{} Möglichkeiten (Gemälde von Ernst Ludwig Kirchner).} }
\bildlizenz { E L Kirchner Variete.jpg } {Ernst Ludwig Kirchner} {} {Commons} {gemeinfrei} {}
Bei einem Tanzkurs mit $n$ Damen und $n$ Herren gilt heute beim Schneewalzer Damenwahl, wobei die Damen in der Reihenfolge ihrer Sitzordnung wählen dürfen. Die erste Dame hat $n$ Wahlmöglichkeiten, die zweite $n-1$ Möglichkeiten, die dritte $n-2$ Möglichkeiten, u.s.w., die vorletze Dame hat noch zwei Möglichkeiten und für die letzte Dame verbleibt eine Möglichkeit\zusatzfussnote {Man könnte sich daran stören, dass man von Möglichkeiten spricht, obwohl nur eine Möglichkeit da ist, also keine echte Wahlmöglichkeit besteht. Mathematisch ist das aber die einzig sinnvolle Interpretation; eine Möglichkeit als keine Möglichkeit zu zählen würde alles durcheinander bringen} {.} {.}
\inputdefinition
{}
{
Zu einer natürlichen Zahl $n$ nennt man die Zahl
\mavergleichskettedisp
{\vergleichskette
{n!
}
{ \defeq} { n(n-1)(n-2) \cdots 3 \cdot 2 \cdot 1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
die \definitionswort {Fakultät}{} von $n$
\zusatzklammer {sprich $n$ Fakultät} {} {.}
}
Es ist
\mavergleichskette
{\vergleichskette
{(n+1)!
}
{ = }{(n+1)(n!)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Man setzt
\mavergleichskette
{\vergleichskette
{0!
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Für kleine $n$ erhält man die folgende Wertetabelle.
\wertetabelleelfausteilzeilen { $n$ }
{\mazeileundfuenf {0} {1} {2} {3} {4} }
{\mazeileunddrei {5} {6} {7} }
{\mazeileunddrei {8} {9} {10} }
{ $n!$ }
{\mazeileundfuenf {1} {1} {2} {6} {24} }
{\mazeileunddrei {120} {720} {5040} }
{\mazeileunddrei {40320} {362880} {3628800} }
\inputfaktbeweis
{Endliche Menge/Permutationen/Fakultät/Fakt}
{Lemma}
{}
{
\faktsituation {Auf einer
\definitionsverweis {endlichen Menge}{}{}
$M$ mit $n$ Elementen}
\faktfolgerung {gibt es $n!$
\definitionsverweis {bijektive Abbildungen}{}{}
von $M$ nach $M$.}
\faktzusatz {}
\faktzusatz {}
}
{
Wir zeigen etwas allgemeiner, dass es zwischen zwei endlichen Mengen
\mathkor {} {M} {und} {N} {,}
die beide $n$ Elemente besitzen, $n!$ bijektive Abbildungen gibt. Dies zeigen wir durch Induktion nach $n$, wobei der Fall\zusatzfussnote {Man kann auch bei
\mavergleichskettek
{\vergleichskettek
{ n
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
beginnen, dann geht es um die Anzahl der Abbildungen von einer leeren Menge in eine leere Menge. Da gibt es in der Tat eine Abbildung, nämlich die leere Abbildung, was auch der Grund ist, warum man
\mavergleichskettek
{\vergleichskettek
{ 0!
}
{ = }{ 1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
setzt} {.} {}
\mavergleichskette
{\vergleichskette
{n
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
klar ist. Die Aussage sei nun für $n$ schon bewiesen und es liegen zwei
\mathl{(n+1)}{-}elementige Mengen
\mathkor {} {M} {und} {N} {}
vor. Es sei
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein fixiertes Element. Dann gibt es für die Bilder
\mathl{\varphi(x)}{} genau
\mathl{n+1}{} Möglichkeiten, nämlich die Anzahl der Menge $N$. Wenn dies festgelegt ist, so entsprechen die bijektiven Abbildungen von $M$ nach $N$ mit
\mavergleichskettedisp
{\vergleichskette
{\varphi(x)
}
{ =} {y
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
den bijektiven Abbildungen von
\mathl{M \setminus \{x\}}{} nach
\mathl{N \setminus \{y\}}{.} Nach Induktionsvoraussetzung gibt es $n!$ solche bijektiven Abbildungen. Daher ist die Anzahl der bijektiven Abbildungen zwischen
\mathkor {} {M} {und} {N} {}
gleich
\mavergleichskettedisp
{\vergleichskette
{(n+1) \cdot n!
}
{ =} { (n+1)!
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Gleichbedeutend damit ist, dass es $n!$ Möglichkeiten gibt, $n$ Objekte auf $n$ Plätze zu verteilen, oder $n!$ Möglichkeiten, eine Menge von $n$ Objekten abzuzählen
\zusatzklammer {durchzunummerieren} {} {.}
\inputbeispiel{}
{
Wir möchten eine vollständige Liste von allen
\definitionsverweis {bijektiven Abbildungen}{}{}
von der Menge
\mathl{\{1,2,3\}}{} in die Menge
\mathl{\{a,b,c\}}{} in der Form von Wertetabellen angeben. Wegen
\mavergleichskettedisp
{\vergleichskette
{ 3!
}
{ =} { 3 \cdot 2 \cdot 1
}
{ =} { 6
}
{ } {
}
{ } {
}
}
{}{}{}
gibt es sechs solche Abbildungen. Es gibt keine natürliche Reihenfolge dieser Abbildungen, dennoch kann man hier mehr oder weniger systematisch vorgehen. Beispielsweise kann man den Wert an der Stelle $1$ zuerst festlegen und dann die möglichen Kombinationen für
\mathkor {} {2} {und} {3} {}
durchgehen. Dies führt auf die folgenden Wertetabellen.
\wertetabelledreiausteilzeilen { $x$ }
{\mazeileunddrei {1} {2} {3} }
{ $\varphi_1 (x)$ }
{\mazeileunddrei {a} {b} {c} }
\wertetabelledreiausteilzeilen { $x$ }
{\mazeileunddrei {1} {2} {3} }
{ $\varphi_2 (x)$ }
{\mazeileunddrei {a} {c} {b} }
\wertetabelledreiausteilzeilen { $x$ }
{\mazeileunddrei {1} {2} {3} }
{ $\varphi_3 (x)$ }
{\mazeileunddrei {b} {a} {c} }
\wertetabelledreiausteilzeilen { $x$ }
{\mazeileunddrei {1} {2} {3} }
{ $\varphi_4 (x)$ }
{\mazeileunddrei {b} {c} {a} }
\wertetabelledreiausteilzeilen { $x$ }
{\mazeileunddrei {1} {2} {3} }
{ $\varphi_5 (x)$ }
{\mazeileunddrei {c} {a} {b} }
\wertetabelledreiausteilzeilen { $x$ }
{\mazeileunddrei {1} {2} {3} }
{ $\varphi_6 (x)$ }
{\mazeileunddrei {c} {b} {a} }
}
\zwischenueberschrift{Die Binomialkoeffizienten}
\inputfaktbeweis
{Binomialkoeffizient/Explizit/Teilmengenanzahl/Fakt}
{Satz}
{}
{
\faktsituation {}
\faktvoraussetzung {Die Anzahl der $k$-elementigen Teilmengen in einer $n$-elementigen Menge ist}
\faktfolgerung {
\mathdisp {{ \frac{ n! }{ k! (n-k)! } }} { . }
}
\faktzusatz {}
\faktzusatz {}
}
{
Es sei $M$ eine $n$-elementige Menge und
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine $k$-elementige Teilmenge. Wir betrachten die Menge aller bijektiven Abbildungen
\maabbdisp {} {{ \{ 1 , \ldots , n \} }} {M
} {,}
die zusätzlich
\mathl{\{1 , \ldots , k\}}{} auf $T$ und
\zusatzklammer {deshalb} {} {}
\mathl{\{k+1 , \ldots , n\}}{} auf
\mathl{M \setminus T}{} abbilden. Nach
Lemma 13.3
und nach
Satz 9.6
gibt es
\mathl{k! \cdot (n-k)!}{} solche Abbildungen. Insgesamt gibt es $n!$ bijektive Abbildungen von
\mathl{{ \{ 1 , \ldots , n \} }}{} nach $M$. Daher ist
\mavergleichskettedisp
{\vergleichskette
{ { \left( \text{Anzahl der } k\text{-elementigen Teilmengen von } M \right) } \cdot k! \cdot (n-k)!
}
{ =} { n!
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Insbesondere ist
\mathl{k! \cdot (n-k)!}{} ein
\definitionsverweis {Teiler}{}{}
von $n!$ und es ist
\mathdisp {{ \frac{ n! }{ k! (n-k)! } }} { }
die Anzahl der $k$-elementigen Teilmengen von $M$.
Der Satz beinhaltet, dass
\mathl{k! (n-k)!}{} ein Teiler von $n!$ ist und somit ist der Bruch
\mathl{{ \frac{ n! }{ k! (n-k)! } }}{} eine natürliche Zahl. Diese bekommt einen eigenen Namen und ein eigenes Symbol.
\inputdefinition
{}
{
Es seien
\mathkor {} {k} {und} {n} {}
natürliche Zahlen mit
\mavergleichskette
{\vergleichskette
{k
}
{ \leq }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann nennt man
\mavergleichskettedisp
{\vergleichskette
{ \binom { n } { k }
}
{ \defeq} {{ \frac{ n ! }{ k ! ( n - k)! } }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
den \definitionswort {Binomialkoeffizienten}{} \anfuehrung{$n$ über $k$ }{.}
}
\inputbemerkung
{}
{
Für die
\definitionsverweis {Binomialkoeffizienten}{}{}
gilt die Regel
\mavergleichskettedisp
{\vergleichskette
{ \binom { n } { k }
}
{ =} { \binom { n } { n-k }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
wie unmittelbar aus der Definition folgt. Dies kann man sich auch mit Hilfe von
Satz 13.6
klar machen. Die Komplementabbildung
\maabbeledisp {} { \mathfrak {P} \, (M ) } { \mathfrak {P} \, (M )
} {T} { \complement T
} {,}
auf einer $n$-elementigen Menge $M$ ist
\definitionsverweis {bijektiv}{}{}
und bildet $k$-elementige Teilmengen auf
\mathl{(n-k)}{-}elementige Teilmengen ab.
}
Den Binomialkoeffizienten
\mathl{\binom { n } { k }}{} kann man auch als
\mavergleichskettealignhandlinks
{\vergleichskettealignhandlinks
{ \binom { n } { k }
}
{ =} { { \frac{ n! }{ k! (n-k)! } }
}
{ =} { { \frac{ n\cdot (n-1) \cdot (n-2) \cdots (n-k+2) (n-k+1)\cdot(n-k)\cdot (n-k-1) \cdots 2 \cdot 1 }{ ( k\cdot(k-1) \cdot(k-2) \cdots 2 \cdot 1 ) \cdot ( (n-k)\cdot (n-k-1) \cdots 2 \cdot 1 ) } }
}
{ =} { { \frac{ n\cdot(n-1)\cdot (n-2) \cdots (n-k+2)\cdot(n-k+1) }{ k\cdot(k-1)\cdot (k-2) \cdots 2 \cdot 1 } }
}
{ } {
}
}
{}
{}{}
schreiben, da die Faktoren aus
\mathl{(n-k)!}{} auch in $n!$ vorkommen und daher kürzbar sind. In dieser Darstellung stehen im Zähler und im Nenner gleich viele Faktoren. Gelegentlich ist es sinnvoll, auch negative $k$ oder
\mavergleichskette
{\vergleichskette
{k
}
{ > }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
zuzulassen und in diesen Fällen die Binomialkoeffizienten gleich $0$ zu setzen. Dies passt zur Interpretation in
Satz 13.6.
\inputbeispiel{}
{
In der vierelementigen Menge
\mathl{\{a,b,c,d\}}{} gibt es
\mavergleichskettedisp
{\vergleichskette
{ \binom { 4 } { 2 }
}
{ =} { { \frac{ 4 \cdot 3 }{ 2 \cdot 1 } }
}
{ =} { 6
}
{ } {
}
{ } {
}
}
{}{}{}
zweielementige Teilmengen. Diese sind
\mathdisp {\{a,b\}, \{a,c\}, \{a,d\},\{b,c\}, \{b,d\},\{c,d\}} { . }
}
\inputbeispiel{}
{
In einer $49$-elementigen Menge gibt es genau
\mavergleichskettedisp
{\vergleichskette
{ \binom { 49 } { 6 }
}
{ =} { { \frac{ 49 \cdot 48 \cdot 47 \cdot 46 \cdot 45 \cdot 44 }{ 6 \cdot 5 \cdot 4 \cdot 3 \cdot2\cdot 1 } }
}
{ =} { 13 983 816
}
{ } {
}
{ } {
}
}
{}{}{}
$6$-elementige Teilmengen. Es gibt also so viele mögliche Zahlenkombinationen beim Lotto \anfuehrung{Sechs aus 49 }{.} Der Kehrwert von dieser Zahl ist die Wahrscheinlichkeit, beim Lotto sechs Richtige zu haben. Es werden dabei die Teilmengen gezählt, nicht die möglichen Ziehreihenfolgen. Die Anzahl der möglichen Ziehreihenfolgen ist
\mathdisp {49 \cdot 48 \cdot 47 \cdot 46 \cdot 45 \cdot 44} { , }
zu jeder sechselementigen Teilmenge gibt es
\mathl{6!}{} mögliche Ziehreihenfolgen die auf diese Teilmenge führen.
}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Pascal_triangle.svg} }
\end{center}
\bildtext {Das \stichwort {Dreieck der Binomialkoeffizienten} {} war in Indien und in Persien schon um 1000 bekannt,} }
\bildlizenz { Pascal triangle.svg } {} {Kazukiokumura} {Commons} {CC-by-sa 3.0} {}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Yanghui_triangle.gif} }
\end{center}
\bildtext {in China heißt es \stichwort {Yanghui-Dreieck} {}
\zusatzklammer {nach Yang Hui (um 1238-1298)} {} {,}} }
\bildlizenz { Yanghui triangle.gif } {} {Noe} {Commons} {PD} {}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {TrianguloPascal.jpg} }
\end{center}
\bildtext {in Europa heißt es das \stichwort {Pascalsche Dreieck} {}
\zusatzklammer {nach Blaise Pascal (1623-1662)} {} {.}} }
\bildlizenz { TrianguloPascal.jpg } {Pascal} {Drini} {Commons} {PD} {}
\inputfaktbeweis
{Binomialkoeffizient/Summe in Pascaldreieck/Fakt}
{Lemma}
{}
{
\faktsituation {Die
\definitionsverweis {Binomialkoeffizienten}{}{}}
\faktfolgerung {erfüllen die rekursive Beziehung
\mavergleichskettedisp
{\vergleichskette
{ \binom { n+1 } { k }
}
{ =} { \binom { n } { k } + \binom { n } { k-1 }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Es ist
\mavergleichskettealignhandlinks
{\vergleichskettealignhandlinks
{ \binom { n } { k } + \binom { n } { k-1 }
}
{ =} { { \frac{ n! }{ (n-k)!k! } } + { \frac{ n! }{ (n-(k-1))!(k-1)! } }
}
{ =} { { \frac{ n! }{ (n-k)!k! } } + { \frac{ n! }{ (n+1-k)!(k-1)! } }
}
{ =} { { \frac{ (n+1-k) \cdot n! }{ (n+1-k)!k! } } + { \frac{ k \cdot n! }{ (n+1-k)!k ! } }
}
{ =} { { \frac{ (n+1-k+k) \cdot n! }{ (n+1-k)!k ! } }
}
}
{
\vergleichskettefortsetzungalign
{ =} { { \frac{ (n+1)! }{ (n+1-k)!k ! } }
}
{ =} { \binom { n+1 } { k }
}
{ } {}
{ } {}
}
{}{.}
Wir geben noch einen zweiten Beweis für diese Aussage, der sich an der inhaltlichen Beschreibung der Binomialkoeffizienten als Teilmengenanzahl orientiert.
Es sei $M$ eine
\mathl{(n+1)}{-}elementige Menge und
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein fixiertes Element. Nach
Satz 13.6
ist die Anzahl der $k$-elementigen Teilmengen von $M$ gleich
\mathl{\binom { n+1 } { k }}{.} Eine solche Teilmenge enthält entweder $x$ oder aber nicht. Im ersten Fall entspricht dann eine solche Teilmenge einer
\mathl{(k-1)}{-}elementigen Teilmenge von
\mathl{M \setminus \{x\}}{,} das ergibt den Summanden
\mathl{\binom { n } { k-1 }}{.} Im zweiten Fall entspricht eine solche Teilmenge einer $k$-elementigen Teilmenge von
\mathl{M \setminus \{x\}}{,} das ergibt den Summanden
\mathl{\binom { n } { k }}{.}
\zwischenueberschrift{Der binomische Lehrsatz}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Binomio_al_cubo.svg} }
\end{center}
\bildtext {} }
\bildlizenz { Binomio al cubo.svg } {Drini} {} {Commons} {PD} {}
Die folgende \stichwort {allgemeine binomische Formel} {} oder \stichwort {binomischer Lehrsatz} {} bringt die Addition, die Multiplikation und die Potenzierung in einem kommutativen Halbring und insbesondere für die natürlichen Zahlen miteinander in Beziehung.
\inputfaktbeweis
{Kommutativer Halbring/Binomi/Fakt}
{Satz}
{}
{
\faktsituation {}
\faktvoraussetzung {Es sei $R$ ein
\definitionsverweis {kommutativer Halbring}{}{}
und
\mavergleichskette
{\vergleichskette
{a,b
}
{ \in }{R
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Ferner sei $n$ eine natürliche Zahl.}
\faktfolgerung {Dann gilt
\mathdisp {( a + b )^{n} = \sum_{ k=0 } ^{ n } \binom { n } { k } a^{k} b^{n - k}} { . }
}
\faktzusatz {}
\faktzusatz {}
}
{
Wir führen Induktion nach $n$. Für
\mavergleichskette
{\vergleichskette
{n
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
steht einerseits
\mavergleichskette
{\vergleichskette
{ (a+b)^0
}
{ = }{ 1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und andererseits
\mavergleichskette
{\vergleichskette
{a^0b^0
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.} Es sei die Aussage bereits für $n$ bewiesen. Dann ist
\mavergleichskettealignhandlinks
{\vergleichskettealignhandlinks
{(a+b)^{n+1}
}
{ =} {(a+b) (a+b)^n
}
{ =} {(a+b) { \left( \sum_{ k=0 } ^{ n } \binom { n } { k } a^{k} b^{n - k} \right) }
}
{ =} {a \left( \sum_{ k=0 } ^{ n } \binom { n } { k } a^{k} b^{n - k}\right) + b \left( \sum_{ k=0 } ^{ n } \binom { n } { k } a^{k} b^{n - k} \right)
}
{ =} {\sum_{ k=0 } ^{ n } \binom { n } { k } a^{k+1} b^{n - k} + \sum_{ k=0 } ^{ n } \binom { n } { k } a^{k} b^{n - k+1}
}
}
{
\vergleichskettefortsetzungalign
{ =} {\sum_{ k= 1 } ^{ n+1 } \binom { n } { k-1 } a^{k} b^{n - k+1} + \sum_{ k=0 } ^{ n+1 } \binom { n } { k } a^{k} b^{n - k+1}
}
{ =} { \sum_{ k= 1 } ^{ n+1 } \left( \binom { n } { k-1 } + \binom { n } { k } \right) a^{k} b^{n+1 - k} + b^{n+1}
}
{ =} { \sum_{ k=1 } ^{ n +1} \binom { n+1 } { k } a^{k} b^{n+1 - k} + b^{n+1}
}
{ =} { \sum_{ k= 0 } ^{ n +1} \binom { n+1 } { k } a^{k} b^{n+1 - k}
}
}
{}{.}
Den vorstehenden Satz kann man sich auch folgendermaßen klar machen. Beim Ausmultiplizieren von
\mavergleichskettedisp
{\vergleichskette
{ (a+b)^n
}
{ =} { \underbrace{ (a+b) \cdot (a+b) \cdots (a+b) }_{n\text{-fach } }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
muss jeder Summand
gemäß dem allgemeinen Distributivgesetz
\zusatzklammer {in jedem Faktor} {} {}
mit jedem Summanden multipliziert werden. Für jedes Teilprodukt muss man sich bei jedem Faktor entscheiden, ob man den vorderen Summanden $a$ oder den hinteren Summanden $b$ nimmt. Die einzelnen Produkte haben die Form
\mathl{a^k b^{n-k}}{,} wobei $k$ die Anzahl der Faktoren ist, bei denen $a$ gewählt wurde und $n-k$ die Anzahl der Faktoren ist, bei denen $b$ gewählt wurde. Wenn man $k$ fixiert, so kann man sich fragen, auf wie viele Arten das Produkt
\mathl{a^k b^{n-k}}{} zustande kommen kann. Eine solche Möglichkeit ist dadurch gegeben, dass man unter den $n$ Faktoren bestimmt, in welchen von ihnen $a$ gewählt wird. Die Anzahl der Möglichkeiten ist also die Anzahl der $k$-elementigen Teilmengen von
\mathl{{ \{ 1 , \ldots , n \} }}{,} also gleich
\mathl{\binom { n } { k }}{.}