0 Daumen
235 Aufrufe

Aufgabe: Binomialkoeffizienten


Was könnte für eine Ausarbeitung von Binomialkoeffizienten als Leitidee sein?

für jeden Vorschlag bin ich sehr Dankbar :)


Meine Ausarbeitung habe ich schon bereit geschrieben nun fehlt mir die Leitideen

Avatar von

2 Antworten

+1 Daumen

Wie viele mögliche Lottozahlen gibt es?

Und wie groß ist dann die Wahrscheinlichkeit das man mit einem Tipp einen Volltreffer hat.

Avatar von 477 k 🚀
+1 Daumen

Aloha :)

Die Kernidee des Binomialkoeffizienten

Wir haben \(n\) Objekte und wollen daraus genau \(k\) Objekte (ohne Zurücklegen) auswählen. Die Anzahl dieser Auswahlmöglichkeiten bezeichnen wir mit \(\binom{n}{k}\).$$\binom{n}{k}\coloneqq\text{Anzahl der Möglichkeiten, aus \(n\) Objekten genau \(k\) auszuwählen.}$$

Diese Ausdrücke heißen "Binomialkoeffizienten", man liest sie als "n über k" oder auch "n aus k".

Beispiel

Die Menge \(\{A,B,C,D\}\) enthält \(n=4\) Objekte.

Es gibt genau \(1\) Möglichkeit, kein Objekt auszuwählen, das liefert dann die leere Menge:$$\binom{4}{0}=1\quad\text{nämlich}\quad\{\emptyset \}$$Es gibt genau \(4\) Möglichkeiten, genau ein Objekt auszuwählen:$$\binom{4}{1}=4\quad\text{nämlich}\quad\{\{A\},\{B\},\{C\},\{D\}\}$$Es gibt genau \(6\) Möglichkeiten, genau zwei Objekte auszuwählen:$$\binom{4}{2}=6\quad\text{nämlich}\quad\{\{A,B\},\{A,C\},\{A,D\}\{B,C\},\{B,D\},\{C,D\}\}$$Es gibt genau \(4\) Möglichkeiten, genau drei Objekte auszuwählen:$$\binom{4}{3}=4\quad\text{nämlich}\quad\{\{A,B,C\},\{A,B,D\},\{A,C,D\},\{B,C,D\}\}$$Es gibt genau \(1\) Möglichkeiten, genau vier Objekte auszuwählen:$$\binom{4}{4}=1\quad\text{nämlich}\quad\{\{A,B,C,D\}\}$$

Einfache Folgerungen

$$\binom{n}{0}=1\quad;\quad\binom{n}{n}=1\quad;\quad\binom{n}{k}=\binom{n}{n-k}$$

zu 1) Es gibt immer nur eine Möglichkeit, kein Objekt auszuwählen, wir erhalten dann die leere Menge.

zu 2) Es gibt immer nur eine Möglichkeit, alle Objekte auszuwählen.

zu 3) Es gibt genau so viele Möglichkeiten, genau \(k\) Objekte auswählen wie genau \((n-k)\) Objekte nicht auszuwählen.

Rekursionsgleichung

Wie viele Möglichkeiten gibt es, aus \((n+1)\) Objekten genau \(k\) auszuwählen? Zur Beantwortung stellen wir uns vor, wir hätten \(n\) Objekte und würden dazu ein neues Objekt dazulegen. Dann gibt es 2 Möglichkeiten.

a) Das neue Objekt wird ausgewählt. Dann müssen aus den \(n\) alten Objekten noch genau \((k-1)\) ausgewählt werden. Dafür gibt es \(\binom{n}{k-1}\) Möglichkeiten.

b) Das neue Objekt wird nicht ausgewählt. Dann müssen aus den \(n\) alten Objekten genau \(k\) Objekte ausgewählt werden. Dafür gibt es \(\binom{n}{k}\) Möglichkeiten.

Das bedeutet mit Binomialkoeffizienten geschrieben:$$\binom{n+1}{k}=\binom{n}{k-1}+\binom{n}{k}$$

Pacal-Dreieck

