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

Man bestimme die Anzahl aller Anordnungen (Permutationen) der Buchstaben a,b,c,d,e,f,g,h in denen weder der Block "acg" noch der Block "cgbe" 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)

Lösungsvorschlag von mnemetz

Betrachte

$\underbrace {\text{a b c d e f g h}} _{\text{8 Auswahlen o. Wh.}}$

Daraus folgt: $n=8$: Alle Möglichkeiten, die 8 Buchstaben anzuordnen ist 8! = 40.320.

Betrachte Anordnungsmöglichkeiten Block "acg":

${\text{6 Anordnugen mögl. }}{\begin{cases}\underbrace {\begin{matrix}a&b&c&d&e&f&g&h\\X&X&X&&&&&\\-&X&X&X&&&&\\-&-&X&X&X&&&\\-&-&-&X&X&X&&\\-&-&-&-&X&X&X&\\-&-&-&-&-&X&X&X\\\end{matrix}} _{\text{5 Buchst. anordbar}}\end{cases}}$

Somit ergibt sich für die Anodnungsmöglichkeiten von "acg":

$6*5!=720$

Die Anzahl aller Anordnungen (Permutationen) der Buchstaben a,b,c,d,e,f,g,h in denen der Block "acg" nicht vorkommt ist somit: $8!-5*6!=40320-720=39600$.

Betrachte Anordnungsmöglichkeiten Block "cgbe":

${\text{5 Anordnugen mögl. }}{\begin{cases}\underbrace {\begin{matrix}a&b&c&d&e&f&g&h\\X&X&X&X&&&&\\-&X&X&X&X&&&\\-&-&X&X&X&X&&\\-&-&-&X&X&X&X&\\-&-&-&-&X&X&X&X\\\end{matrix}} _{\text{4 Buchst. anordbar}}\end{cases}}$

Somit ergibt sich für die Anodnungsmöglichkeiten von "cgbe":

$5*4!=120$

Die Anzahl aller Anordnungen (Permutationen) der Buchstaben a,b,c,d,e,f,g,h in denen der Block "cgbe" nicht vorkommt ist somit: $8!-5*4!=40320-120=40200$.

Anm Student123: nicht ganz vollständig! siehe unten!

---

Siehe auch: TU Wien:Mathematik 1 UE (diverse)/Übungen WS06/Beispiel 160, TU Wien:Mathematik 1 UE (diverse)/Übungen WS06/Beispiel 161

Lösungsvorschlag von Jacko

Anzahl der Anordnungen

Menge: a,b,c,d,e,f,g,h -> n=8

Permutationen: n! = 8! = 40320

Möglichkeiten für Block "acg"

Positionsmöglichkeiten:

${\text{6 Anordnugen mögl. }}{\begin{cases}\underbrace {\begin{matrix}a&c&g&-&-&-&-&-\\-&a&c&g&-&-&-&-\\-&-&a&c&g&-&-&-\\-&-&-&a&c&g&-&-\\-&-&-&-&a&c&g&-\\-&-&-&-&-&a&c&g\\\end{matrix}} _{\text{5 Buchst. anordbar}}\end{cases}}$

-> 6*5! = 720

Möglichkeiten für Block "cgbe"

Positionsmöglichkeiten:

${\text{5 Anordnugen mögl. }}{\begin{cases}\underbrace {\begin{matrix}c&g&b&e&-&-&-&-\\-&c&g&b&e&-&-&-\\-&-&c&g&b&e&-&-\\-&-&-&c&g&b&e&-\\-&-&-&-&c&g&b&e\\\end{matrix}} _{\text{4 Buchst. anordbar}}\end{cases}}$

-> 5*4! = 120

Möglichkeiten für Block "acgbe"

Da auch beide Blöcke vorkommen können besteht die Möglichkeit, dass sich diese überschneiden (ac(g)be).

Positionsmöglichkeiten:

${\text{4 Anordnugen mögl. }}{\begin{cases}\underbrace {\begin{matrix}a&c&g&b&e&-&-&-\\-&a&c&g&b&e&-&-\\-&-&a&c&g&b&e&-\\-&-&-&a&c&g&b&e\\\end{matrix}} _{\text{3 Buchst. anordbar}}\end{cases}}$

-> 4*3! = 24

Berechnung der tatsächlichen Möglichkeiten

Hierzu wird das Inklusions-Exklusions Verfahren verwendet.

Sei 8! = |G|

Möglichkeiten für Block "acg" ... |A|

Möglichkeiten für Block "cgbe" ... |B|

Möglichkeiten für Block "acgbe" ... |AnB|

|G| - |A| - |B| + |AnB| = 8! - 6*5! - 5*4! + 4*3! = 40320 - 720 - 120 + 24 = 39 504

Anm:Student123 Diese Lösung ist laut Tutor richtig, da sie die Möglichkeiten für Block "acgbe" berücksichtigt, welche sonst nicht vorkommen, da sie 1 mal dazugerechnet werden (bei |G|) aber 2 mal abgezogen werden (- |A| - |B|).