Prinzip der Inklusion und Exklusion

10.06.2009, 11:18

Mr-Teddy

Prinzip der Inklusion und Exklusion

Auf wie viele Arten kann man die Buchstaben A, A, A,B,B,C,C,D,E, F permutieren,
so dass nie zwei gleiche Buchstaben nebeneinander stehen?

Ich weiß, dass man hier das Prinzip der Inklusion und Exklusion anwenden muss. Genau da liegt mein Problem, weil ich dieses nicht verstehe. Deswegen würde ich es gerne an der Aufgabe verstehen.

10.06.2009, 11:43

Auf diesen Beitrag antworten »

Dadurch, dass es nicht nur zwei sondern sogar drei A sind, muss man etwas weiter ausholen:

Zunächst mal erweist sich die Unterscheidung der drei A als notwendig, im Sinne einer einheitlichen Darstellung unterscheide ich mal alle Buchstaben voneinander, und zwar durch künstliches Anhängen eines Indizes:

$\begin{eqnarray*} A_1, A_2, A_3, B_1, B_2, C_1, C_2, D, E, F \end{eqnarray*}$

Dann gibt es $\begin{eqnarray*} 10! = 3\,628\,800 \end{eqnarray*}$ Permutationen dieser 10 nunmehr unterscheidbaren Buchstaben. Welche "einfachen" Ereignisse beschreiben nun das hier unerwünschte Verhalten des Nebeneinanderstehens zweier gleicher Buchstaben? Das sind

$\begin{eqnarray*} N_1 \end{eqnarray*}$ ... $\begin{eqnarray*} A_1 \end{eqnarray*}$ und $\begin{eqnarray*} A_2 \end{eqnarray*}$ stehen nebeneinander
$\begin{eqnarray*} N_2 \end{eqnarray*}$ ... $\begin{eqnarray*} A_1 \end{eqnarray*}$ und $\begin{eqnarray*} A_3 \end{eqnarray*}$ stehen nebeneinander
$\begin{eqnarray*} N_3 \end{eqnarray*}$ ... $\begin{eqnarray*} A_2 \end{eqnarray*}$ und $\begin{eqnarray*} A_3 \end{eqnarray*}$ stehen nebeneinander
$\begin{eqnarray*} N_4 \end{eqnarray*}$ ... $\begin{eqnarray*} B_1 \end{eqnarray*}$ und $\begin{eqnarray*} B_2 \end{eqnarray*}$ stehen nebeneinander
$\begin{eqnarray*} N_5 \end{eqnarray*}$ ... $\begin{eqnarray*} C_1 \end{eqnarray*}$ und $\begin{eqnarray*} C_2 \end{eqnarray*}$ stehen nebeneinander

Gesucht ist nun die Anzahl $\begin{eqnarray*} |(N_1 \cup N_2 \cup N_3 \cup N_4 \cup N_5)^c| \end{eqnarray*}$ , welche sich über die Siebformel (auch Inklusions-Exklusions-Formel genannt) bestimmen lässt.

Abschließend muss man dann die künstliche Unterscheidung wieder entfernen, und zwar durch Division der eben gewonnenen Anzahl durch $\begin{eqnarray*} 3! \cdot 2! \cdot 2! \end{eqnarray*}$ (das entspricht der Permutationenanzahl der A, B, C jeweils untereinander).

10.06.2009, 11:59

Mr-Teddy

Auf diesen Beitrag antworten »

Ich muss also von den $\begin{eqnarray*} 10! \end{eqnarray*}$ Permutationen $\begin{eqnarray*} N_1, N_2, N_3, N_4 und N_5 \end{eqnarray*}$ abziehen.

Schließe ich dann damit aber nicht nur die Permutationen aus, in denen einer der Bedingungen N erfüllt werden und lasse die, in denen mehrere N erfüllt werden außen vor?

10.06.2009, 12:42

Auf diesen Beitrag antworten »

Zitat:

