TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 198

Aus VoWi
Wechseln zu: Navigation, Suche

Man bestimme die Anzahl aller Anordnungen (Permutationen) der Buchstaben a,b,c,d,e,f,g in denen weder der Block "abcd" noch der Block "fa" vorkommt. (Hinweis: Die Anzahl der Permutationen einer n-elementigen Menge ist n!)

Anmerkung[Bearbeiten]

Das Beispiel ist praktisch gleich wie dieses Beispiel aus vorhergegangenen Semestern. Der Unterschied ist nur, dass der Buchstabe 'h' in der Angabe fehlt

Lösungsvorschlag[Bearbeiten]

1. Schritt[Bearbeiten]

Anzahl der möglichen Permutationen berechnen, die auftreten können:
7! = 5.040

2. Schritt[Bearbeiten]

Man überlegt sich, wie oft "abcd" in den Permutationen vorkommen kann. Das kann man auf eine Permutation einer Teilmultimenge zurückführen.
D.h. man hat n=2 Plätze, an denen die restlichen Buchstaben auftreten können und man muss k=3 mal ziehen, weil aus den 7 Buchstaben "abcd" bereits belegt ist.
\Rightarrow {n +k -1 \choose k} = {2+3-1 \choose 3} = {4 \choose 3}= 4
Und für jede diese Kombination kann noch eine Permutation von (7-4)!=3! auftreten, weil an jeder nicht belegten Stelle 3 unterschiedliche Buchstaben auftreten können

Das ergibt 4 \cdot 3! = 24 Permutationen

3. Schritt[Bearbeiten]

Das selbe gilt für "fa":
Hier hat muss man aber k=5 mal aus der Multimenge ziehen.
Das ergibt {2+5-1 \choose 5} = {6 \choose 5}= 15
Und wieder gibt es für jede dieser Möglichkeiten (7-2)!=5! Permutationen der restlichen Stellen

Das ergibt 15 \cdot 5! = 1800 Permutationen

4. Schritt[Bearbeiten]

Jetzt gibt es aber nur noch das Problem, dass die Buchstabenkombination "fabcd" sowohl im zweiten als auch dritten Schritt berücksichtigt haben. Man muss also jetzt noch feststellen, wie oft "fabcd" vorkommen kann. Diesmal ist unser k=7-5=2:
{2+2-1 \choose 2} = {3 \choose 2}= 3

Das ergibt wieder für jede dieser Möglichkeiten (7-5)!=2! Permutationen der restlichen Stellen.
Das sind 3 \cdot 2! = 6 Permutationen

5. Schritt[Bearbeiten]

Jetzt endlich kann man die Siebformel anwenden um auf das Ergebnis zu kommen:
{5.040 - 1800 - 24 + 12 = 3.228 \qquad }

Anmerkung von bbernhard1[Bearbeiten]

Bei Schritt 3 hat sich meines Erachtens ein kleiner Rechenfehler eingeschlichen:
{6 \choose 5} ergibt 6 und nicht 15.

Somit kommt man auf folgendes Endergebnis:
{5.040 - 720 - 24 + 6 = 4302 \qquad }

Alternativer Lösungsvorschlag von Superwayne[Bearbeiten]

Man kann das Beispiel auch rein mit Permutation einer n-elementigen Menge rechnen, wie es auch die Angabe suggeriert:

  1. \{ a, b, c, d, e, f, g \} \Rightarrow 7!
  2. \{ b, c, d, e, fa, g \} \Rightarrow 6!
  3. \{ abcd, e, f, g \} \Rightarrow 4!
  4. \{ e, g, fabcd \} \Rightarrow 3!

Von der gesamten Menge 7! muss man demnach 6! und 4! abziehen, da wir diese Möglichkeiten ausschließen, 3! aber addieren, da Permutationen "fabcd" in beiden Permutation vorkommt und deshalb zu oft abgezogen wurde:

7! - 6! - 4! + 3! = 4302

-- Superwayne 19:51, 30. Nov. 2014 (CET)

Link zu ähnlichem Beispiel[Bearbeiten]

TU Wien:Mathematik 1 UE (diverse)/Übungen WS07/Beispiel 169