Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Anzahl der Äquivalenzrelationen

Anzahl der Äquivalenzrelationen

Universität / Fachhochschule

Relationen

Tags: Relation.

mueschbrot aktiv_icon

12:00 Uhr, 16.04.2016

Hallo! :-)

Momentan beschäftigen wir uns mit Relationen im Studium. Dabei haben wir eine Aufgabe, die lautet:

Sei An eine Menge mit

n

Elementen. Untersuchen Sie für

n = 6,

wie viele verschiedene Äquivalenzrelationen es auf der Menge An gibt.

So, dabei habe ich mir nun gedacht, dass ich mir die ganzen Möglichkeiten aufschreibe:

Für:

6 + 0 \to 1

ÄR

1 + 1 + 1 + 1 + 1 + 1 \to 1

ÄR

2 + 4 \to 15

ÄR

1 + 1 + 4 \to 15

ÄR

3 + 3 \to 10

ÄR

3 + 2 + 1 \to 60

ÄR (?)

5 + 1 \to 6

ÄR

4 + 1 + 1 \to 15

ÄR

2 + 2 + 2 \to 28

ÄR

2 + 1 + 1 + 1 + 1 \to 15

ÄR

3 + 1 + 1 + 1 \to 10

ÄR

2 + 2 + 1 + 1 \to 28

ÄR

= 196

ÄR

Ist das richtig? Gibt es noch einen leichteren Weg um auf die gesamten ÄR zu kommen?

Danke euch schon im Voraus! :-)

Shipwater aktiv_icon

12:09 Uhr, 16.04.2016

Schau mal hier: mathworld.wolfram.com/BellNumber.html
Die richtige Antwort lautet also

203

. Du wirst dich irgendwo vertan haben, kontrolliere nochmal.

mueschbrot aktiv_icon

12:23 Uhr, 16.04.2016

Danke für die Seite, aber ich sehe da tatsächlich gar nicht durch

\circ . \circ

Shipwater aktiv_icon

12:29 Uhr, 16.04.2016

Der Seite kann man

B_{6} = 203

entnehmen, mehr brauchst du davon nicht zu wissen. Deswegen musst du dich irgendwo vertan haben. Kontrolliere also nochmal. Deine Idee, die Anzahl der möglichen Partitionen zu bestimmen, ist schon die Richtige.
Zur Kontrolle ist auch das hilfreich: de.wikipedia.org/wiki/Stirling-Zahl#Stirling-Zahlen_zweiter_Art
Es ist also

S_{6,1} = 1, S_{6,2} = 31, S_{6,3} = 90, S_{6,4} = 65, S_{6,5} = 15

und

S_{6,6} = 1

wobei

S_{n, k}

die Anzahl der k-elementigen Partitionen einer n-elementigen Menge ist. Alle aufaddiert kommt man wieder auf

203

mueschbrot aktiv_icon

12:40 Uhr, 16.04.2016

Achso! :-D) Okay! Dann muss ich nochmal schauen, wo mir die letzten 7 fehlen

x . x

Ich danke dir für die Antwort & die Hilfe! :-)

Shipwater aktiv_icon

12:42 Uhr, 16.04.2016

Addiert man deine Möglichkeiten auf, kommt man übrigens auf

204

und nicht auf

196

. Du hast also eine zu viel drinnen.
Aus deiner Lösung liest man übrigens ab:

S_{6,1} = 1

(stimmt)

S_{6,2} = 15 + 10 + 6 = 31

(stimmt)

S_{6,3} = 15 + 60 + 15 + 28 = 118

(viel zu viel)

S_{6,4} = 10 + 28 = 38

(viel zu wenig)

S_{6,5} = 15

(stimmt)

S_{6,6} = 1

(stimmt)
Du hast dich also wohl bei den

3 -

und 4-elementigen Partitionen verhaspelt.
In deiner Notation sollte sich zum Beispiel korrekterweise ergeben:

3 + 1 + 1 + 1 \to (\begin{matrix} 6 \\ 3 \end{matrix}) = 20

ÄR

2 + 2 + 1 + 1 \to \frac{(\begin{matrix} 6 \\ 2 \end{matrix}) \cdot (\begin{matrix} 4 \\ 2 \end{matrix})}{2} = 45

ÄR
Und damit

S_{6,4} = 20 + 45 = 65

.
Deine Aufgabe ist es nun

S_{6,3}

zu korrigieren, dann stimmt alles.
Übrigens hast du einmal

1 + 1 + 4

