5796-Aufgabe
2003-02-09 19:31
Faleiro
So. Vorhin im Tutorium bekam ich die Loesung nicht mehr zusammen, aber jetzt habe ich sie wieder:
Gefragt war nach der Anzahl der moeglichen surjektiven Abbildungen von einer achtelementigen Menge auf eine dreielementige. Der Einfachheit halber seien die Elemente 1,2,3 etc.
Man kann eine solche Abbildung durch ein 8-Tupel darstellen, z.B. (3,3,1,2,3,2,1,1). Das soll bedeuten: Die 1 aus der ersten Menge wird auf die 3 in der zweiten Menge abgebildet, die 2 auch auf die 3, etc.
Wie viele Abbildungen kann es, Surjektivitaet mal aussen vor, ueberhaupt geben? Wir waehlen achtmal aus den dreien aus, also 3*3*3*3*3*3*3*3 = 3^8.
Da sind aber auch surjektive drin, die muessen wir jetzt abziehen: Surjektiv sind alle die, wo im Tupel entweder ein Element "fehlt" oder wo im Tupel zwei Element fehlen. (Alle drei koennen ja nicht fehlen, irgendwohin muss die Abbildung ja zeigen, sonst widerspricht es der Definition einer Abbildung…)
Beispiel: (2,2,3,3,3,2,3,3) – hier bildet nichts auf die 1 ab, daher nicht surjektiv.
Wieviele solcher Tupel koennen wir bilden? Ganz einfach: 2^8 fuer jedes fehlende Element, d.h. 2^8, wo die 1 fehlt, 2^8, wo die 2 fehlt und auch 2^8, wo die 3 fehlt. Die alle sind schon mal mit Sicherheit nicht surjektiv.
Nun muessen wir noch die abziehen, in denen sogar auf *zwei* Elemente nicht abgebildet wird:
(1,1,1,1,1,1,1,1), (2,2,2,2,2,2,2,2), (3,3,3,3,3,3,3,3) sind lustigerweise die einzigen solchen. Irgendwie logisch. Nun stellen wir aber mit Schrecken fest, dass wir z.B. (1,1,1,1,1,1,1,1) nicht nur bereits abgezogen haben, sondern sogar schon *zweimal* abgezogen haben! Denn (1,1,1,1,1,1,1,1) liegt sowohl in der Menge derer, in denen keine 2 vorkommt, als auch in der Menge derer, in denen keine 3 vorkommt.
Da wir sie also unfairerweise schon doppelt von der gesamt-Tupel-Menge 3^8 abgezogen haben, addieren wir einfach 3.
Insgesamt haben wir also 3^8 - (3 * 2^8) + 3 = 5796. :-)
Ich hoffe, das war verstaendlich. TriPhoenix, danke, dass du dir die Zeit genommen hast heute nachmittag. Mir zumindest hat es viel gebracht.
Gefragt war nach der Anzahl der moeglichen surjektiven Abbildungen von einer achtelementigen Menge auf eine dreielementige. Der Einfachheit halber seien die Elemente 1,2,3 etc.
Man kann eine solche Abbildung durch ein 8-Tupel darstellen, z.B. (3,3,1,2,3,2,1,1). Das soll bedeuten: Die 1 aus der ersten Menge wird auf die 3 in der zweiten Menge abgebildet, die 2 auch auf die 3, etc.
Wie viele Abbildungen kann es, Surjektivitaet mal aussen vor, ueberhaupt geben? Wir waehlen achtmal aus den dreien aus, also 3*3*3*3*3*3*3*3 = 3^8.
Da sind aber auch surjektive drin, die muessen wir jetzt abziehen: Surjektiv sind alle die, wo im Tupel entweder ein Element "fehlt" oder wo im Tupel zwei Element fehlen. (Alle drei koennen ja nicht fehlen, irgendwohin muss die Abbildung ja zeigen, sonst widerspricht es der Definition einer Abbildung…)
Beispiel: (2,2,3,3,3,2,3,3) – hier bildet nichts auf die 1 ab, daher nicht surjektiv.
Wieviele solcher Tupel koennen wir bilden? Ganz einfach: 2^8 fuer jedes fehlende Element, d.h. 2^8, wo die 1 fehlt, 2^8, wo die 2 fehlt und auch 2^8, wo die 3 fehlt. Die alle sind schon mal mit Sicherheit nicht surjektiv.
Nun muessen wir noch die abziehen, in denen sogar auf *zwei* Elemente nicht abgebildet wird:
(1,1,1,1,1,1,1,1), (2,2,2,2,2,2,2,2), (3,3,3,3,3,3,3,3) sind lustigerweise die einzigen solchen. Irgendwie logisch. Nun stellen wir aber mit Schrecken fest, dass wir z.B. (1,1,1,1,1,1,1,1) nicht nur bereits abgezogen haben, sondern sogar schon *zweimal* abgezogen haben! Denn (1,1,1,1,1,1,1,1) liegt sowohl in der Menge derer, in denen keine 2 vorkommt, als auch in der Menge derer, in denen keine 3 vorkommt.
Da wir sie also unfairerweise schon doppelt von der gesamt-Tupel-Menge 3^8 abgezogen haben, addieren wir einfach 3.
Insgesamt haben wir also 3^8 - (3 * 2^8) + 3 = 5796. :-)
Ich hoffe, das war verstaendlich. TriPhoenix, danke, dass du dir die Zeit genommen hast heute nachmittag. Mir zumindest hat es viel gebracht.