Nachdem wir uns diese Rekursions-Gleichung überlegt haben, können wir die Binomialkoeffizienten für kleine Werte von \(n\) sehr schnell berechnen, indem wir sie in einem Dreieck anordnen:

$$\begin{array}{l}\phantom{\binom{0}{0}}n=0:\\[1ex]\phantom{\binom{0}{0}}n=1:\\[1ex]\phantom{\binom{0}{0}}n=2:\\[1ex]\phantom{\binom{0}{0}}n=3:\\[1ex]\phantom{\binom{0}{0}}n=4:\\[1ex]\phantom{\binom{0}{0}}n=5:\end{array}\quad\begin{array}{c}\binom{0}{0}\\[1ex]\binom{1}{0}\quad\binom{1}{1}\\[1ex]\binom{2}{0}\quad\binom{2}{1}\quad\binom{2}{2} \\[1ex]\binom{3}{0}\quad\binom{3}{1}\quad\binom{3}{2}\quad\binom{3}{3}\\[1ex]\binom{4}{0}\quad\binom{4}{1}\quad\binom{4}{2}\quad\binom{4}{3}\quad\binom{4}{4}\\[1ex]\binom{5}{0}\quad\binom{5}{1}\quad\binom{5}{2}\quad\binom{5}{3}\quad\binom{5}{4}\quad\binom{5}{5}\end{array}\quad\Longleftrightarrow\quad\begin{array}{c}1\\[1ex]1\quad1\\[1ex]1\quad2\quad1 \\[1ex]1\quad3\quad3\quad1\\[1ex]1\quad4\quad6\quad4\quad1\\[1ex]1\quad5\quad10\quad10\quad5\quad1\end{array}$$

Wegen \(\binom{n}{0}=1\) und \(\binom{n}{n}=1\) fängt jede Zeile mit einer \(1\) an und endet mit einer \(1\). Alle Binomialkoeffizienten dazwischen erhalten wir als Summe ihrer beiden Eltern, die über ihm im Dreieck stehen (siehe Rekursions-Gleichung).

Berechnungsformel für den Binomialkoeffizienten

Für große \(n\) ist die Bestimmung von \(\binom{n}{k}\) mit dem Pascal-Dreieck zu aufwendig. Dafür bietet sich die folgende Berechnungsformel an:$$\binom{n}{k}=\frac{n!}{k!\cdot(n-k)!}$$Diese Formel wird oft als Definition für den Binomialkoeffizienten verwendet. Das ist zwar ok, verbirgt aber die Einsicht, was der Binomialkoeffizient wirklich bedeutet. Wir prüfen die Richtigkeit der Formel, indem wir die Gültigkeit der Randbedingungen und die Gültigkeit der Rekursionsgleichung überprüfen:

$$\binom{n}{0}=\frac{n!}{0!\cdot(n-0)!}=\frac{n!}{1\cdot n!}=1\quad\checkmark\quad;\quad\binom{n}{n}=\frac{n!}{n!\cdot(n-n)!}=\frac{n!}{n!\cdot1}=1\quad\checkmark$$

$$\binom{n}{k}+\binom{n}{k-1}=\frac{n!}{k!\cdot(n-k)!}+\frac{n!}{(k-1)!\cdot(n-(k-1))!}$$$$\qquad=\frac{n!}{k!\cdot(n-k)!}\cdot\frac{(n-k+1)}{(n-k+1)}+\frac{n!}{(k-1)!\cdot(n-k+1)!}\cdot\frac{k}{k}$$$$\qquad=\frac{n!\cdot(n-k+1)}{k!\cdot\underbrace{(n-k)!\cdot(n-k+1)}_{=(n-k+1)!}}+\frac{n!\cdot k}{\underbrace{(k-1)!\cdot k}_{=k!}\cdot(n-k+1)!}$$$$\qquad=\frac{n!\cdot n-n!\cdot k+n!}{k!\cdot(n-k+1)!}+\frac{n!\cdot k}{k!\cdot(n-k+1)!}=\frac{n!\cdot n\,\cancel{-n!\cdot k}+n!\,\cancel{+n!\cdot k}}{k!\cdot(n-k+1)!}$$$$\qquad=\frac{n!\cdot n+n!}{k!\cdot(n-k+1)!}=\frac{n!\cdot(n+1)}{k!\cdot(n+1-k)!}=\frac{(n+1)!}{k!\cdot((n+1)-k)!}=\binom{n+1}{k}\quad\checkmark$$Damit ist die Gültigkeit der Berechnungsformel bewiesen.

