Permutationen ohne best. Zeichenfolgen

Neue Frage »

10.05.2006, 21:00	Thomander	Auf diesen Beitrag antworten »
Permutationen ohne best. Zeichenfolgen Hallo, ich habe hier eine Aufgabe: Auf wie viele Weisen lassen sich die Buchstaben des Wortes INFORMATIK anordnen, so dass die Anordnung keines der Teilwörter KINO, NOT, MAI und TOR enthält? Da in INFORMATIK zwei I vorkommen, gibt es insgesamt 10!/2! mögliche Permutationen, oder? Aber wie bekomme ich jetzt heraus, in welchen dieser Permutationen z.B. KINO nicht vorkommt? Kann es sein, dass es 7 * 6! (also 7!) Permutationen gibt, in denen KINO vorkommt? Ich habe mir das nämlich so gedacht: KINOXXXXXX bis XXXXXXKINO das wären doch 7 mal 6! Möglichkeiten, Permutationen mit KINO zu erzeugen... Wenn das so stimmt, muss ich das dann für die anderen Teilwörter auch machen und die Ergebnisse zusammzählen? Dabei kann es doch sein, dass KINO und MAI in ein und derselben Permutation vorkommen... Diese zähle ich doch dann doppelt... mfg Thomander
10.05.2006, 21:07	AD	Auf diesen Beitrag antworten »
Erstmal ein paar Mengen einführen: $\begin{eqnarray} \Omega \end{eqnarray}$ ... Menge aller Permutationen von INFORMATIK $\begin{eqnarray} A_1 \end{eqnarray}$ ... Menge aller Permutationen von INFORMATIK, die KINO enthalten $\begin{eqnarray} A_2 \end{eqnarray}$ ... Menge aller Permutationen von INFORMATIK, die NOT enthalten $\begin{eqnarray} A_3 \end{eqnarray}$ ... Menge aller Permutationen von INFORMATIK, die MAI enthalten $\begin{eqnarray} A_4 \end{eqnarray}$ ... Menge aller Permutationen von INFORMATIK, die TOR enthalten Was du suchst, ist die Anzahl $\begin{eqnarray} \|\Omega\setminus(A_1\cup A_2\cup A_3\cup A_4)\| = \|\Omega\|-\|A_1\cup A_2\cup A_3\cup A_4\| \end{eqnarray}$ So, den einfachen Teil $\begin{eqnarray} \|\Omega\|=\frac{10!}{2!} \end{eqnarray}$ hast du bereits. Und zur Berechnung der Vereinigung kannst du die Einschluss-Ausschluss-Formel heranziehen.
10.05.2006, 21:44	Thomander	Auf diesen Beitrag antworten »
OK, die Mengen habe ich, ist ja eigentlich kein Problem. \|A1\|=7! \|A2\|=8! \|A3\|=8! \|A4\|=8! Für die Einschluss-Ausschlussformel benötige ich aber auch die Schnittmengen. Wie berechne ich die Kardinalität der Schnittmengen z.B. von A1 und A2 oder von A1 und A3?
10.05.2006, 21:53	AD	Auf diesen Beitrag antworten »
Stimmt nicht ganz: \|A1\|=7! , Permutationen der 7 Blöcke KINO , A , F , I , M , R , T \|A2\|=8!/2 , Permutationen der 8 Blöcke NOT, A , F , I , I , K , M , R \|A3\|=8! , Permutationen der 8 Blöcke MAI , F , I , K , N , O , R , T \|A4\|=8!/2 , Permutationen der 8 Blöcke TOR , A , F , I , I , K , M , N Und nun zu den Durchschnitten, da gebe ich mal drei verschiedene Beispiele: $\begin{eqnarray} A_1 \cap A_2 \end{eqnarray}$ ... Permutationen der 6 Blöcke KINOT , A , F , I , M , R $\begin{eqnarray} A_1 \cap A_3 \end{eqnarray}$ ... Permutationen der 5 Blöcke KINO , MAI , F , R , T $\begin{eqnarray} A_2 \cap A_4 \end{eqnarray}$ ... keine Permutationen, da NOT und TOR nicht gemeinsam vorkommen können usw.
10.05.2006, 22:11	Thomander	Auf diesen Beitrag antworten »
Merci, ich habs jetzt. Die Zahl aller möglichen Permutationen: 1 814 400 Die Zahl der P. ohne die Teilwörter: 84 192 Kann das sein? Die meisten Schnitte ergaben 0, da nur der Schnitt der 3 Mengen A1, A2 und A3 keine Leere Menge ergab. Der Schnitt aller Mengen war auch wieder die leere Menge...
10.05.2006, 22:15	AD	Auf diesen Beitrag antworten »
Also ich komme auf 83424 Permutationen mit wenigstens einem der Teilwörter - kann mich aber auch verrechnet haben. EDIT: Das mit den Dreier- und Viererschnitten ist richtig, nur $\begin{eqnarray} \|A_1\cap A_2\cap A_3\|=4! \end{eqnarray}$ ergibt was von Null verschiedenes.
Anzeige

10.05.2006, 22:17	Thomander	Auf diesen Beitrag antworten »
Mit wenigstens einem der Teilwörter? Oder ohne eines der Teilwörter?
10.05.2006, 22:19	AD	Auf diesen Beitrag antworten »
So wie ich es gesagt habe: $\begin{eqnarray} \|A_1\cup A_2\cup A_3\cup A_4\|=83424 \end{eqnarray}$ , und Vereinigung der $\begin{eqnarray} A_i \end{eqnarray}$ heißt, dass wenigstens eins der $\begin{eqnarray} A_i \end{eqnarray}$ eintritt.
10.05.2006, 22:37	Thomander	Auf diesen Beitrag antworten »
Sorry, hatte mich verrechnet...

Neue Frage »

Antworten »

Permutationen ohne best. Zeichenfolgen

Verwandte Themen