Kombinatorik: Anzahl Partitionen mit gewisser Elementgröße

05.01.2013, 14:17

Michael2

Kombinatorik: Anzahl Partitionen mit gewisser Elementgröße

Meine Frage:
Guten Tag, ich es geht um folgende Aufgabe, die mir Kopfzerbrechen bereitet:
Wieviele Äquivalenzrelationen R gibt es auf einer 7-elementigen Menge, so dass R genau drei Äquivalenzklassen von der Mächtigkeit 2, 2 und 3 hat?

Meine Ideen:
Mein Ansatz lautet:
Nach meinem Verständnis ist hier nach einer Teilmenge der Äquivalenzrelationen gefragt, die die Menge in genau drei Teile partitioniert und die Gesamtanzahl an Äquivalenzrelationen, die dieser Bedingung genügt ist $\begin{eqnarray*} S_{7,3} \end{eqnarray*}$ . Davon muss ich jetzt die Anzahl an Äquivalenzrelationen abziehen, die die Menge Partitionen mit genau drei Elementen unterteilt, deren Elementgröße (der Partition) dann nicht der Aufteilung 2,2,3 entspricht, bspw. gibt es ja eine Äquivalenzrelation die die Menge in Elemente der Größe 3,3,1 partitioniert. Mein Gedanke: die Anzahl an Äquivalenzrelationen von $\begin{eqnarray*} S_{7,3} \end{eqnarray*}$ abziehen, die die Menge in Partitionen mit 3 Elementen unterteilt aber deren Größe der Äquivalenzklassen nicht dem Schema 2,2,3 (Reihenfolge ja egal) entspricht.
Um bspw. zu zählen, wie viele Partitionen es gibt, die 7 in Äquivalenzklassen von der Größe 4, 2, 1 zerlegt würde ich wie folgt vorgehen: $\begin{eqnarray*} \frac{7!}{4!*(7-4)!} + \frac{7!}{2!*(7-2)!} +\frac{7!}{1!*(7-1)!} \end{eqnarray*}$ also zählen, wie viele Möglichkeiten es gibt, 7 entsprechend aufzuteilen. Ist meine Idee richtig? Ich bin mir recht unsicher, vor allem was meinen letzten Gedankengang betrifft. Vielen Dank für hilfreiche Hinweise im voraus!
Mit freundlichen Grüßen
Michael

05.01.2013, 16:08

Michael2

Auf diesen Beitrag antworten »

RE: Kombinatorik: Anzahl Partitionen mit gewisser Elementgröße
Ah sorry, was ich natürlich haben wollte war folgendes:
Ich kann ja erstmal 4 Elemente auswählen aus 7, die dann in das Partitionselement mit Betrag 4 stecken, dann 2 Elemente aus 3 auswählen und die dann ins Partitionselement mit Größe 2 stecken und dann das letzte ins letzte, bis jetzt leere Partitionselement stecken, heißt:
$\begin{eqnarray*} \frac{7!}{4!*3!}*\frac{3!}{2!*1!}*1 \end{eqnarray*}$

05.01.2013, 19:41

Michael2

Auf diesen Beitrag antworten »

RE: Kombinatorik: Anzahl Partitionen mit gewisser Elementgröße
Bitte um Kommentare bzgl. meiner Gedanken! :-)

05.01.2013, 20:06

Mystic

Auf diesen Beitrag antworten »

RE: Kombinatorik: Anzahl Partitionen mit gewisser Elementgröße
Ich kapier nicht, warum du nicht gleich die ursprüngliche Aufgabe so löst, wie im 2.Ansatz, nämlich du wählst 3 Elemente von 7 für die erste Klasse und dann 2 Elemente von den restlichen 4 für die 2.Klasse, womit sich dann automatisch und ohne weiteres Zutun die restlichen 2 Elemente der 3.Klasse ergeben, was also dann

$\begin{eqnarray*} \frac 12 \binom 73 \binom 42 \end{eqnarray*}$

Möglichkeiten ergibt (der Faktor 1/2 ergibt sich daraus, dass eine Vertauschung der 2. und 3.Klasse ja nichts Neues liefert)...

07.01.2013, 23:00

Michael2

Auf diesen Beitrag antworten »

RE: Kombinatorik: Anzahl Partitionen mit gewisser Elementgröße
Ja das war dumm von mir, Kombinatorik muss ich noch viel üben! :-) Aber danke und sorry dass ich jetzt erst antworte bin aber momentan viel im Streß mit Vorklausuren etc. :-/

14.02.2013, 13:15

rainer_zufall

Auf diesen Beitrag antworten »

Warum funktioniert das nicht, wenn ich erst (2 über 7) * (2 über 5) * (3 über 3) rechne und dann durch 2 teile?
Da muss man ja anscheinend durch 3! = 6 teilen

14.02.2013, 14:58

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von rainer_zufall
Warum funktioniert das nicht, wenn ich erst (2 über 7) * (2 über 5) * (3 über 3) rechne und dann durch 2 teile?
Da muss man ja anscheinend durch 3! = 6 teilen

Warum durch 3! teilen? Welche 6 Möglichkeiten sind denn da immer gleichwertig? Nein, man muss auch hier zum Schluss durch 2 teilen...

P.S.: Dass du konsequent (n über k) mit (k über n) verwechselst, sei dabei hier nur am Rande erwähnt...

14.02.2013, 14:59

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von rainer_zufall
Warum funktioniert das nicht, wenn ich erst (2 über 7) * (2 über 5) * (3 über 3) rechne und dann durch 2 teile?

So kann's ja gar nicht funktionieren, denn dieser Wert ist gleich Null. Vermutlich meinst du aber

Zitat:

wenn ich erst (7 über 2) * (5 über 2) * (3 über 3) rechne und dann durch 2 teile?

in Formel ausgedrückt $\begin{eqnarray*} \frac{1}{2} \binom{7}{2}\cdot \binom{5}{2}\cdot \binom{3}{3} \end{eqnarray*}$ , so geht's tatsächlich auch. Beide Wege führen zu

$\begin{eqnarray*} \frac{7!}{2\cdot 2!2!3!} \end{eqnarray*}$ .

14.02.2013, 15:32

rainer_zufall

Auf diesen Beitrag antworten »

jepp, das hab ich wohl tatsächlich verwechselt Augenzwinkern

war wohl zu tief in Gedanken