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

Aus VoWi
Zur Navigation springen Zur Suche springen

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[Bearbeiten]

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[Bearbeiten]

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