MathePrisma Logo

Kombinatorik

Kombinatorik

Kombinatorische Grundaufgaben

Ziehen
MIT
Zurücklegen,
OHNE
Berücksichtigung der
Reihenfolge

Wie sieht das Baumdiagramm für zweimaliges Ziehen aus einer Urne mit vier Kugeln aus,

  • bei der zwar die Reihenfolge unwichtig ist,

  • die Kugel aber nach dem Zug zurückgelegt wird?



Finden Sie es wieder selbst heraus:













Erstellen Sie das
entsprechende
Baumdiagramm!


Ziehen mit
Zurücklegen, ohne
Berücksichtigung der
Reihenfolge
n=4, k=2



Die allgemeine Formel im Fall "mit Wiederholung, ohne Berücksichtigung der Reihenfolge" erhält man über folgende Überlegung:




Betrachte:
Auswahl von
k Elementen aus
Menge mit
k+n-1 Elementen
ohne Zurücklegen,
ohne Beachtung der
Reihenfolge

Wir betrachten n + k-1 Kästchen (an Stelle von Kugeln).
Von diesen Kästchen wählen wir k-Stück aus.
Hierbei spielt die Reihenfolge, in der die Kästchen gewählt werden, keine Rolle und es kann kein Kästchen doppelt gewählt werden.
Damit beträgt die Anzahl der Möglichkeiten diese k Kästchen zu wählen
.



Wir zeigen nun, dass diese Aufgabe dem Ziehen von k Kugeln aus einer Urne mit Wiederholung
ohne Beachtung der Reihenfolge entspricht:


Entspricht:
Auswahl von
k Elementen aus
Menge mit
n Elementen
mit Zurücklegen, ohne
Beachtung der
Reihenfolge

Verallgemeinerung

Für die Auswahl

  • von k Elementen
  • aus einer Menge mit n Elementen
  • mit Wiederholung
  • und ohne Berücksichtigung der Reihenfolge


gibt es
\(\displaystyle \begin{pmatrix} n+k-1\\ k \end{pmatrix}\)
Möglichkeiten.

Beispiel für Auswahl mit Wiederholung, ohne Beachtung der Reihenfolge:

Frage

Bei einem Sonderangebot kann man sich eine Kiste (zwölf Flaschen) aus drei verschiedenen Getränkesorten beliebig zusammenstellen.
Wieviele Möglichkeiten gibt es dafür?

Es gibt:   Möglichkeiten.

Warum hier "mit
Wiederholung,
Reihenfolge
unwichtig"?





n=3, k=12

  • Mit Wiederholung": Sie können von einer Getränkesorte mehr als eine Flasche nehmen.
  • Reihenfolge unwichtig": Es interessiert nur, wieviele Flaschen Sie von welcher Sorte ausgewählt haben. In welcher Reihenfolge diese danach in Ihrer Kiste liegen, ist bei unserer Fragestellung unwichtig.



Sie wählen hier zwölf Flaschen aus drei Getränkesorten aus (mit Wiederholung),
d.h. n=3 und k=12.
In obige Formel eingesetzt, ergibt sich die gesuchte Lösung.

slideshow5Bew4_1_1
slideshow5Bew4_1_2
Die n-1 nicht gewählten Felder streichen wir und nummerieren sie von 1 bis n-1.
slideshow7Bew4_2_1
Die n-1 nicht gewählten Felder streichen wir und nummerieren sie von 1 bis n-1.
slideshow7Bew4_2_2
Die n-1 nicht gewählten Felder streichen wir und nummerieren sie von 1 bis n-1.
slideshow7Bew4_2_4
Die n-1 nicht gewählten Felder streichen wir und nummerieren sie von 1 bis n-1.
slideshow7Bew4_2_5
Die n-1 nicht gewählten Felder streichen wir und nummerieren sie von 1 bis n-1.
slideshow7Bew4_2_6
Die n-1 nicht gewählten Felder streichen wir und nummerieren sie von 1 bis n-1.
slideshow7Bew4_2_7
Die n-1 nicht gewählten Felder streichen wir und nummerieren sie von 1 bis n-1.
slideshow7Bew4_2_8
Die n-1 nicht gewählten Felder streichen wir und nummerieren sie von 1 bis n-1.
In die k gewählten Kästchen tragen wir die k Kugeln ein.
slideshow7Bew4_2_10
Die n-1 nicht gewählten Felder streichen wir und nummerieren sie von 1 bis n-1.
In die k gewählten Kästchen tragen wir die k Kugeln ein.
slideshow7Bew4_2_11
Die n-1 nicht gewählten Felder streichen wir und nummerieren sie von 1 bis n-1.
In die k gewählten Kästchen tragen wir die k Kugeln ein.
Die Kugeln vor dem i-ten gestrichenen Feld entsprechen der i-ten Kugel.
slideshow7Bew4_2_9
Die n-1 nicht gewählten Felder streichen wir und nummerieren sie von 1 bis n-1.
In die k gewählten Kästchen tragen wir die k Kugeln ein.
Die Kugeln vor dem i-ten gestrichenen Feld entsprechen der i-ten Kugel.
slideshow7Bew4_2_12
Die n-1 nicht gewählten Felder streichen wir und nummerieren sie von 1 bis n-1.
In die k gewählten Kästchen tragen wir die k Kugeln ein.
Die Kugeln vor dem i-ten gestrichenen Feld entsprechen der i-ten Kugel.
slideshow7Bew4_2_13
Die n-1 nicht gewählten Felder streichen wir und nummerieren sie von 1 bis n-1.
In die k gewählten Kästchen tragen wir die k Kugeln ein.
Die Kugeln vor dem i-ten gestrichenen Feld entsprechen der i-ten Kugel.
slideshow7Bew4_2_14
Die n-1 nicht gewählten Felder streichen wir und nummerieren sie von 1 bis n-1.
In die k gewählten Kästchen tragen wir die k Kugeln ein.
Die Kugeln vor dem i-ten gestrichenen Feld entsprechen der i-ten Kugel.
slideshow7Bew4_2_15
Die n-1 nicht gewählten Felder streichen wir und nummerieren sie von 1 bis n-1.
In die k gewählten Kästchen tragen wir die k Kugeln ein.
Die Kugeln vor dem i-ten gestrichenen Feld entsprechen der i-ten Kugel.
slideshow7Bew4_2_16
Die n-1 nicht gewählten Felder streichen wir und nummerieren sie von 1 bis n-1.
In die k gewählten Kästchen tragen wir die k Kugeln ein.
Die Kugeln vor dem i-ten gestrichenen Feld entsprechen der i-ten Kugel.
slideshow7Bew4_2_17
Die n-1 nicht gewählten Felder streichen wir und nummerieren sie von 1 bis n-1.
In die k gewählten Kästchen tragen wir die k Kugeln ein.
Die Kugeln vor dem i-ten gestrichenen Feld entsprechen der i-ten Kugel.
Damit wurden k Kugeln aus einer Menge von n verschiedenen Kugeln ausgewählt, wobei die Kugeln auch mehrfach gezogen werden konnten.
slideshow7Bew4_2_18