TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2025W/Beispiel 205

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!)

Dieses Beispiel ist als solved markiert. Ist dies falsch oder ungenau? Aktualisiere den Lösungsstatus (Details: Vorlage:Beispiel)

Anmerkung

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

1. Schritt

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

2. Schritt

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 (\genfrac{}{}{0ex}{}{n+k-1}{k})=(\genfrac{}{}{0ex}{}{2+3-1}{3})=(\genfrac{}{}{0ex}{}{4}{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

Das selbe gilt für "fa":
Hier hat muss man aber k=5 mal aus der Multimenge ziehen.
Das ergibt $(\genfrac{}{}{0ex}{}{2+5-1}{5})=(\genfrac{}{}{0ex}{}{6}{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

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$:
$(\genfrac{}{}{0ex}{}{2+2-1}{2})=(\genfrac{}{}{0ex}{}{3}{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

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

Anmerkung von bbernhard1

Bei Schritt 3 hat sich meines Erachtens ein kleiner Rechenfehler eingeschlichen:
$(\genfrac{}{}{0ex}{}{6}{5})$ ergibt 6 und nicht 15.

Somit kommt man auf folgendes Endergebnis:
$5.040-720-24+6=4302$

Alternativer Lösungsvorschlag von Superwayne

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

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