Anwendungsbeispiel: Der binomische Lehrsatz

Ihren Namen haben die Binomialkoeffizienten durch ihr Auftauchen im sog. "binomischen Lehrsatz" erhalten. Wir suchen eine Formel zur schnellen Berechnung von Binomen:$$(a+b)^n=\underbrace{(a+b)\cdot(a+b)\cdot(a+b)\cdots(a+b)}_{n\text{ Faktoren}}$$Bei der Durchführung der Mutliplikation müssen wir aus jedem der \(n\) Faktoren entweder ein \(a\) oder ein \(b\) auswählen.

Wir haben genau \(\binom{n}{n}\) Möglichkeiten, um \(n\)-mal das \(a\) auszuwählen (und kein Mal das \(b\)). Den Beitrag \(a^n\) gibt es also \(\binom{n}{n}=1\) Mal.

Wir haben genau \(\binom{n}{n-1}\) Möglichkeiten, um \((n-1)\)-mal das \(a\) auszuwählen und \(1\)-mal das \(b\). Den Beitrag \(a^{n-1}b\) gibt es also \(\binom{n}{n-1}\) Mal.

Wir haben genau \(\binom{n}{n-2}\) Möglichkeiten, um \((n-2)\)-mal das \(a\) auszuwählen und \(2\)-mal das \(b\). Den Beitrag \(a^{n-2}b^2\) gibt es also \(\binom{n}{n-2}\) Mal.

Führt man diese Argumentation fort, kann man den binomischen Lehrsatz hinschreiben:$$(a+b)^n=\sum\limits_{k=0}^n\binom{n}{n-k}\cdot a^{n-k}\cdot b^k=\sum\limits_{k=0}^n\binom{n}{k}\cdot a^{n-k}\cdot b^k$$

Avatar von 148 k 🚀

@Tschaka


Diese Formel wird oft als Definition für den Binomialkoeffizienten verwendet. Das ist zwar ok, verbirgt aber die Einsicht, was der Binomialkoeffizient wirklich bedeutet.

Hier fängst du an, unseriös zu werden:

wirklich bedeutet.


Du setzt das Primat auf vorhergehende Anwendungsfälle, die in der Summe der Betrachtung all dieser Anwendungsfälle sozusagen didaktisch ein solches Konstrukt "Binomialkoeffizien" erzeugen. (Eigentlich ist es sogar nur ein einziger Anwendungsfall.)

Warum sollte ausgerechnet die Kombinatorik die Binomialkoeffizienten ursächlich erzeugt haben? Die kommen auch völlig ohne Kombinatorik allein beim Ausmultiplizieren des Terms (a+b)n zustande (das hast du nachträglich selbst aufgeführt)

Und selbst das braucht man nicht. Man kann Binomialkoeffizienten einfach nur so "definieren" und hinterher staunen, welche Anwendungsmöglichkeiten es für ein so definiertes Konstrukt in mehreren Gebieten der Mathematik gibt.

Ich habe damals in der Schule den Binomialkoeffizienten leider einfach nur so definiert bekommen. Der tiefere Sinn blieb mir dann lange verborgen. Erst als mir die Bedeutung innerhalb der Kombinatorik klar wurde, waren plötzlich die Rekursionsgleichung und der binomische Lehrsatz völlig trivial. Die braucht man dann noch nicht mal zu lernen, weil man sie sofort hinschreiben kann.

Daher hast du schon Recht. Die Herangehensweise über die Kombinatorik basiert auf meinen persönlichen Erfahrungen. Ich versuche immer, Zusammenhänge zu verstehen, weil ich sehr lernfaul bin.

Adar kann sich ja nun selbst entscheiden, welchen Zugang er gerne wählen möchte.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community