und einmal

4 + 1 + 1,

das fällt natürlich zusammen. Und du solltest

2 + 2 + 2

nochmal überdenken, wie kommst du da auf

28

mueschbrot aktiv_icon

15:26 Uhr, 16.04.2016

Mir fällt gerade auf, dass ich

4 + 1 + 1

doppelt habe. Somit habe ich

189

ÄR zusammen und komme bei dem Part mit den 3 Elementen auf

103

d . h

. mir fehlt etwas bei

2 + 2 + 1 + 1

Ich kann das mit der Kombinatorik nicht... mir fehlt das Verständnis dafür. Habs oft versucht... aber es funktioniert bei komplexeren Dingen nicht. Deswegen habe ich alles ordentlich aufgeschrieben und dabei muss ich wohl bestimmte Dinge vergessen haben

\frac{:}{}

Shipwater aktiv_icon

16:55 Uhr, 16.04.2016

Hast du dir meinen letzten Beitrag überhaupt durchgelesen? Da hab ich doch schon so gut wie alles korrigiert. Nur

2 + 2 + 2

musst du dir nochmal überlegen. Also

1 + 1 + 4 \to (\begin{matrix} 6 \\ 4 \end{matrix}) = 15

ÄR stimmt und

3 + 2 + 1 \to (\begin{matrix} 6 \\ 3 \end{matrix}) \cdot (\begin{matrix} 3 \\ 2 \end{matrix}) = 60

ÄR auch. Nur

2 + 2 + 2 \to 28

ÄR ist falsch. Laut Formel sollst du insgesamt auf

S_{6,3} = 90

kommen, also bleiben dir

90 - 15 - 60 = 15

für

2 + 2 + 2

übrig. Und das kann man sich kombinatorisch auch leicht überlegen:

S_{6,3} = \frac{(\begin{matrix} 6 \\ 2 \end{matrix}) \cdot (\begin{matrix} 4 \\ 2 \end{matrix})}{3!} = 15

mueschbrot aktiv_icon

23:31 Uhr, 16.04.2016

Ja, das hatte ich gelesen - du hattest deinen Beitrag jedoch zeitgleich korrigiert, deswegen passte meine Antwort dann nicht mehr. :-)

Ich danke, dir für die Problemlösung, ich werde mich da morgen früh mal ordentlich einleben und gucken, ob ich das auf die Reihe bekomme. :-)

Vielen Danke, für deine großartige Hilfe!

Shipwater aktiv_icon

10:39 Uhr, 17.04.2016

Ich war nur verwundert, weil dein Beitrag erst 3 Stunden nach meinem abgeschickt wurde. Keine Ursache und viel Erfolg weiterhin!

mueschbrot aktiv_icon

11:56 Uhr, 17.04.2016

Jaaa, das lag daran, dass ich das Fenster für die Antwort die ganze Zeit geöffnet hatte und nebenbei die Matheaufgaben gemacht habe

:' D

Ich habe nun in meiner Tabelle auf die Fehler gefunden und da hat sich noch eine Frage bei mir aufgetan.

Zum einen gibt es ja die Möglichkeit für

3 + 3

dort rechnet man ja

(\begin{matrix} 6 \\ 3 \end{matrix}) = \frac{20}{2} = 10

. Das ist noch logisch, denn die Sachen doppeln sich ja sonst.
Jedoch bei

3 + 1 + 1 + 1

macht man das nicht. Jedoch doppeln sich die Elemente hier doch auch oder nicht?

Shipwater aktiv_icon

13:52 Uhr, 17.04.2016

Nein, denn bei

3 + 1 + 1 + 1

hast du ja nur eine Teilmenge mit 3 Elementen und die anderen sind alle einelementig. Schreibe notfalls alle Möglichkeiten aus, dann wirst du es sehen. Der Witz ist einfach, dass

{{1,2,3}, {4,5,6}}

und

{{4,5,6}, {1,2,3}}

die selbe Partition sind, aber

{{1,2,3}, {4}, {5}, {6}}

und

{{1}, {2}, {3}, {4,5,6}}

eben unterschiedliche Partitionen sind.

mueschbrot aktiv_icon

22:23 Uhr, 18.04.2016

Achja! Stimmt! Daran habe ich absolut nicht gedacht! Ich danke dir nochmals!

Shipwater aktiv_icon

21:22 Uhr, 19.04.2016

Keine Ursache.

1302284

1301419

	Status: nicht eingeloggt	Noch nicht registriert?