Vertauschungsproblem bei Kombinatorikaufgabe

13.08.2006, 14:16

Bobo

Vertauschungsproblem bei Kombinatorikaufgabe

Ich wollte die Menge aller Möglichkeiten bei einer (selbstgestellten (vielleicht gehts auch gar nicht)) Kombinatorik-Aufgabe ausrechnen:

Es gibt Kugeln in fünf verschiedenen Farben: rot, blau, grün, gelb, lila. i (i>4) von diesen Kugeln werden von links nach rechts aufgereiht. Es dürfen aber maximal vier verschiedene Farben in der Reihe vorkommen, wobei nie eine gelbe ganz rechts stehen darf. Wie viel verschiedene Möglichkeiten gibt es die Kugeln aneinanderzureihen in abhängigkeit von i.
Ich hoffe, dass die Aufgabe einmal einmal eindeutig ist. ^^

Ich habs übers Gegenereignis versucht:
Für die Stelle ganz rechts gibt es 4 Möglichkeiten, links davon wieder 4, dann 3, dann 2, dann 1. Für alle Weiteren gibt es 5 Möglichkeiten. Jetzt muss man das alles noch vertauschen... nur wie.
Insgesamt gibt es $\begin{eqnarray*} 4 \cdot 5^{i-1} \end{eqnarray*}$ Möglichkeiten, wenn man die Farbenbegrenzung ignoriert. Also ergibt sich:
$\begin{eqnarray*} 4 \cdot 5^{i-1} -4 \cdot 4! \cdot 5^{i-5} \cdot v \end{eqnarray*}$ mit v=Vertauschungen

Leider komm ich bei den Vertauschungen nicht weiter.
Danke für die Hilfe,
Bobo

13.08.2006, 14:42

JochenX

Auf diesen Beitrag antworten »

Nee, ich glaube, dein Ansatz ist etwas falsch, wieso z.B. sollten die 5 verschiedenen Farben des Gegenereignisses (das den einfachen Fall gelb ganz rechts ignoriert) direkt die 5 Plätze ganz links einnehmen?

Gehe wie "normal" vor.
Sei A die Menge ALLER günstigen Anordnungen, gesucht ist |A|.
Zerlege A disjunkt in A1, A2, A3, A4.
Dabei ist Aj die Menge der Anordnungen, die zusätzlich zu den Bedingungen von A erfüllen, dass genau j verschiedene Farben vorkommen. Dann ist $\begin{eqnarray*} |A|=\sum_{j=1}^{4}~|A_j| \end{eqnarray*}$

Ohne die Gelbnichtrechts-Einschränkung wärst du jetzt schon so gut wie fertig, denn offensichtlich wäre dann die Kardinalität von Aj gerade j^i.

Für die Gelbregel musst du noch etwas weiter einschränken, schwer ist das aber auch nicht.
Zerlege Aj wieder in 2 Teilmengen ("gelb kommt vor", "gelb kommt nicht vor").

Z.B. wird A1 zerlegt in zwei Teilmengen, eine mit Mächtigkeit 4, die andere mit Mächtigkeit 0, insgesamt ist |A1|=4, das war der poplige Teil.
Den Rest machst du, mehr als Nachdenken und Rechnen ist das nicht.

13.08.2006, 16:14

Auf diesen Beitrag antworten »

Zitat:

Original von LOED
Dabei ist Aj die Menge der Anordnungen, die zusätzlich zu den Bedingungen von A erfüllen, dass genau j verschiedene Farben vorkommen.

offensichtlich wäre dann die Kardinalität von Aj gerade j^i.

Hmm, "offensichtlich" berechnest du hier eine ganz andere Anzahl: Nämlich die der Anordnungen von $\begin{eqnarray*} i \end{eqnarray*}$ Kugeln, wo jede mit einer von $\begin{eqnarray*} j \end{eqnarray*}$ festgelegten Farben gefärbt ist. Zum einen müssen dann in der Anordnung nicht alle $\begin{eqnarray*} j \end{eqnarray*}$ Farben auftreten, zum anderen ist die Festlegung von $\begin{eqnarray*} j \end{eqnarray*}$ festen aus den 5 Farben nicht ganz das, was die Aufgabenstellung besagt...

