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

From VoWi
< TU Wien:Algebra und Diskrete Mathematik UE (diverse)‎ | Übungen SS19
Revision as of 16:53, 7 March 2019 by Gittenborg (talk | contribs) (Gittenborg verschob die Seite TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen WS18/Beispiel 200 nach TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 200 und überschrieb dabei eine Weiterleitung: versch…)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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

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

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