Anzahl surjektiver Abb < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:25 Mi 06.02.2013 | | Autor: | Coup |
| Aufgabe | Sei X: { 1,2,3,4 } , Y : { a,b,c}
wie viele surjektive und Injektive Abbildungen von X->Y gibt es ? |
Hallo,
Injektive Abbildungen gibt es keine da meine Menge X zu groß ist und ich nur auf höchstens ein y aus Y abbilden darf.
Aber surjektiv sind eine ganze Menge Abbildungen oder nicht ?
z.b
f(1)=a
f(2)=b
f(3)=c
f(4)=c
Ist eine surjektive Abbildung
ODER
f(1)=a
f(2)=a
f(3)=a
f(4)=a
Wie kann ich das kombinatorisch so zusammenfassen das ich ein Ergebnis der Möglichkeiten bekomme ohne alles durchzuprobieren ?
lg
Micha
|
|
| |
|
Hallo Micha,
die Aufgabe scheint Deutungsspielraum zu haben, aber ich bezweifle, dass es einen solchen gibt.
> Sei X: { 1,2,3,4 } , Y : { a,b,c}
>
> wie viele surjektive und Injektive Abbildungen von X->Y
> gibt es ?
>
> Injektive Abbildungen gibt es keine da meine Menge X zu
> groß ist und ich nur auf höchstens ein y aus Y abbilden
> darf.
Aha. Du gehst also davon aus, dass es eine Abbildungsvorschrift für jedes Element von X geben muss.
Das sehe ich auch so.
Und dann hast Du Recht.
> Aber surjektiv sind eine ganze Menge Abbildungen oder nicht
> ?
>
> z.b
> f(1)=a
> f(2)=b
> f(3)=c
> f(4)=c
> Ist eine surjektive Abbildung
Ja, wohl wahr.
> ODER
> f(1)=a
> f(2)=a
> f(3)=a
> f(4)=a
Hm, nein. Hier stellt sich die Frage, ob die Abbildungsvorschrift auch jedes Element von Y berücksichtigen muss oder nicht.
> Wie kann ich das kombinatorisch so zusammenfassen das ich
> ein Ergebnis der Möglichkeiten bekomme ohne alles
> durchzuprobieren ?
Wenn nicht jedes Element von Y "getroffen" werden muss, ist das einfach. Sei $x=|X|$ und $y=|Y|$, hier also x=4, y=3.
Dann ist die Zahl z der surjektiven Abbildungen einfach [mm] z=y^x. [/mm] Jedes der x Elemente von X kann auf irgendeines der y Elemente von Y abgebildet werden.
Meines Erachtens gesucht sind aber eben nur die Abbildungen, die auch ganz Y "verwenden".
Dann ist die Rechnung eine andere:
Ein Element von Y ist Abbildungsziel zweier Elemente von X.
Welches Element von Y? --> y Möglichkeiten.
Welche Elemente von X? --> [mm] \vektor{x\\2} [/mm] Möglichkeiten.
Dann bleiben im speziellen Fall noch je 2 Elemente von X bzw. von Y, die einander eineindeutig (also bijektiv) zugeordnet werden müssen. Dafür gibt es 2 Möglichkeiten.
Insgesamt sind es dann also [mm] z=3*\vektor{4\\2}*2=36 [/mm] mögliche Abbildungen.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:48 So 10.02.2013 | | Autor: | Coup |
Danke dir :)
Sei X: { 1,2,3,4 } , Y : { a,b,c}
Wie viele inj. wären es denn für Y->X injektiv ?
bzw. Sind das Unterschiedliche Abbildungen in meinem Beispiel ?
f(a) = 1
f(b) = 2
f(c) = 3
f(a) = 3
f(b) = 2
f(c) = 1
Wie könnte ich die Anzahl injektiver kombinatorisch berechnen ?
vielen Danke :)
Micha
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:52 So 10.02.2013 | | Autor: | fred97 |
> Danke dir :)
> Sei X: { 1,2,3,4 } , Y : { a,b,c}
> Wie viele inj. wären es denn für Y->X injektiv ?
>
> bzw. Sind das Unterschiedliche Abbildungen in meinem
> Beispiel ?
> f(a) = 1
> f(b) = 2
> f(c) = 3
>
> f(a) = 3
> f(b) = 2
> f(c) = 1
>
> Wie könnte ich die Anzahl injektiver kombinatorisch
> berechnen ?
Wieviele Permutationen von 1,2,3 gibt es ?
FRED
>
> vielen Danke :)
>
> Micha
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:12 So 10.02.2013 | | Autor: | kaju35 |
Hallo Fred
müsste nicht auch noch berücksichtigt werden,
dass Du drei von vier Zahlen auswählst? In anderen
Worten, dass Du [mm] $\binom{4}{3}=4$ [/mm] heranmultiplizierst?
Insgesamt ergibt das eine Anzahl von 24
injektiven Abbildungen.
Gruß
Kai
|
|
|
|