Nein, hier muss wieder unser guter alter Freund, die Siebformel ran. Wie Jochen lasse ich vorerst die Bedingung, dass ganz rechts keine gelbe Kugel steht, mal weg:

Im Grundraum $\begin{eqnarray*} \Omega=\{1,2,3,4,5\}^i \end{eqnarray*}$ fragen wir nach der Mächtigkeit der Menge

$\begin{eqnarray*} M \end{eqnarray*}$ ... $\begin{eqnarray*} i \end{eqnarray*}$ -Tupel, die maximal 4 der 5 Farben enthalten.

Mit den Mengen

$\begin{eqnarray*} M_k \end{eqnarray*}$ ... $\begin{eqnarray*} i \end{eqnarray*}$ -Tupel, die Farbe $\begin{eqnarray*} k \end{eqnarray*}$ nicht enthalten

kann man $\begin{eqnarray*} M=M_1\cup M_2\cup M_3\cup M_4\cup M_5 \end{eqnarray*}$ beschreiben, und die Siebformel liefert nach kurzer Überlegung

$\begin{eqnarray*} |M| = \sum_{m=1}^5 ~ (-1)^{m-1} \binom{5}{m} (5-m)^i \end{eqnarray*}$

Jetzt noch zur Bedingung der nichtgelben letzten Kugel: $\begin{eqnarray*} M \end{eqnarray*}$ ist permutationssymmetrisch bzgl. der 5 Farben. Daraus folgt, dass jede der 5 Farben an jeder der $\begin{eqnarray*} i \end{eqnarray*}$ Positionen gleich oft in $\begin{eqnarray*} M \end{eqnarray*}$ vorkommt, speziell ist die letzte Kugel in genau $\begin{eqnarray*} \frac{|M|}{5} \end{eqnarray*}$ Konfigurationen gelb. Somit ist die gesuchte Anzahl gleich

$\begin{eqnarray*} \frac{4}{5}|M| = \frac{4}{5}\left[ 5\cdot 4^i-10\cdot 3^i+10\cdot 2^i-5\cdot 1^i\right] = 4\left[ 4^i-2\cdot 3^i+2\cdot 2^i-1\right] \end{eqnarray*}$

Sorry für die Komplettlösung, aber ab und zu darf das ja mal sein, nicht wahr? smile

13.08.2006, 17:25

JochenX

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent

Zitat:

ohje, ja, natürlich zähle ich da dann die Reihen mit zu wenig Farben mit, ohne, dass sie passen. unglücklich

Zitat:

[,] zum anderen ist die Festlegung von $\begin{eqnarray*} j \end{eqnarray*}$ festen aus den 5 Farben nicht ganz das, was die Aufgabenstellung besagt...

inwiefern habe ich das missgedeutet? Den Einwand verstehe ich jetzt nicht.
Ich denke, wenn ich die "zu wenigfarbenden" noch abziehe (Sieb?), sollte ich (natürlich umständlicher als du Gott

) auch zum Ziel kommen.

Ich würde dann ungefähr so vorgehen (ich mache wieder nur den leichten Teil und sehe für die größeren schon das Siebförmelchen auch durchblitzen):

|A1|=4 (kein Einwand, oder?)
ich zerlege A2 in "mit gelb" (A21) und "ohne gelb" (A22)

Dann wähle ich für $\begin{eqnarray*} A_{21} \end{eqnarray*}$ erst mal eine zweite Kugel aus den 4 verbleibenden; danach gibt es $\begin{eqnarray*} 2^{i-1} \end{eqnarray*}$ Belegungen für die ersten i-1 Plätze, abzüglich einer, nämlich der, die nachher eine einfarbige Reihe gibt, und der letzte Platz ist fest.
Insgesamt $\begin{eqnarray*} |A_{21}|={4 \choose 1}*1*(2^{i-1}-1)=4*(2^{i-1}-1) \end{eqnarray*}$

