Anzahl bestimmter Relationen < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Gegeben sei die Menge [mm] G_{3} [/mm] = {0,1,2}.
a) Geben Sie graphisch eine Relation R [mm] \subseteq G_{3} \times G_{3} [/mm] an, die linkstotal und rechtseindeutig, aber nicht rechtstotal und nicht linkseindeutig ist.
b) Geben Sie in Mengenschreibweise eine andere Relation [mm] R_{2} \subseteq G_{3} \times G_{3} [/mm] an, die linkstotal und rechtseindeutig, aber nicht rechtstotal und nicht linkseindeutig ist.
c) Wie viele solcher Relationen R gibt es?
d) Wie viele bijektive Abbildungen von [mm] G_{3} [/mm] nach [mm] G_{3} [/mm] gibt es. |
Hallo zusammen!
Ich fühle mich ja fast schon schlecht, dass ich hier jetzt so viel poste, aber ich hätte echt nicht gedacht, dass es tatsächlich ein Forum gibt, in dem man so kompetent Tipps und Hilfe zu Aufgaben bekommt... ich bin begeistert!
Zur Aufgabe:
a) und b) sind ja erstmal kein Problem, die waren relativ leicht gelöst. Mit d) hatte ich auch nicht wirklich ein Problem, da habe ich einfach 3! = 6 ausgerechnet.
Mein Problem liegt nun bei c).
Ich habe über diese Aufgabe zwei Mal ausführlich nachgedacht und bin zwei Mal auf ein anderes Ergebnis gekommen. :D
Die erste Überlegung war:
Es gibt 3 Möglk. je ein Element aus [mm] G_{3rechts} [/mm] freizulassen (wegen der nicht erfüllten Rechtstotalität)
Es gibt 3 Möglk. ein Element aus [mm] G_{3rechts} [/mm] mit zwei Pfeilen zu versehen (wegen der nicht erfüllten Linkseindeutigkeit)
Es gibt 6 Möglk. die Pfeile in [mm] G_{3rechts} [/mm] anzuordnen.
3*3*6 = 54 Möglk einer solchen Relation R
Das kam mir dann komisch vor und ich hab nochmal drüber nachgedacht:
3 Möglk. in [mm] G_{3rechts} [/mm] ein Element freizulassen
3 Möglk. in [mm] G_{3rechts} [/mm] zwei Elemente freizulassen
9 Möglk. zwei Elemente aus [mm] G_{3links} [/mm] mir einem Element aus [mm] G_{3rechts} [/mm] zu verbinden
9 Möglk. ein Element aus [mm] G_{3links} [/mm] mit einem Element aus [mm] G_{3rechts} [/mm] zu verbinden
3*3*9*9 = 729
Das kam mir dann erst plausibel vor, auch wenn ich die Zahl etwas groß fand.
Aber dann hat ein Kommilitone mir gesgat, dass er 21 raus hat und dass das auf jeden Fall richtig sei, wie er drauf gekommen ist hat er mir aber nicht verraten wollen. -_- Das hat mich dann doch sehr verunsichert, da 21 keinem meiner Ergebnisse auch nur ein bisschen ähnlich ist.
Sind meine beiden Überlegungen nun also komplett falsch oder fehlt was oder hab ich was zu viel...?
Über Hilfe würde ich mich sehr freuen.
Grüße,
HoagsObject
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:43 Fr 26.10.2012 | | Autor: | tobit09 |
Hallo HoagsObject,
soviel vorweg: Dein Komilitone hat Recht.
Es gibt nur [mm] $3^3=27$ [/mm] linkstotale und rechtseindeutige Relationen [mm] $R\subseteq G_3\times G_3$, [/mm] so dass die gesuchte Anzahl auf jeden Fall [mm] $\le27$ [/mm] sein muss.
Kombinatorik (Lehre vom Abzählen) ist oft sehr knibbelig und man vertut sich leicht.
> Die erste Überlegung war:
>
> Es gibt 3 Möglk. je ein Element aus [mm]G_{3rechts}[/mm]
> freizulassen (wegen der nicht erfüllten Rechtstotalität)
Schon diese drei Möglichkeiten sind nicht zwangsläufig voneinander verschieden. Man könnte ja auch zwei Elemente freilassen.
Wir könnten jedoch zunächst nur die Fälle, in denen genau ein Element freigelassen wird, betrachten und hinterher die Anzahl der Fälle, in denen zwei Elemente freigelassen werden, hinzuaddieren. Davon gehe ich im Folgenden aus.
Nennen wir das freigelassene Element auf der rechten Seite x.
> Es gibt 3 Möglk. ein Element aus [mm]G_{3rechts}[/mm] mit zwei
> Pfeilen zu versehen (wegen der nicht erfüllten
> Linkseindeutigkeit)
Wenn du schon festgelegt hast, dass x freigelassen wird, bleiben nur noch 2 Elemente auf der rechten Seite übrig, die wir mit zwei Pfeilen versehen können.
Nennen wir das Element, das mit zwei Pfeilen versehen werden soll y.
Bleibt ein eindeutig bestimmtes Element z auf der rechten Seite, das genau einen Pfeil erhalten muss.
> Es gibt 6 Möglk. die Pfeile in [mm]G_{3rechts}[/mm] anzuordnen.
Nachdem x, y und z festgelegt sind, gibt es nur noch 3 Möglichkeiten, die Pfeile anzuordnen: Es kann nur gewählt werden, von welchem Element auf der linken Seite der Pfeil zu z ausgeht. Die anderen beiden Elemente auf der linken Seite müssen dann zu y gehen.
Macht insgesamt 3*2*3=18 Möglichkeiten, genau ein Element auf der rechten Seite freizulassen.
Zusätzlich gibt es 3 Möglichkeiten, genau zwei Elemente auf der rechten Seite freizulassen, also alle Elemente auf der linken Seite mit dem gleichen Element a auf der rechten Seite zu verbinden: Man hat nur die Wahl des Elements a, wofür es 3 Möglichkeiten gibt.
Insgesamt erhalten wir so 18+3=21 mögliche Wahlen von R.
Das was ich geschrieben habe, ist übrigens weit entfernt von einem präzisen Beweis. Es ist nur ein "Plausibel-Machen". Eine Umsetzung zu einem präzisen Beweis würde sicherlich länger dauern, als einfach alle 27 linkstotalen und rechtseindeutigen Relationen aufzulisten, dann die rechtstotalen bzw. linkseindeutigen zu streichen und die übrig-gebliebenen zu zählen.
Viele Grüße
Tobias
|
|
|
|
