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

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

Dieses Beispiel ist als solved markiert. Ist dies falsch oder ungenau? Aktualisiere den Lösungsstatus (Details: Vorlage:Beispiel)

Lösungsvorschlag von mnemetz

(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

Also:

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 _{i=1}^{3}A_{i}\right|={\underset {720}{\underbrace {\sum _{i=1}^{n}\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

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

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

Ähnliche Beispiele:

Beispiel_168, 
Beispiel_170

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