TU Wien:Mathematik 1 UE (diverse)/Übungen WS06/Beispiel 162

Angabe

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

Lösungsvorschlag von mnemetz

Betrachte

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

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{array}{c}\underset{\text{5 Buchst. anordbar}}{\underbrace{\begin{array}{cccccccc}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{array}}}\end{array}$

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

$6\ast 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\ast 6!=40320-720=39600$.

Betrachte Anordnungsmöglichkeiten Block "cgbe":

$\text{5 Anordnugen mögl. }\{\begin{array}{c}\underset{\text{4 Buchst. anordbar}}{\underbrace{\begin{array}{cccccccc}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{array}}}\end{array}$

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

$5\ast 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\ast 4!=40320-120=40200$.

---

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{array}{c}\underset{\text{5 Buchst. anordbar}}{\underbrace{\begin{array}{cccccccc}a& c& g& -& -& -& -& -\\ -& a& c& g& -& -& -& -\\ -& -& a& c& g& -& -& -\\ -& -& -& a& c& g& -& -\\ -& -& -& -& a& c& g& -\\ -& -& -& -& -& a& c& g\end{array}}}\end{array}$

-> 6*5! = 720

Möglichkeiten für Block "cgbe"

Positionsmöglichkeiten:

$\text{5 Anordnugen mögl. }\{\begin{array}{c}\underset{\text{4 Buchst. anordbar}}{\underbrace{\begin{array}{cccccccc}c& g& b& e& -& -& -& -\\ -& c& g& b& e& -& -& -\\ -& -& c& g& b& e& -& -\\ -& -& -& c& g& b& e& -\\ -& -& -& -& c& g& b& e\end{array}}}\end{array}$

-> 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{array}{c}\underset{\text{3 Buchst. anordbar}}{\underbrace{\begin{array}{cccccccc}a& c& g& b& e& -& -& -\\ -& a& c& g& b& e& -& -\\ -& -& a& c& g& b& e& -\\ -& -& -& a& c& g& b& e\end{array}}}\end{array}$

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