Original von Mr-Teddy
Ich muss also von den $\begin{eqnarray*} 10! \end{eqnarray*}$ Permutationen $\begin{eqnarray*} N_1, N_2, N_3, N_4 und N_5 \end{eqnarray*}$ abziehen.

Nein, du sollst die Inklusions-Exklusions-Formel anwenden.

10.06.2009, 12:56

Mr-Teddy

Auf diesen Beitrag antworten »

Ja aber genau hier liegt ja mein Problem. Ich weiß, dass ich irgendwas abziehen und dann wieder hinzu addieren muss aber ich blick nich durch

10.06.2009, 13:03

Auf diesen Beitrag antworten »

Die Siebformel lautet

$\begin{eqnarray*} \left| \bigcup\limits_{k=1}^n N_k \right| = \sum\limits_{\substack{I\subseteq\{1,\ldots,n\}\\ I\neq \emptyset}} (-1)^{|I|-1} \left| \bigcap\limits_{i\in I} N_i \right| \end{eqnarray*}$

Du musst dich jetzt also der Anzahlberechnung der diversen Durchschnitte, wie etwa dem Dreierdurchschnitt

$\begin{eqnarray*} |N_1 \cap N_2 \cap N_4| \end{eqnarray*}$

usw. widmen. Alles nehme ich dir nicht ab, also wacker voran!

10.06.2009, 13:19

Mr-Teddy

Auf diesen Beitrag antworten »

Tut mir leid das hilft mir alles kein Stück. Es geht mir auch garnicht darum, dass irgendwer mir die Aufgabe abnimmt, mir wäre es nur ganz lieb gewesen, wenn mir jemand das Inklusion Exklusion Prinzip an dem Beispiel näher gebracht hätte.

10.06.2009, 13:29

Auf diesen Beitrag antworten »

Wo klemmt's denn genau?

(1) Verstehst du die Darstellung

$\begin{eqnarray*} \left| \bigcup\limits_{k=1}^n N_k \right| = \sum\limits_{\substack{I\subseteq\{1,\ldots,n\}\\ I\neq \emptyset}} (-1)^{|I|-1} \left| \bigcap\limits_{i\in I} N_i \right| \end{eqnarray*}$

nicht? Dem kann im hier betrachteten Fall n=5 abgeholfen werden, mit der mörderischen Expansion

$\begin{eqnarray*} |N_1 \cup N_2 \cup N_3 \cup N_4 \cup N_5| &=& |N_1| + |N_2| + |N_3| + |N_4| + |N_5| \\ &-& |N_1 \cap N_2| - |N_1 \cap N_3| - |N_1 \cap N_4| - |N_1 \cap N_5| - |N_2 \cap N_3| \\ && - |N_2 \cap N_4| - |N_2 \cap N_5| - |N_3 \cap N_4| - |N_3 \cap N_5| - |N_4 \cap N_5| \\ &+& |N_1 \cap N_2 \cap N_3| + |N_1 \cap N_2 \cap N_4| + |N_1 \cap N_2 \cap N_5| + |N_1 \cap N_3 \cap N_4| \\ && + |N_1 \cap N_3 \cap N_5| + |N_1 \cap N_4 \cap N_5| + |N_2 \cap N_3 \cap N_4| \\ && + |N_2 \cap N_3 \cap N_5| + |N_2 \cap N_4 \cap N_5| + |N_3 \cap N_4 \cap N_5| \\ &-& |N_1 \cap N_2 \cap N_3 \cap N_4| - |N_1 \cap N_2 \cap N_3 \cap N_5| - |N_1 \cap N_2 \cap N_4 \cap N_5| \\ && - |N_1 \cap N_3 \cap N_4 \cap N_5| - |N_2 \cap N_3 \cap N_4 \cap N_5| \\ &+& |N_1 \cap N_2 \cap N_3 \cap N_4 \cap N_5| \end{eqnarray*}$

(2) Oder geht es dir darum, warum man das überhaupt so macht? Das nutzt man natürlich nur in den Fällen, wo die Anzahlberechnung der Durchschnitte einfach bewerkstelligt werden kann. Und das ist hier der Fall - hier mal als Beispiel von zwei der zehn Dreierdurchschnitte:

