matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenRelationenAnzahl bestimmter Relationen
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Deutsch • Englisch • Französisch • Latein • Spanisch • Russisch • Griechisch
Forum "Relationen" - Anzahl bestimmter Relationen
Anzahl bestimmter Relationen < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Relationen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Anzahl bestimmter Relationen: Korrektur
Status: (Frage) beantwortet Status 
Datum: 10:10 Fr 26.10.2012
Autor: HoagsObject

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.

        
Bezug
Anzahl bestimmter Relationen: Antwort
Status: (Antwort) fertig Status 
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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Relationen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]