Kombinatorik/Elementar/Einführung/Textabschnitt

Definition

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

n! := n (n - 1) (n - 2) \dots 3 \cdot 2 \cdot 1

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

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

Lemma

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

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

Wir zeigen etwas allgemeiner, dass es zwischen zwei endlichen Mengen $M$ und $N$ , die beide $n$ Elemente besitzen, $n!$ bijektive Abbildungen gibt. Dies zeigen wir durch Induktion nach $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 Bilder $φ (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

φ (x) = y

den bijektiven Abbildungen von $M ∖ {x}$ nach $N ∖ {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)! .

◻

Gleichbedeutend damit ist, dass es $n!$ Möglichkeiten, $n$ Objekte auf $n$ Plätze zu verteilen bzw. $n!$ Möglichkeiten, eine Menge von $n$ Objekten abzuzählen.

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$
$φ_{1} (x)$	$a$	$b$	$c$

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

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

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

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

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

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$ “.

Von der Definition her ist es nicht sofort klar, dass es sich bei den Binomialkoeffizienten um natürliche Zahlen handelt. Dies folgt aus der folgenden Beziehung.

Lemma

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

der Binomialkoeffizient

$(\binom{n}{k}) .$

Insbesondere sind die Binomialkoeffizienten natürliche Zahlen.

Beweis

Es sei $M$ eine $n$ -elementige Menge und

T \subseteq M

eine $k$ -elementige Teilmenge. Wir betrachten die Menge aller bijektiven Abbildungen

{1, \dots, n} ⟶ M,

die zusätzlich ${1, \dots, k}$ auf $T$ (und damit) ${k + 1, \dots, n}$ auf $M ∖ T$ abbilden. Nach Fakt und nach Fakt gibt es $k! \cdot (n - k)!$ solche Abbildungen. Insgesamt gibt es $n!$ bijektive Abbildungen von ${1, \dots, n}$ nach $M$ . Daher ist

(Anzahl der k -elementigen Teilmengen von M) \cdot k! \cdot (n - k)! = n! .

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

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

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

◻

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.

Diesen Bruch kann man auch als

\frac{n (n - 1) (n - 2) \dots (n - k + 2) (n - k + 1)}{k (k - 1) (k - 2) \dots 2 \cdot 1}

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.

Lemma

Die Binomialkoeffizienten

erfüllen die rekursive Beziehung

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

Beweis

Es ist

\begin{matrix} (\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{matrix}

◻

Wir geben noch einen zweiten Beweis für diese Aussage, der sich an der inhaltlichen Beschreibung als Teilmengenanzahl orientiert.

Es sei $M$ eine $(n + 1)$ -elementige Menge und $x \in M$ ein fixiertes Element. Nach Fakt 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 ∖ {x}$ , das ergibt den Summanden $(\binom{n}{k - 1})$ . Im zweiten Fall entspricht eine solche Teilmenge einer $k$ -elementigen Teilmenge von $M ∖ {x}$ , das ergibt den Summanden $(\binom{n}{k})$ .