$\begin{eqnarray*} |N_1 \cap N_2 \cap N_4| = 7! \cdot 2 \cdot 2! \end{eqnarray*}$

$\begin{eqnarray*} |N_1 \cap N_4 \cap N_5| = 7! \cdot 2!^3 \end{eqnarray*}$ .

10.06.2009, 14:45

Mr-Teddy

Auf diesen Beitrag antworten »

Und wie kommst du auf solche Ergebnisse, wie bei $\begin{eqnarray*} |N_1 \cap N_2 \cap N_4| \end{eqnarray*}$ ?
Ich weiß ich hab echt keine Ahnung aber ich hatte heute das erste mal mit dem Thema zu tun

10.06.2009, 14:53

Auf diesen Beitrag antworten »

Zitat:

Original von Mr-Teddy
Ich weiß ich hab echt keine Ahnung aber ich hatte heute das erste mal mit dem Thema zu tun

Keine Kombinatorik in der Schule - und wieso studierst du dann schon? Augenzwinkern

---------------------------

$\begin{eqnarray*} N_1\cap N_2 \end{eqnarray*}$ bedeutet, dass die drei A nebeneinander stehen, mit $\begin{eqnarray*} A_1 \end{eqnarray*}$ in der Mitte (also $\begin{eqnarray*} A_2 A_1 A_3 \end{eqnarray*}$ oder $\begin{eqnarray*} A_3 A_1 A_2 \end{eqnarray*}$ ), und $\begin{eqnarray*} N_4 \end{eqnarray*}$ bedeutet eben, dass die beiden B nebeneinanderstehen (also $\begin{eqnarray*} B_1 B_2 \end{eqnarray*}$ oder $\begin{eqnarray*} B_2 B_1 \end{eqnarray*}$ ), z.B. sowas

$\begin{eqnarray*} \fbox{$C_2$} \fbox{$D$} \fbox{$A_3 A_1 A_2$} \fbox{$E$} \fbox{$B_2 B_1$} \fbox{$F$} \fbox{$C_1$} \end{eqnarray*}$

Die von mir markierten 7 Blöcke kannst du nun beliebig permutieren, es kommt immer wieder eine Konfiguration raus, die zu $\begin{eqnarray*} N_1\cap N_2 \cap N_4 \end{eqnarray*}$ gehört. Außerdem hast du innerhalb des A-Blocks bzw. B-Blocks wie bereits erwähnt jeweils zwei Möglichkeiten für die Anordnungen der As und Bs.

10.06.2009, 15:54

Mr-Teddy

Auf diesen Beitrag antworten »

Achso, oh man, eigentlich ja voll logisch ^^

Gut, also sehe ich es richtig, dass
$\begin{eqnarray*} |N_1 \cap N_2 \cap N_3| = 0 \end{eqnarray*}$ ist?

Dann käme ich auf:

$\begin{eqnarray*} |N_1 \cup N_2 \cup N_3 \cup N_4 \cup N_5| &=& 9! + 9! + 9! + 9! - (8! * 2) - (8! * 2) - (8! * 2 * 2) - (8! * 2 * 2) - (8! * 2) - (8! * 2 * 2) - (8! * 2 * 2) - (8! * 2) - (8! * 2) - (8! * 2) + 0 + (7! * 2 * 2) + (7! * 2 * 2) + (7! * 2 * 2) (7! * 2 * 2) + (7! * 2 * 2 * 2) + (7! * 2 * 2) + (7! * 2 * 2) + (7! * 2 * 2 * 2) + (7! * 2 * 2 * 2) - 0 - 0 - (6! * 2 * 2 * 2) - (6! * 2 * 2 * 2) - (6! * 2 * 2 * 2) + 0 \end{eqnarray*}$

Und die Lösung davon muss ich dann mit 3! * 2! * 2! dividieren.

Stimmt das oder lieg ich wieder daneben?

10.06.2009, 15:57

Auf diesen Beitrag antworten »

Zitat:

