fb18.de
/ Diplom Informatik
/ Unterbereich Grundstudium
/ Mathe
M1 Syntax
Gegeben folgende Aufgabe:
Menge A hat 7 Elemente, Menge C hat 6 Elemente.
Gesucht: Abbildung von A nach C mit |f(A)| = 3
Kann ich in der Klausur einfach folgendes schreiben:
S(7,3) * (6 ueber 3) = 301 * 20 = 6020 ?
Wird das so akzeptiert oder muss ich das irgendwie erläutern etc?
Ich würde zumindest noch dranschreiben, woher S(7,3) und (6 über 3) eigentlich kommen
wie woher? was das eigentlich heißt oder wie?
Das heißt ich schreibe:
Man teilt die Menge A in 3 Klassen auf und sucht sich aus der Menge B immer 3 Elemente.
Somit erhält man:
S(7,3) * (6 ueber 3) = 301 * 20 = 6020 ?
Wäre das so richtig gelöst in der Klausur?
Hm,
kann da mal jemand Stellung zu beziehen, ob ich mein Ergebnis nicht eigentlich noch mit 3! multiplizieren muss?
Nein musst es nicht mit 3! multiplizieren
warum nicht?
EDIT:
Ich dachte mir das so:
Ich suche aus der Menge C 3 Elemente aus.
Dann gibt es zu jeder dieser Auswahl surjektive Abbildungen von A nach C, daher noch die Fakultät nicht rein, odeR?
Die Anzahl surjektiver Abbildungen von 7 Elementen auf 3 Elemente ist 3! * S(7,3) und das multipliziere ich mit (6 ueber 3) ?
Von surjektiven Abbildungen steht da doch gar nichts
Du willst einfach nur aus 6 Elementen 3 auswählen, deshalb (6 über 3)
und danach guckst du wieviele Möglichkeiten es gibt diese 7 Elemente aus A in 3 Klassen einzuteilen bzw auf 3 Elemente abzubilden
Ja, aber genau das ist doch äquivalent zur surjektiv-Frage..
Ich wähle von den 6 Elementen 3 aus.
Und dann gucke ich wieviele surjektive Abbildungen es gibt, die 7 auf 3 Elemente abbilden (es muessen ja alle 3 getroffen werden)
Edit:
Angenommen ich würde dann nicht surjektiv abbilden, dann hätte ich 3^7 Möglichkeiten von 7 auf 3 Elemente, es muss also surjektiv sein, also auch die 3! dazu, oder?
Gruppenleiter, sagt was dazu ;)
Tri hat es gestern im Tutorium auch mit Fakultät genannt. Wenn man das macht, kommt man jedoch nicht auf die in den GProt's abgedruckten Ergebnisse…
Wer hat nun Recht? Hilfe! ;-)
Ich behaupte natürlich ich habe Recht [img]
http://www.fb18.de/gfx/15.gif[/img]
Das ist so: wir müssen die surjektiven Abbildungen betrachten, ansonsten haben wir eventuell Abbildungen mit drin, die weniger als 3 Elemente Abbilden. Die Zahl der surjektiven Abbildungen der Menge 7 auf 3 sind [img]
http://mokrates.de/cgi-bin/texstring?3!%20%5Ccdot%20S(7%2C3)[/img]. Dann halt noch die Möglichkeiten dazu 3 auszuwählen aus 7 und dann kommen wir auf besagtes
[img]
http://mokrates.de/cgi-bin/texstring?3!%20%5Ccdot%20S(7%2C3)%20%5Ccdot%20%7B7%5Cchoose3%7D[/img]
Und hier der Grund waurm ich glaube dass S(7,3) nicht ausreicht: Dies ginge davon aus dass es reicht einfach die Partitionen zu zählen. Eines wird dabei aber vergessen. Angenommen wir haben der einfachheit halber 3 Elemente (A,B,C) auf 2 (X,Y) abzubilden. Dann würde man sagen, klar wir müssen die 3 Elemente in 2 Teile partitionieren. Also gibt es die Möglichkeiten (A) (B,C), (A,C) (B), (B,C) (A). Also 3 Möglichkeiten. Was hier aber vergessen wird ist dass wir auch noch auswählen müssen, WORAUF das ganze abgebildet wird. Dann gibts nämlcih 6 Surjektionen (jede Zeile steht für eine Surjektion):
| A | B | C
-----+---+---+---
1 | X | Y | Y
2 | Y | X | X
3 | X | Y | X
4 | Y | X | Y
5 | Y | X | X
6 | X | Y | Y
Wir haben nämlich für die Zuordnun der Mengenteile nochmal k! Möglichkeiten. Und damit haben wir dann in unserem Fall 3! Möglichkeiten bei jeder Partition, weil uns nicht nur interessiert, wie wir aufteilen, sondern auch welcher Teil wem zugeordnet wird.
HTH
wie wäre es mit 3^7=2187 Abbildungen?
Nein das wären viel zu viele. Insbesondere wären da Abbildungen bei, die alle 7 Elemente auf dasselbe abbilden, und dann ist |f(A)| = 1. Es müssen ansich schon die surjektiven sein.
Ja, ich denke auch, dass es surjektiv sein muss, wenn man sich das bei kleineren Mengen explizit aufschreibt kommt man mit der Formel ohne Fakultät nicht hin.
ja, ich sehe es ein!
Dann haben wir also |A|=7 , |C|=6 und |f(A)|=3.
Wir können dann mit der folgenden, neuen Fragestellung an die Aufgabe rangehen:
Wieviele surjektive Abbildungen f:A->C (mit |C|=3) gibt es?
Da |A| >= |C| bzw. 7 >= 3 folgt
|C|! S(|A|,|C|) bzw. 3! S(7,3)
So steht die Formel auch im Biggs (neuer Biggs S.129 Theorem 12.3.1).
Das deckt sich jedoch nicht mit Tris Behauptung bzw. Formel [img]
http://www.fb18.de/gfx/8.gif[/img]
Doch, du kannst dir ja die drei Elemente aus den Elementen von C aussuchen, daher musst du das ganze noch mit (6 ueber 3) multiplizieren
Genau, C hat nämlcih 6 Elemente, dann muss man schon fragen:
Wieviele surjektive Abbildungen von A nach C' mit |C'| = 3 gibt es?
Und danach
Wieviele 3-elemntigen Teilmengen C' von C gibts?