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

Vorli begleitet dich bei den Vorlesungen. Das hilft sehr, denn Vorli sorgt für eine gute Balance aus Energie und Entspannung.

Abbildungen zwischen endlichen Mengen

In der letzten Vorlesung haben wir zwei wichtige Prinzipien der elementaren Kombinatorik kennengelernt, nämlich das Additivitätsprinzip für disjunkte Mengen (Lemma 1.6) und das Multiplikativitätsprinzip für Produktmengen (Lemma 1.7). Hier werden wir entsprechende Überlegungen für Abbildungen zwischen endlichen Mengen anstellen.

In der folgenden Aussage bezeichnen wir zu einer Abbildung

$f\colon L\longrightarrow M$

zu ${}y\in M$ die Menge

${}f^{-1}(y):={\left\{x\in L\mid f(x)=y\right\}}\,$

als Urbildmenge zu ${}y$. Man spricht auch von der Faser zu ${}y$.

Satz

Es seien ${}L$ und ${}M$ endliche Mengen und es sei

$f\colon L\longrightarrow M$

eine Abbildung.

Dann gilt

${}{\#\left(L\right)}=\sum _{y\in M}{\#\left(f^{-1}(y)\right)}\,.$

Beweis

Da jedes Element ${}x\in L$ auf genau ein Element aus ${}M$ abgebildet wird, liegt eine disjunkte Vereinigung

${}L=\biguplus _{y\in M}f^{-1}(y)\,$

vor. Nach Lemma 1.6 ist daher die Gesamtanzahl der Menge gleich der Summe der Anzahlen der disjunkten Teilmengen.

$\Box$

Satz

Es seien ${}L$ und ${}M$ endliche Mengen mit ${}\ell$ bzw. ${}m$ Elementen.

Dann gibt es ${}m^{\ell }$ Abbildungen von ${}L$ nach ${}M$.

Beweis

Ohne Einschränkung sei

${}L=\{1,2,\ldots ,\ell \}\,.$

Es gibt eine natürliche bijektive Abbildung

$\operatorname {Abb} \,{\left(L,M\right)}\longrightarrow \underbrace {M\times \cdots \times M} _{\ell {\text{ Faktoren}}},\,f\longmapsto \left(f(1),\,f(2),\,\ldots ,\,f(\ell )\right),$

was darauf beruht, dass eine Abbildung und eine vollständige Wertetabelle äquivalente Objekte sind. Daher folgt die Aussage aus Lemma 1.7 bzw. dessen Verallgemeinerung auf eine mehrfache Produktmenge, siehe Aufgabe 1.20.

$\Box$

Solche Aussagen werden in der Kombinatorik gerne mit einem Kugel- und Urnenmodell ausgedrückt. In diesem Fall sagt, man dass es ${}n^{\ell }$ Möglichkeiten gibt, ${}\ell$ unterscheidbare Kugeln auf ${}n$ unterscheidbare Urnen ohne weitere Bedingung zu verteilen. Abbildungen entsprechen dabei immer dem beidseitig unterscheidbaren Fall, einfach deshalb, weil in einer Menge die Elemente unterscheidbar sind.

Die Fakultät

Dieses Tanzpaar hat sich schon gefunden. Für die verbliebenen Personen gibt es insgesamt noch ${}(n-1)!$ Möglichkeiten (Gemälde von Ernst Ludwig Kirchner).

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.

Definition

Zu einer natürlichen Zahl ${}n$ nennt man die Zahl

${}n!:=n(n-1)(n-2)\cdots 3\cdot 2\cdot 1\,$

die Fakultät von ${}n$ (sprich ${}n$ Fakultät).

Es ist ${}(n+1)!=(n+1)(n!)$. Man setzt ${}0!=1$. Für kleine ${}n$ erhält man die folgende Wertetabelle.

${}n$	${}0$	${}1$	${}2$	${}3$	${}4$	${}5$	${}6$	${}7$	${}8$	${}9$	${}10$
${}n!$	${}1$	${}1$	${}2$	${}6$	${}24$	${}120$	${}720$	${}5040$	${}40320$	${}362880$	${}3628800$

Satz

Es seien ${}M$ und ${}N$ endliche Mengen, die beide ${}n$ Elemente besitzen.

Dann gibt es ${}n!$ bijektive Abbildungen von ${}M$ nach ${}N$.

Beweis

Wir führen Induktion über ${}n$, wobei der Fall ${}n=1$ klar ist. Die Aussage sei nun für ${}n$ schon bewiesen und es liegen zwei ${}(n+1)$-elementige Mengen ${}M$ und ${}N$ vor. Es sei ${}x\in M$ ein fixiertes Element. Dann gibt es für die Werte ${}\varphi (x)$ genau ${}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

${}\varphi (x)=y\,$

den bijektiven Abbildungen von ${}M\setminus \{x\}$ nach ${}N\setminus \{y\}$. Nach Induktionsvoraussetzung gibt es ${}n!$ solche bijektiven Abbildungen. Daher ist die Anzahl der bijektiven Abbildungen zwischen ${}M$ und ${}N$ gleich

${}(n+1)\cdot n!=(n+1)!\,.$

$\Box$

Gleichbedeutend damit ist, dass es ${}n!$ Möglichkeiten gibt, ${}n$ Objekte auf ${}n$ Plätze zu verteilen, oder ${}n!$ Möglichkeiten, ${}n$ unterscheidbare Kugeln auf ${}n$ unterscheidbare Urnen so zu verteilen, dass keine Urne leer bleibt, oder ${}n!$ Möglichkeiten, eine Menge von ${}n$ Objekten abzuzählen (durchzunummerieren).

Korollar

Auf einer endlichen Menge ${}M$ mit ${}n$ Elementen

gibt es ${}n!$ bijektive Abbildungen von ${}M$ nach ${}M$.

Beweis

Dies ist ein Spezialfall von Satz 2.4.

$\Box$

Bijektive Abbildungen einer Menge in sich bekommen einen eigenen Namen.

Definition

Eine Permutation ${}\sigma$ auf einer Menge ${}M$ ist eine bijektive Abbildung

$\sigma \colon M\longrightarrow M.$

Beispiel

Wir möchten eine vollständige Liste von allen bijektiven Abbildungen von der Menge ${}\{1,2,3\}$ in die Menge ${}\{a,b,c\}$ in der Form von Wertetabellen angeben. Wegen

${}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 ${}2$ und ${}3$ durchgehen. Dies führt auf die folgenden Wertetabellen.

${}x$	${}1$	${}2$	${}3$
${}\varphi _{1}(x)$	${}a$	${}b$	${}c$

${}x$	${}1$	${}2$	${}3$
${}\varphi _{2}(x)$	${}a$	${}c$	${}b$

${}x$	${}1$	${}2$	${}3$
${}\varphi _{3}(x)$	${}b$	${}a$	${}c$

${}x$	${}1$	${}2$	${}3$
${}\varphi _{4}(x)$	${}b$	${}c$	${}a$

${}x$	${}1$	${}2$	${}3$
${}\varphi _{5}(x)$	${}c$	${}a$	${}b$

${}x$	${}1$	${}2$	${}3$
${}\varphi _{6}(x)$	${}c$	${}b$	${}a$

Lemma

Es seien ${}L$ und ${}M$ endliche Mengen mit ${}\ell$ bzw. ${}m$ Elementen mit ${}\ell \leq m$.

Dann gibt es ${}m(m-1)(m-2)\cdots (m-\ell +1)$ injektive Abbildungen von ${}L$ nach ${}M$.

Beweis

Siehe Aufgabe 2.14.

$\Box$

Die Bestimmung der Anzahl von surjektiven Abbildungen ist deutlich schwieriger, wir werden in der 13. Vorlesung darauf zurückkommen.

Die Potenzmenge

Definition

Zu einer Menge ${}M$ nennt man die Menge aller Teilmengen von ${}M$ die Potenzmenge von ${}M$. Sie wird mit

${\mathfrak {P}}\,(M)$

bezeichnet.

Wenn ${}M$ die Menge der Leute im Kurs sind, so kann man ${}{\mathfrak {P}}\,(M)$ als die Menge aller Parties auffassen, die diese Leute feiern können, wenn man eine Party mit der Menge der anwesenden Leute identifiziert.

Lemma

Es sei ${}M$ eine endliche Menge mit ${}m$ Elementen.

Dann besitzt die Potenzmenge ${}{\mathfrak {P}}\,(M)$ genau ${}2^{m}$ Elemente.

Beweis

Siehe Aufgabe 2.22.

$\Box$

Die Binomialkoeffizienten

Wir bezeichnen mit ${}{\mathfrak {P}}_{k}\,(M)$ die Menge der ${}k$-elementigen Teilmengen von ${}M$. Im Folgenden interessieren wir uns für deren Anzahl.

Satz

Die Anzahl der ${}k$-elementigen Teilmengen in einer ${}n$-elementigen Menge ist

${\frac {n!}{k!(n-k)!}}.$

Beweis

Es sei ${}M$ eine ${}n$-elementige Menge und ${}T\subseteq M$ eine ${}k$-elementige Teilmenge. Wir betrachten die Menge aller bijektiven Abbildungen

${\{1,\ldots ,n\}}\longrightarrow M,$

die zusätzlich ${}\{1,\ldots ,k\}$ auf ${}T$ und (deshalb) ${}\{k+1,\ldots ,n\}$ auf ${}M\setminus T$ abbilden. Nach Lemma 2.3 und nach Lemma 1.7 gibt es ${}k!\cdot (n-k)!$ solche Abbildungen. Insgesamt gibt es ${}n!$ bijektive Abbildungen von ${}{\{1,\ldots ,n\}}$ nach ${}M$. Daher ist

${}{\left({\text{Anzahl der }}k{\text{-elementigen Teilmengen von }}M\right)}\cdot k!\cdot (n-k)!=n!\,.$

Insbesondere ist ${}k!\cdot (n-k)!$ ein Teiler von ${}n!$ und es ist

${\frac {n!}{k!(n-k)!}}$

die Anzahl der ${}k$-elementigen Teilmengen von ${}M$.

$\Box$

Der Satz beinhaltet, dass ${}k!(n-k)!$ ein Teiler von ${}n!$ ist und somit ist der Bruch ${}{\frac {n!}{k!(n-k)!}}$ eine natürliche Zahl. Diese bekommt einen eigenen Namen und ein eigenes Symbol.

Definition

Es seien ${}k$ und ${}n$ natürliche Zahlen mit ${}k\leq n$. Dann nennt man

${}{\binom {n}{k}}:={\frac {n!}{k!(n-k)!}}\,$

den Binomialkoeffizienten „${}n$ über ${}k$“.

Bemerkung  

Für die Binomialkoeffizienten gilt die Regel

${}{\binom {n}{k}}={\binom {n}{n-k}}\,,$

wie unmittelbar aus der Definition folgt. Dies kann man sich auch mit Hilfe von Satz 2.5 klar machen. Die Komplementabbildung

${\mathfrak {P}}\,(M)\longrightarrow {\mathfrak {P}}\,(M),\,T\longmapsto \complement T,$

auf einer ${}n$-elementigen Menge ${}M$ ist bijektiv und bildet ${}k$-elementige Teilmengen auf ${}(n-k)$-elementige Teilmengen ab.

Den Binomialkoeffizienten ${}{\binom {n}{k}}$ kann man auch als

${}{\begin{aligned}{\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}}\end{aligned}}$

