Der Binomialkoeffizient und nCr

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

Betrachte nn Objekte, wobei rr Objekte identisch sind, und auch die restlichen n−rn-r Objekte identisch sind. Die Anzahl der möglichen Permutationen, die gebildet werden können, ist

(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).

Es besteht eine enge Beziehung zwischen den Permutationen von Wörtern, die aus zwei verschiedenen Buchstaben bestehen, und Bäumen. Betrachten wir ein Wort, das aus zwei Buchstaben besteht, z. B. "AABB". Wir wissen bereits, dass es

(42)=6\left(\begin{array}{lll} 4 \\ 2\end{array}\right)=6

Permutationen des Wortes gibt. Aber was sind diese Wörter? Um das herauszufinden, ist es hilfreich, einen Baum wie folgt zu zeichnen: Da das Wort 44 Buchstaben hat, zeichnen wir 44 Generationen des Baumes, wobei der linke Zweig immer A und der rechte Zweig immer B ist (oder umgekehrt, das spielt keine Rolle):

Jeder Pfad von oben nach unten ergibt ein Wort. Wenn wir allen Pfaden folgen, erhalten wir alle möglichen 44-Buchstaben-Wörter, die mit den Buchstaben "A" und "B" gebildet werden können. Mit dem Baum ist leicht einzusehen, dass es 24=162^4=16 solcher Pfade oder eben Wörter geben muss.

Ebenfalls, folgt man den Pfaden, die genau 22 A und 22 B enthalten, kann man alle Permutationen von AABB herausfinden (siehe Abbildung oben). Es gibt (42)=6\left(\begin{array}{lll} 4 \\ 2\end{array}\right)=6 solcher Wörter (oder Pfade).

Oder wenn wir die Pfade verfolgen, die genau 11 A und 33 Bs enthalten, können wir alle Permutationen von ABBB herausfinden. Es gibt (41)=4\left(\begin{array}{lll} 4 \\ 1\end{array}\right)=4 solcher Wörter (oder Pfade). Und so weiter.

Es ist klar, dass die Vereinigung aller Permutationen der Wörter mit 00, 11, 22, 33 oder 44 "A" alle möglichen Wörter mit 44 Buchstaben bestehend aus "A" und "B" ergeben. Mit anderen Worten, es ist

(40)+(41)+(42)+(43)+(44)=24\left(\begin{array}{lll} 4 \\ 0 \end{array}\right) +\left(\begin{array}{lll} 4 \\ 1 \end{array}\right) +\left(\begin{array}{lll} 4 \\ 2 \end{array}\right) +\left(\begin{array}{lll} 4 \\ 3 \end{array}\right) +\left(\begin{array}{lll} 4 \\ 4 \end{array}\right)=2^4

was man an in diesem Beispiel schnell genug überprüfen kann, indem man die Summe tatsächlich berechnet:

1+4+6+4+1=161+4+6+4+1=16

Es ist einfach zu verallgemeinern:

Theorem 3

Betrachten wir eine natürliche Zahl nn. Wir haben das Folgende:

  1. Die Anzahl der Wörter mit nn Buchstaben, die mit zwei verschiedenen, aber gegebenen, Buchstaben gebildet werden können, ist 2n2^n.(Die Wörter bestehend aus nur einem dieser Buchstaben werden ebenfalls gezählt.)

  2. Die Summe aller Binomialkoeffizienten ist 2n2^n:

∑r=0n(nr)=(n0)+(n1)+...+(nn−1)+(nn)=2n\sum_{r=0}^n \left(\begin{array}{lll} n \\ r \end{array}\right) =\left(\begin{array}{lll} n \\ 0 \end{array}\right) +\left(\begin{array}{lll} n \\ 1 \end{array}\right) +...+\left(\begin{array}{lll} n \\ n-1 \end{array}\right) +\left(\begin{array}{lll} n \\ n \end{array}\right)=2^n