Für $\begin{eqnarray*} A_{22} \end{eqnarray*}$ wähle ich 2 aus den verbleibenden 4 Farben, es sind von den $\begin{eqnarray*} 2^i \end{eqnarray*}$ 2 Reihen verboten (die einfarbigen), also gilt:
$\begin{eqnarray*} |A_{22}|={4 \choose 2}*(2^i-2) \end{eqnarray*}$

So ab 3 Farben bin ich dann schon zu faul und verweise Bobo lieber auf deine Lösung.
Aber komme ich so wirklich nicht zum Ziel, habe ich da wirklich noch mehr übersehen?

Gruß

edit: A3 ist auch noch überschaubar mit meiner Patzmethode
Ohne Garantie bringe ich noch
$\begin{eqnarray*} |A_{31}|={4 \choose 2}*2*(3^{i-1}-2-2*2^{i-1}) \end{eqnarray*}$ und
$\begin{eqnarray*} |A_{32}|={4 \choose 3}*(3^i-3-{3 \choose 2}*2^i) \end{eqnarray*}$

13.08.2006, 17:35

Auf diesen Beitrag antworten »

Zitat:

Original von LOED

Zitat:

[,] zum anderen ist die Festlegung von $\begin{eqnarray*} j \end{eqnarray*}$ festen aus den 5 Farben nicht ganz das, was die Aufgabenstellung besagt...

inwiefern habe ich das missgedeutet? Den Einwand verstehe ich jetzt nicht.

Nun ja, "wäre dann die Kardinalität von Aj gerade j^i" übersetze ich mit $\begin{eqnarray*} |A_j|=j^i \end{eqnarray*}$ , und das ist ganz einfach falsch, was man z.B. schon für j=1 sieht. In deinem letzten Beitrag steht ja deutlich das richtige $\begin{eqnarray*} |A_1|=4 \end{eqnarray*}$ ...

13.08.2006, 17:44

JochenX

Auf diesen Beitrag antworten »

Ah jetzt habe ich deinen Einwand verstanden, Doppelmist.
Nicht nur, dass ich da welche zu viel berechnet habe, ich habe ganz vergessen, vorher die passenden Farben auszuwählen und mit dem passenden Faktor für diese Möglichkeiten zu multiplizieren.

Schande über mich, ich hoffe, zumindest so, wie es jetzt oben steht, würde es zum Erfolg führen.

PS: Offensichtlich ist "Offensichtliches" nicht immer so offensichtlich, wie es scheint.
Erinnert mich an meinen Übersetzungsfehler "by no means obvious" => "völlig offensichtlich" für meinen letzten Seminarvortrag.
Manchmal ist der Wunsch halt Vater des Gedankens, wenn es um Offensichtlichkeit geht.

Danke!

(Offtopic @Ben als Antwort auf den nächsten Betrag: wurde bei der Vorbesprechung mit dem Prof gemerkt, er fands dann auch lustig und hat an den entsprechenden Stellen noch mal richtig schön auf Details rumgeritten während des Vortrags!)

13.08.2006, 17:57

Ben Sisko

Auf diesen Beitrag antworten »

Zitat:

Original von LOED
Erinnert mich an meinen Übersetzungsfehler "by no means obvious" => "völlig offensichtlich" für meinen letzten Seminarvortrag.

Hast das vorher noch gemerkt oder wurde es im Vortrag bemerkt?

13.08.2006, 19:34

Bobo

Auf diesen Beitrag antworten »

Wäre jemand so frei mir die Siebformel zu erklären (ich hab so weit versucht zu kommen wie ich es mit Wikipedia ging). Und wie man von der Siebformel auf Arthurs Formel kommt.

13.08.2006, 20:13

Auf diesen Beitrag antworten »

