Binomialkoeffizient

Wir beginnen mit einer Definition:

Definition 1

Betrachte zwei natürliche Zahlen (inklusive 00) nn und rr, wobei n≥rn\geq r. Der Binomialkoeffizient von nn und rr, bezeichnet mit

(nr)\left(\begin{array}{lll} n \\ r\end{array}\right)

ist definiert als

(nr)=n!r!⋅(n−r)!\left(\begin{array}{lll} n \\ r\end{array}\right)=\frac{n!}{r!\cdot(n-r)!}

(ausgesprochen "n tief r").

Eine andere Notation ist nCrnCr (aus dem Englischen: "n choose r"), die vor allem auf dem Taschenrechner zu finden ist. Aus dem vorhergehenden Kapitel wissen wir nun:

Theorem 1

Ein Wort bestehe aus rr Kopien eines Buchstaben und n−rn-r Kopien eines anderen Buchstabens (etwa AABBAAAB). Die total Anzahl an Buchstaben ist also nn. Die Anzahl der möglichen Wörter die durch umordnen gebildet werden können ist gerade der Binomialkoeffizient

(nr)\left(\begin{array}{lll} n \\ r\end{array}\right)
Proof

mit der MISSISSIPPI-Formel folgt, dass die Anzahl Wörter gerade

n!r!⋅(n−r)!\frac{n!}{r!\cdot (n-r)!}

ist, also laut Definition

(nr)\left(\begin{array}{lll} n \\ r\end{array}\right)
Example 1

Die Anzahl der Wörter, die durch Umstellen der Buchstaben des Wortes "KKKZZKZ" gebildet werden können, ist

(74)=7!4!⋅(7−4)!=7!4!⋅3!=35\left(\begin{array}{cll} 7 \\ 4\end{array}\right)=\frac{7!}{4!\cdot (7-4)!}=\frac{7!}{4!\cdot 3!}=35

weil die Anzahl der Buchstaben n=7n=7 ist und es k=4k=4 K gibt. Natürlich könnten wir auch argumentieren, dass es k=3k=3 Z gibt, und dann würden wir erhalten

(73)=7!3!⋅(7−3)!=7!3!⋅4!=35\left(\begin{array}{cll} 7 \\ 3\end{array}\right)=\frac{7!}{3!\cdot (7-3)!}=\frac{7!}{3!\cdot 4!}=35

und tatsächlich erhalten wir die gleiche Anzahl von Möglichkeiten. Alles andere würde keinen Sinn ergeben.

Hier sind einige weitere Eigenschaften von Binomialkoeffizienten:

Theorem 2
  1. (n0)=1\left(\begin{array}{lll} n \\ 0\end{array}\right)=1
  2. (nn)=1\left(\begin{array}{lll} n \\ n\end{array}\right)=1
  3. (n1)=n\left(\begin{array}{lll} n \\ 1\end{array}\right)=n
  4. (nn−1)=n\left(\begin{array}{lll} n \\ n-1\end{array}\right)=n
  5. (nr)=(nn−r)\left(\begin{array}{lll} n \\ r\end{array}\right)=\left(\begin{array}{lll} n \\ n-r\end{array}\right)
Exercise 1

Beweise die obigen Aussagen auf zwei Arten. Erstens mit Hilfe der Definition des Binomialkoeffizienten, und zweitens, indem man die Anzahl der Permutationen eines Wortes mit nn Buchstaben findet.

Solution

Mit der Definition

  1. (n0)=n!0!(n−0)!=n!n!=1\left(\begin{array}{lll} n \\ 0\end{array}\right)=\frac{n!}{0!(n-0)!}=\frac{n!}{n!}=1
  2. (nn)=n!n!(n−n)!=n!n!=1\left(\begin{array}{lll} n \\ n\end{array}\right)=\frac{n!}{n!(n-n)!}=\frac{n!}{n!}=1
  3. (n1)=n!1!(n−1)!=n!(n−1)!=n\left(\begin{array}{lll} n \\ 1\end{array}\right)=\frac{n!}{1!(n-1)!}=\frac{n!}{(n-1)!}=n
  4. (nn−1)=n!(n−1)!(n−(n−1))!=n!(n−1)!=n\left(\begin{array}{lll} n \\ n-1\end{array}\right)=\frac{n!}{(n-1)!(n-(n-1))!}=\frac{n!}{(n-1)!}=n
  5. (nr)=n!r!(n−r)!\left(\begin{array}{lll} n \\ r\end{array}\right)=\frac{n!}{r!(n-r)!} and (nn−r)=n!(n−r)!(n−(n−r))!=n!(n−r)!⋅r!\left(\begin{array}{lll} n \\ n-r\end{array}\right)=\frac{n!}{(n-r)!(n-(n-r))!}=\frac{n!}{(n-r)!\cdot r!} also gleich!

Mit der Anzahl der Permutationen eines Wortes mit nn Buchstaben

Zum Beispiel bestehe das Wort aus den Buchstaben K und Z, und es sei rr die Anzahl der K.

  1. r=0r=0, also kein K, also sind alle Buchstaben gleich, ZZZZZ. Wenn wir die Buchstaben umordnen, erhalten wir immer das gleiche Wort. Also (n0)=1\left(\begin{array}{lll} n \\ 0\end{array}\right)=1

  2. r=nr=n, also nur K, also sind wieder alle Buchstaben gleich, KKKKK. Somit ist (nn)=1\left(\begin{array}{lll} n \\ n\end{array}\right)=1

  3. r=1r=1, also ein Buchstabe K, z.B. KZZZZ. Durch Umordnen der Buchstaben erhalten wir nn Möglichkeiten (es gibt nn Positionen, an denen wir das KK platzieren können: KZZZZ, ZKZZZ, ZZKZZ, ... ). Also (n1)=n\left(\begin{array}{lll} n \\ 1\end{array}\right)=n

  4. r=n−1r=n-1, also n−1n-1 Buchstaben K, z.B. KKKKZ. Wieder erhalten wir (nn−1)=n\left(\begin{array}{lll} n \\ n-1\end{array}\right)=n.

  5. (nr)\left(\begin{array}{lll} n \\ r\end{array}\right): Anzahl der Wörter, die gebildet werden können, wenn rr K im Wort und n−rn-r Z vorhanden sind.

    (nn−r)\left(\begin{array}{lll} n \\ n-r\end{array}\right): Anzahl der Wörter, die gebildet werden können, wenn das Wort n−rn-r K und rr Z enthält.

    Es handelt sich um unterschiedliche Wörter (z.B. KKZZZ und KKKZZ), aber es ist klar, dass in beiden Fällen die Anzahl der möglichen Permutationen gleich sein muss (einfach im zweiten Fall den Buchstaben K in Z und den Buchstaben Z in K umbenennen).