Original von Mr-Teddy
Gut, also sehe ich es richtig, dass
$\begin{eqnarray*} |N_1 \cap N_2 \cap N_3| = 0 \end{eqnarray*}$ ist?

Rcihtig, denn die drei A können nicht alle wechselseitig benachbart sein.

Zitat:

Original von Mr-Teddy
$\begin{eqnarray*} |N_1 \cup N_2 \cup N_3 \cup N_4 \cup N_5| &=& 9! + 9! + 9! + 9! - (8! * 2) - (8! * 2) - (8! * 2 * 2) - (8! * 2 * 2) - (8! * 2) - (8! * 2 * 2) - (8! * 2 * 2) - (8! * 2) - (8! * 2) - (8! * 2) + 0 + (7! * 2 * 2) + (7! * 2 * 2) + (7! * 2 * 2) (7! * 2 * 2) + (7! * 2 * 2 * 2) + (7! * 2 * 2) + (7! * 2 * 2) + (7! * 2 * 2 * 2) + (7! * 2 * 2 * 2) - 0 - 0 - (6! * 2 * 2 * 2) - (6! * 2 * 2 * 2) - (6! * 2 * 2 * 2) + 0 \end{eqnarray*}$

Oje, rechne das mal bitte aus, dann kann ich vergleichen.

Zitat:

Original von Mr-Teddy
Und die Lösung davon muss ich dann mit 3! * 2! * 2! dividieren.

So ist es, damit streichst du die zwischenzeitlich benötigten "Hilfsindizes" wieder weg. Freude

Beachte aber bitte, dass du damit die Anzahl der Anordnungen bestimmt hast, wo es benachbarte gleiche Buchstaben gibt. Gesucht in der Aufgabe war gerade das Gegenteil!

10.06.2009, 16:05

Mr-Teddy

Auf diesen Beitrag antworten »

Also wenn ich mich nicht verrechnet habe, käme ich dann auf 22.800

10.06.2009, 16:17

Auf diesen Beitrag antworten »

Da hab ich was ganz anderes raus. Ich stell mal kurz meine Rechnung vor:

Die Symmetrie von $\begin{eqnarray*} N_1,N_2,N_3 \end{eqnarray*}$ einerseits und $\begin{eqnarray*} N_4,N_5 \end{eqnarray*}$ andererseits in der Anzahlberechnung berücksichtigend, vereinfacht sich die obige Siebformel im vorliegenden Problem zu

$\begin{eqnarray*} |N_1 \cup N_2 \cup N_3 \cup N_4 \cup N_5| &=& 5|N_1| - 3|M| - 7|N_1 \cap N_4| + 6|M \cap N_4| + 3|N_1 \cap N_4 \cap N_5| - 3|M \cap N_4 \cap N_5| \\ &=& 5\cdot 2\cdot 9! - 3\cdot 2\cdot 8! - 7\cdot 2^2 \cdot 8! + 6\cdot 2^2 \cdot 7! + 3 \cdot 2^3 \cdot 7! - 3\cdot 2^3 \cdot 6! = 2\,482\,560 \end{eqnarray*}$ ,

dabei soll $\begin{eqnarray*} M=N_1\cap N_2 \end{eqnarray*}$ exemparisch für diese A-Dreierblöcke stehen. Für die gesuchte Anzahl ergibt das dann, Komplement sowie Division durch $\begin{eqnarray*} 3!\cdot 2!\cdot 2! \end{eqnarray*}$ berücksichtigend:

$\begin{eqnarray*} \frac{10!-2\,482\,560}{3!\cdot 2!\cdot 2!} = 95\,520 \end{eqnarray*}$

10.06.2009, 16:34

Mr-Teddy

Auf diesen Beitrag antworten »

Ich hab zwei kleine Leichtsinnsfehler ^^ Aber jetzt weiß ich wie man auf die Lösung kommt. Hoffentlich kann ich das jetzt auch auf andere Aufgaben anwenden.
Vielen Dank für die Hilfe

Neue Frage »

Antworten »

Prinzip der Inklusion und Exklusion

Verwandte Themen