🎓 Ui, schon Prüfungszeit? Hier geht's zur Mathe-Prüfungsvorbereitung.
Springe zum Inhalt oder Footer
SerloDie freie Lernplattform

11. Kombinatorik

In der Kombinatorik interessiert man sich dafür, wie viele Möglichkeiten es für die Ergebnisse bestimmter Versuchsanordnungen gibt - z.B., um die Wahrscheinlichkeit für das Auftreten eines solchen Ereignisses zu berechnen.

Viele Probleme dieser Art lassen sich auf Urnenmodelle zurückführen.

Bild

Einführung und Motivation

Wir stellen uns dazu n unterscheidbare Kugeln (nummerierte Lottokugeln) in einer Urne vor, aus denen nun nacheinander k Kugeln gezogen werden. Wenn Wahrscheinlichkeiten interessieren, soll bei jedem Zug die Wahrscheinlichkeit für jede Kugel gleich sein ("blind ziehen"), zum Anzählen der Möglichkeiten reicht es, wenn in jedem Zug jede Kugel drankommen kann. Im Folgenden seien n,k0, wobei wir 00=0!=1 setzen.

Für den Versuchsaufbau sind zwei Entscheidungen zu treffen:

  • man kann die gezogene Kugel wieder in die Urne zurücklegen (nachdem man sich die Nummer notiert hat…) oder nicht und

  • man kann sich beim Ergebnis dafür interessieren, in welcher Reihenfolge die Kugeln gezogen wurden oder nicht (letztes trifft z.B. beim Lotto zu, wo die Lottogesellschaft uns die Zahlen sortiert).

Somit sind vier verschiedene Fälle zu betrachten.

Ziehen mit Zurücklegen, mit Berücksichtigung der Reihenfolge

Wenn wir die Kugeln wieder zurückwerfen, haben wir in jedem der k Züge n Möglichkeiten.

Das ist also wie in der Aufgabe mit den 2k möglichen Zuständen von k Bit, nur dass dort der Spezialfall n=2 untersucht wurde.

SatzZiehen mit Zurücklegen, mit Beachtung der Reihenfolge

Für allgemeines n haben wir dann nk verschiedene Möglichkeiten.

Ziehen ohne Zurücklegen, mit Berücksichtigung der Reihenfolge

Jetzt werfen wir gezogene Kugeln nicht wieder zurück.

Dann haben wir im ersten Zug nach wie vor n Kugeln, im zweiten Zug aber nur noch n1, im dritten n2, , im letzten (k-ten) Zug noch nk+1 Kugeln zur Auswahl.

Beim j-ten der k Züge also nj+1 Möglichkeiten, also insgesamt

  • n(n1)(n2)(nk+1)

mögliche Ergebnisse.

SatzZiehen ohne Zurücklegen, mit Beachtung der Reihenfolge

Das lässt sich schreiben als

n!(nk)!

Wichtig ist hier der Spezialfall n=k: es gibt n! Möglichkeiten, um n Objekte anzuordnen.

Ziehen ohne Zurücklegen, ohne Berücksichtigung der Reihenfolge

Jetzt sortieren wir die Kugeln nach ihrer Nummerierung, bevor wir das Ergebnis verkünden - die Zugfolgen (15,4,8) und (4,8,15) zählen nun als gleich, wir sind also beim klassischen Lotto. Wie viele Möglichkeiten gibt es nun noch?

SatzZiehen ohne Zurücklegen, ohne Berücksichtigung der Reihenfolge

Wir haben vorhin gesehen, dass es bei k Objekten k! verschiedene Anordnungen gibt. Daher müssen wir das vorherige Ergebnis einfach durch k! dividieren

(nk):=n!k!(nk)!

Die Anzahl der verschiedenen Anordnungsmöglichkeiten ist also genau durch die Binomialkoeffizient gegeben.

Ziehen mit Zurücklegen, ohne Berücksichtigung der Reihenfolge

Der schwierigste Fall zuletzt: wir werfen die Kugeln in die Urne zurück und identifizieren Zugfolgen, die sich nur in der Reihenfolge unterscheiden, d.h., wir interessieren uns nur dafür, wie oft welche Kugel gezogen wird.

Zum Beweis ersetzen wir das ursprüngliche Modell mit Kugeln und Zellen durch ein anderes Modell:

n+k1 Positionen. Verteile n1 Striche auf diese Positionen. Alle Positionen ohne Strich erhalten (einen Stern).

Auf diese Art und Weise kann jedes mögliche Ereignis des ursprünglichen Urnenmodells eindeutig codiert werden.

Nun interpretieren wir dieses Strich-Modell wieder als ein Urnenmodell: Kugeln = mögliche Positionen von 1,2,,n+k1. Gezogen werden n1 Kugeln ohne Zurücklegen und ohne Berücksichtigung der Reihenfolge. Jede gezogene Kugel ist eine Position der n1 Striche.

SatzZiehen mit Zurücklegen, ohne Berücksichtigung der Reihenfolge

Daher gibt es

(n+k1n1)=(n+k1)!(n1)!k!=(n+k1k)

Möglichkeiten, nämlich so viele, wie es Möglichkeiten gibt, aus den Zahlen 1,2,,n+k1 genau n1 zu ziehen (ohne Zurücklegen und ohne Berücksichtigung der Reihenfolge).

Laden

Laden

Laden


Dieses Werk steht unter der freien Lizenz
CC BY-SA 4.0Was bedeutet das?