schreiben, da die Faktoren aus ${}(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 ${}k>n$ zuzulassen und in diesen Fällen die Binomialkoeffizienten gleich ${}0$ zu setzen. Dies passt zur Interpretation in Satz 2.5.

Beispiel

In der vierelementigen Menge ${}\{a,b,c,d\}$ gibt es

${}{\binom {4}{2}}={\frac {4\cdot 3}{2\cdot 1}}=6\,$

zweielementige Teilmengen. Diese sind

$\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{c,d\}.$

Beispiel

In einer ${}49$-elementigen Menge gibt es genau

${}{\binom {49}{6}}={\frac {49\cdot 48\cdot 47\cdot 46\cdot 45\cdot 44}{6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}}=13983816\,$

${}6$-elementige Teilmengen. Es gibt also so viele mögliche Zahlenkombinationen beim Lotto „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

$49\cdot 48\cdot 47\cdot 46\cdot 45\cdot 44,$

zu jeder sechselementigen Teilmenge gibt es ${}6!$ mögliche Ziehreihenfolgen die auf diese Teilmenge führen.

Das Dreieck der Binomialkoeffizienten war in Indien und in Persien schon um 1000 bekannt,

in China heißt es Yanghui-Dreieck (nach Yang Hui (um 1238-1298)),

in Europa heißt es das Pascalsche Dreieck (nach Blaise Pascal (1623-1662)).

Lemma

Die Binomialkoeffizienten

erfüllen die rekursive Beziehung

${}{\binom {n+1}{k}}={\binom {n}{k}}+{\binom {n}{k-1}}\,.$

Beweis

Es ist

${}{\begin{aligned}{\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!}}\\&={\frac {(n+1)!}{(n+1-k)!k!}}\\&={\binom {n+1}{k}}.\end{aligned}}$

$\Box$

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 ${}(n+1)$-elementige Menge und ${}x\in M$ ein fixiertes Element. Nach Satz 2.5 ist die Anzahl der ${}k$-elementigen Teilmengen von ${}M$ gleich ${}{\binom {n+1}{k}}$. Eine solche Teilmenge enthält entweder ${}x$ oder aber nicht. Im ersten Fall entspricht dann eine solche Teilmenge einer ${}(k-1)$-elementigen Teilmenge von ${}M\setminus \{x\}$, das ergibt den Summanden ${}{\binom {n}{k-1}}$. Im zweiten Fall entspricht eine solche Teilmenge einer ${}k$-elementigen Teilmenge von ${}M\setminus \{x\}$, das ergibt den Summanden ${}{\binom {n}{k}}$.

Fußnoten

<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >> PDF-Version dieser Vorlesung Arbeitsblatt zur Vorlesung (PDF)