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

Aus VoWi
Wechseln zu: Navigation, Suche

Man bestimme die Anzahl aller Anordnungen (Permutationen) der Buchstaben a,b,c,d,e,f, in denen weder der Block "bcf" noch der Block "eb" vorkommt. (Hinweis: Die Anzahl der Permutationen einer n-elementigen Menge ist n!).

Lösungsvorschlag von mnemetz[Bearbeiten]

(Anm: Die Angabe wurde tw. mit Beispiel 170 verwurschtelt, siehe auch Lösung von Baccus)

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 "bcf":

\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 "bcf":

6*5! = 720

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

Betrachte Anordnungsmöglichkeiten Block "eb":

\text{7 Anordnungen 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 \\
\end{matrix}}_{\text{6 Buchst. anordbar}}
\end{cases}

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

7*6! = 5040

Die Anzahl aller Anordnungen (Permutationen) der Buchstaben a,b,c,d,e,f,g,h in denen der Block "eb" nicht vorkommt ist somit:  8! - 7*6! = 40320 - 5040 = 35280.

Lösung von Baccus[Bearbeiten]

Hilfreiches[Bearbeiten]

Baustein:Permutation

Baustein:Fakultät

Baustein:Siebformel

Also:[Bearbeiten]

Gefragt ist eine Permutation von {"a", "b", "c", "d", "e", "f"}, \{"bcf"}, \{"eb"}; dabei ist zu beachten, daß "bcf" und "eb" zusammen als "ebcf" vorkommen kann.

Die Menge hat 6 Elemente, die Anzahl aller möglichen Permutationen der Menge ist also 6! = 720.

  • "bcf" fix:
    • noch 3 Stellen permutierbar, 3! = 6;
    • auf 4 Arten anordbar (s.o.): 4*3! = 24 Möglichkeiten.
  • "eb" fix:
    • noch 4 Stellen permutierbar, 4! = 24;
    • auf 5 Arten anordbar: 5*4! = 120 Möglichkeiten.
  • "ebcf" fix:
    • noch 2 Stellen permutierbar, 2! = 2;
    • auf 3 Arten anordbar: 3*2! = 6 Möglichkeiten.

Inkl/Exkl-Prinzip (Siebformel):

\left|\bigcup^3_{i=1} A_i\right|=
\underset{720}{\underbrace{\sum^n_{i=1}\left|A_i\right|}}-
\underset{24+120}{\underbrace{\sum_{i<j}\left|A_i\cap A_j\right|}}+
\underset{6}{\underbrace{\sum_{i<j<k}\left|A_i\cap A_j\cap A_k\right|}}

720 - (24 + 120) + 6 = 582 Anordnungen sind möglich.

--Baccus 00:41, 2. Dez 2006 (CET)

Lösung von Hapi[Bearbeiten]

Die Menge beträgt nur 6 Buchstaben und es gibt noch die Anordnung ebcf !!!

Lösungsweg grundsätzlich richtig, aber die Anzahl der Elemente ist nicht 8 sonder 6!!

1. Anzahl der Permutationen der Buchstaben a-f (6 Stück) ist 6! bzw. 720

2. Anordnungen des Blocks "bcf" auf insgesamt 4 Positionen. Die Anordnung wird mit der Permutation der restlichen 3 Buchstaben aufgefüllt. = 4*3! = 4*6 = 24

3. Anordnungen des Blocks "eb" auf insgesamt 5 Positionen. Die Anordnung wird mit der Permutation der restlichen 4 Buchstaben aufgefüllt. = 5*4! = 5*24 = 120

4. Jetzt sind noch die Anordungen von ebcf zu berücksichtigen, die nach dem Inklusions-Exklusionsprinzip 2 mal herausgenommen wurden: 4 Buchstaben können an 3 Positionen stehen und werden mit 2 Zeichen aufgefüllt, also 3 * 2! = 6

5. Gesamtsumme abzüglich Anordnungen, die nicht vorkommen dürfen, zuzüglich der doppelten Anordnungen:

  720 - 24 - 120 + 6 = 582

Hapi

Lösung von Superwayne[Bearbeiten]

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 \} \Rightarrow 6!
  2. \{ a, bcf, d, e \} \Rightarrow 4!
  3. \{ a, c, d, eb, f \} \Rightarrow 5!
  4. \{ a, d, ebcf \} \Rightarrow 3!

Von der gesamten Menge 6! muss man demnach 4! und 5! abziehen, da wir diese Möglichkeiten ausschließen, 3! aber addieren, da Permutationen "ebcf" in beiden Permutation vorkommt und deshalb zu oft abgezogen wurde:

6! - 5! - 4! + 3! = 582

-- Superwayne 11:20, 27. Nov. 2014 (CET)

Links zu ähnlichen Beispielen[Bearbeiten]

Ähnliche Beispiele:

Beispiel_168, 
Beispiel_170

TU Wien:Mathematik 1 UE (diverse)/Übungen WS10/Beispiel 187