Die Siebformel ermöglicht die Berechnung der Mächtigkeit einer Mengenvereinigung, falls die Mächtigkeiten aller möglichen Mengendurchschnitte verfügbar sind. Sprachlich formuliert summiert man dazu alle Mächtigkeiten der beteiligten Ausgangsmengen, subtrahiert davon dann die Mächtigkeiten aller Zweierdurchschnitte, addiert dann wiederum die Mächtigkeiten aller Dreierdurchschnitte, subtrahiert ... usw.

Die Formel für allgemeine Mengenanzahl gebe ich nicht nochmal an, ist ja der reinste Indexkrieg und steht sowieso in der Wikipedia. Für 5 Mengen mache ich mir aber mal die Mühe, das sieht dann ausführlich so aus:

$\begin{eqnarray*} |M_1\cup M_2\cup M_3\cup M_4\cup M_5| &=& (|M_1| + |M_2| + |M_3| + |M_4| + |M_5|)\\ & & - (|M_1\cap M_2| + |M_1\cap M_3| + |M_1\cap M_4| + |M_1\cap M_5| + |M_2\cap M_3| + |M_2\cap M_4| + |M_2\cap M_5| + |M_3\cap M_4| + |M_3\cap M_5| + |M_4\cap M_5|)\\ & & + (|M_1\cap M_2\cap M_3| + |M_1\cap M_2\cap M_4| + |M_1\cap M_2\cap M_5| + |M_1\cap M_3\cap M_4| + |M_1\cap M_3\cap M_5|\\ & & + |M_1\cap M_4\cap M_5| + |M_2\cap M_3\cap M_4| + |M_2\cap M_3\cap M_5| + |M_2\cap M_4\cap M_5| + |M_3\cap M_4\cap M_5|)\\ & & - (|M_1\cap M_2\cap M_3\cap M_4| + |M_1\cap M_2\cap M_3\cap M_5| + |M_1\cap M_2\cap M_4\cap M_5| + |M_1\cap M_3\cap M_4\cap M_5| + |M_2\cap M_3\cap M_4\cap M_5|)\\ & & + |M_1\cap M_2\cap M_3\cap M_4\cap M_5| \end{eqnarray*}$

Ziemlich grauenhaft, nicht? Zum Glück ergeben sich sehr oft einfache Berechnungen für diese Durchschnittsmächtigkeiten - so wie hier:

Was bedeutet es, wenn man $\begin{eqnarray*} m \end{eqnarray*}$ verschiedene unserer $\begin{eqnarray*} M_k \end{eqnarray*}$ hier schneidet? Nun, dann dürfen die zugehörigen $\begin{eqnarray*} m \end{eqnarray*}$ Farben sämtlich nicht mehr zur Färbung der $\begin{eqnarray*} i \end{eqnarray*}$ Kugeln verwendet werden, es verbleiben somit nur $\begin{eqnarray*} (5-m) \end{eqnarray*}$ Farben zur Färbung der $\begin{eqnarray*} i \end{eqnarray*}$ Kugeln. Also ist

$\begin{eqnarray*} \left| M_{k_1}\cap M_{k_2}\cap \ldots \cap M_{k_m} \right| = (5-m)^i\qquad (*) \end{eqnarray*}$

für alle mögliche Auswahlen von $\begin{eqnarray*} m \end{eqnarray*}$ verschiedenen Farben aus 5 Farben. Wieviel solche Auswahlen, und damit auch Durchschnitte von $\begin{eqnarray*} m \end{eqnarray*}$ Mengen gibt es nun? Nun, die Kombinatorik sagt: Genau $\begin{eqnarray*} \binom{5}{m} \end{eqnarray*}$ .

Den ganzen Schmus also in die Siebformel eingesetzt ergibt die Formel von mir oben.

P.S.: Die Einfachkeit der Berechnung der Durchschnittsmächtigkeit gemäß Formel (*) zeigt nochmal deutlich, warum hier gerade die Siebformel zum Einsatz kommen kann.

Neue Frage »

Antworten »

Vertauschungsproblem bei Kombinatorikaufgabe

Verwandte Themen