Überblick

In der Kombinatorik ist es häufig am einfachsten ein Problem mit dem zugehörigen Urnenmodell in Verbindung zu bringen, von dem man die Lösung bereits kennt. Wir kennen folgende Urnenmodelle:

In einer Urne befinden sich \(n\) Kugeln

  1. Es wird \(k\)-mal gezogen unter Berücksichtigung der Reihenfolge mit Zurücklegen der Kugel: \[k\text{-Tupel aus einer }n\text{-Menge}\]
  2. Es wird \(k\)-mal gezogen unter Berücksichtigung der Reihenfolge ohne Zurücklegen der Kugel: \[k\text{-Permutation aus einer }n\text{-Menge}\]
  3. Es wird \(k\)-mal gezogen ohne Berücksichtigung der Reihenfolge ohne Zurücklegen der Kugel: \[k\text{-Teilmenge aus einer }n\text{-Menge}\]

Die zugehörige Anzahl der Ergebnisse ist:

\( \begin{array} 11. &n^k & \text{dabei darf } k \text{ auch größer als } n \text{ sein.} & \text{Beispiele: Zahlenschloss, Spielautomat, …} \\ 2. &\frac{n!}{(n-k)!} & \text{hier ist } n \ge k \text{.} & \text{Beispiele: Hunderennen, Pferderennen, Parkplatz-Stellplätze, …}\\ 3. &{n\choose k} & \text{auch hier gilt } n \ge k \text{.} & \text{Beispiele: Lotto} \end{array} \)

Permutationen gibt es
ohne Wiederholungen (Jedes Objekt tritt nur einmal auf)
mit Wiederholungen (MISSISSIPPI-Problem) (Objekte können mehrfach auftreten)

Beispielaufgaben:

  1. Vier Personen halten jeder ein Sektglas in der Hand. Jeder stößt mit jedem genau einmal an. Bestimmen Sie die Anzahl der Anstoßvorgänge.
  2. Sieben Personen stellen sich in einer Reihe auf. Geben Sie an, wie viele Möglichkeiten es dafür gibt?
  3. Die sieben Personen stellen sich nun im Kreis auf. Erläutern Sie, wie Sie das Ergebnis aus Aufgabe 2 hierfür modifizieren müssen, um die Anzahl der möglichen Aufstellungen zu erhalten. Bestimmen Sie auch die neue Anzahl der Aufstellungen im Kreis.
  4. Aus dem Wort „Seestern“ sollen Anagramme gebildet werden. Bestimmen Sie jeweils die zugehörige Anzahl von Anagrammen:
    1. Keine weiteren Einschränkungen.
    2. Das Anagramm soll mit E beginnen.
    3. Das Anagramm soll mit T enden.

Lösungen

Lösung 1:

Person 1 muss mit \(3\) Personen anstoßen, Person 2 mit \(2\) Personen, Person 3 mit einer Person, Person 4 hat damit bereits mit allen angestoßen: \(3+2+1=6\) Möglichkeiten.

Lösung 2:

Wir „ziehen“ zwei Personen aus einer Urne mit den \(4\) Personen, diese stoßen miteinander an. Die zugehörige Anzahl ist \({4 \choose 2}=6\).

Wir betrachten eine \(7\)-Permutation aus einer \(7\)-Menge, hierfür gibt es \(7!=5040\) Möglichkeiten.

Jeweils \(7\) Aufstellungen in der Reihe sind im Kreis identisch (es ist egal, wo im Kreis sich die erste Person hinstellt). Man muss die Anzahl aus 2. also durch \(7\) dividieren. Damit bleiben \(\frac{7!}{7}=6!=720\) Möglichkeiten.

  1. Wir betrachten Permutationen einer \(8\)-Menge, wobei ein Buchstabe dreifach (e) und einer doppelt (s) auftritt. Die Formel liefert \(\frac{8!}{3!\cdot 2!}=3360\) Möglichkeiten.
  2. Es bleiben noch \(6\) Buchstaben übrig, davon kommen nun zwei Buchstaben doppelt vor (e und s). Es folgt \(\frac{6!}{2!\cdot 2!}=1260\).
  3. Analog zu b. bleiben \(6\) Buchstaben, wie in a. ist aber einer dreifach (e) und einer doppelt (s) vorhanden. Es gibt also \(\frac{6!}{3!\cdot 2!}=420\) solcher Anagramme.
Weiter
Zurück