Anzahl der eindeutigen Abbildungen

16.10.2005, 11:31

Sunwater

Anzahl der eindeutigen Abbildungen

Hi...

ich habe zwei Mengen M = {1,2,...,m} und N = {1,2,...,n} beide im Bereich der natürlichen Zahlen.

jetzt soll ich folgende Anzahlen angeben:

a) eindeutige Abbildungen f: M -> N
b) eindeutige Abbildungen f: M -> N mit f(1) $\begin{eqnarray*} \leq \end{eqnarray*}$ f(2) $\begin{eqnarray*} \leq \end{eqnarray*}$ ... $\begin{eqnarray*} \leq \end{eqnarray*}$ f(m);
c) und d) das gleiche nur alle eineindeutigen Abbildungen

irgendwie sollen damit die kombinatorischen Grundformeln wiederholt werden?!

16.10.2005, 23:59

irre.flexiv

Auf diesen Beitrag antworten »

a)
Nimm dir ein $\begin{eqnarray*} a \in M \end{eqnarray*}$ . Wieviel Möglichkeiten gibt es dieses a auf ein $\begin{eqnarray*} b \in N \end{eqnarray*}$ abzubilden? Genau n Möglichkeiten.
Jetzt nimm dir das nächste Element aus M, dann hast du noch (n-1) Möglichkeiten dieses auf ein Element aus N abzubilden.
usw.
Für das letzte Element hast du dann noch $\begin{eqnarray*} n - m + 1 \end{eqnarray*}$ Möglichkeiten.
(Das ist natürlich kein Beweis aber eine Begründung)

Für b) fang einfach mit dem kleinsten Element aus M

c) und d) sind Spezialfälle, denn wenn die Funktion eineindeutig sein soll müssen M und N gleichviele Elemente enthalten.

(Das ist übrigends eine typische Aufgabe aus der Algebra.)

Edit: Fehler korrigiert.

17.10.2005, 00:10

Mathespezialschüler

Auf diesen Beitrag antworten »

@irre.flex
Deine Erklärung passt nicht zu deine Formel. Und außerdem soll die Abbildung bei a) noch nicht unbedingt bijektiv sein.
Desweiteren sind deine Bezeichnungen schlecht gewählt, denn $\begin{eqnarray*} m \end{eqnarray*}$ und $\begin{eqnarray*} n \end{eqnarray*}$ sind schon festgelegt!

@Sunwater
a) Wie viele Möglichkeiten hast du bei jedem Element von $\begin{eqnarray*} M \end{eqnarray*}$ eines aus $\begin{eqnarray*} N \end{eqnarray*}$ auszuwählen? Wie viele macht das insgesamt?
b) Einfach mal an die 6 Grundbegriffe der Kombinatorik denken. Permutationen, Variationen, Kombination jeweils unterteilt in 1) mit und 2) ohne Berücksichtigung der Reihenfolge.

Gruß MSS

17.10.2005, 11:49

irre.flexiv

Auf diesen Beitrag antworten »

Da hab ich mich ja ordentlich reingeritten *g

Aber a) ist bei mir nicht surjektiv. Deshalb gibt es für das letzte Element auch n-m+1 Möglichkeiten und nicht eine.

Ich bin von der Definition aus meiner Schulzeit ausgegangen. Eindeutig war eine injektive Funktion. Eineindeutig eine bijektive.

17.10.2005, 11:56

Auf diesen Beitrag antworten »

Da herrscht in der Tat Begriffschaos, was nicht deine Schuld ist. Die Wikipedia widerspricht sich in dieser Hinsicht z.B. selbst

http://de.wikipedia.org/wiki/Eindeutigkeit

vs.

http://de.wikipedia.org/wiki/Injektivit%C3%A4t
http://de.wikipedia.org/wiki/Bijektivit%C3%A4t .

Ich denke mal in Hinblick auf die beabsichtigten Kombinatorik-Formeln, dass bei a) und b) schlicht und einfach alle Abbildungen (bei b) natürlich nur monoton wachsende) gemeint sind, und bei c) und d) dann injektive Abbildungen.

Vielleicht kann Sunwater ja auch noch aufklären, was bei ihm unter "eindeutig" und "eineindeutig" zu verstehen ist.

17.10.2005, 15:49

Mathespezialschüler

Auf diesen Beitrag antworten »

Da ich mit eineindeutig auch immer bijektiv verbinde, habe ich nicht bemerkt, dass Bijektivität hier ja gar nicht möglich ist für $\begin{eqnarray*} n\neq m \end{eqnarray*}$ . Ich meinte bei a) natürlich die Injektivität. Eine eindeutige Abbildung ist für mich einfach eine nicht notwendigerweise injektive Funktion. Entsprechend steht hier eineindeutig wohl im Sinne von injektiv. Denn dass es Bijektivität bedeuten soll, ist ja eigentlich schon damit auszuschließen, dass gar keine bijektive Abbildung existiert (zumindest im allgemeinen Fall). Deshalb würde ich es folgendermaßen interpretieren:
eindeutige Abbildungen - alle Funktionen
eineindeutige Abbildungen - alle injektiven Funktion.

Gruß MSS

17.10.2005, 15:52

Auf diesen Beitrag antworten »

Dann stimmen wir ja schon mal überein. Augenzwinkern

17.10.2005, 17:59

Sunwater

Auf diesen Beitrag antworten »

Ich bin auch der Meinung eine eindeutige Abbildung ist erstmal nur injektiv, da jedem "x genau ein y zugeordnet wird". Also es quasi eine Funktion ist.
Ist dann noch die Anzahl der Elemente in beiden Mengen gleich, dann ist sie auch surjektiv und somit bijektiv.

@Mathespezialschüler

das hilft mir erstmal weiter... danke.

17.10.2005, 19:18

Mathespezialschüler

Auf diesen Beitrag antworten »

@Sunwater
Zwischen "jedem x wird genau ein y zugeordnet" und "injektiv" besteht aber eine Riesenunterschied! Also, was meinst du denn jetzt? Soll das "auch" signalisieren, dass du irre.flexiv Recht gibst?

Gruß MSS

17.10.2005, 20:07

Sunwater

Auf diesen Beitrag antworten »

Zitat:

Zwischen "jedem x wird genau ein y zugeordnet" und "injektiv" besteht aber eine Riesenunterschied! Also, was meinst du denn jetzt? Soll das "auch" signalisieren, dass du irre.flexiv Recht gibst?

naja, nicht ganz - besser formuliert:

eine injektive Abbildung von einer Menge M in eine Menge N bedeutet für mich
dass jedem m $\begin{eqnarray*} \in \end{eqnarray*}$ M höchstens ein n $\begin{eqnarray*} \in \end{eqnarray*}$ N zugeordnet wird. Also es müssen nicht alle Elemente der Bildmenge auftreten ( sonst wäre es ja auch gleich bijektiv ) - aber das ist meine Meinung nach 2 Vorlesung - ich hoffe, ich habe das so richtig verstanden?!

ein Kreis in einem Koordinatensystem ist für mich z.B. keine Funktion, da manchen x mehrere y zugeordnet werden.
Eine Funktion ist immer eindeutig ( = injektiv ), kann aber auch eineindeutig sein ( surjektiv -> bijektiv ). Die Quadratfunktion z.B. ist injektiv da für jedes x genau ein y existiert, aber nicht bijektiv, weil von einem y z.B. 9 kann man nicht eindeutig auf das x schließen ( 3 oder -3 ).
Die Wurzelfunktion dagegen ist bijektiv ( jedenfalls im Rahmen der positiv reellen Zahlen )...

17.10.2005, 20:44

Sunwater

Auf diesen Beitrag antworten »

hab jetzt auch alle Aufgaben raus - wenn man es sich mit ein paar Zahlen mal aufschreibt erkennt man irgendwann mal die Prinzipien der Kombinatorik - danke!

17.10.2005, 21:48

Mathespezialschüler

Auf diesen Beitrag antworten »

Nein, du hast es nicht richtig verstanden. Dass nicht alle Elemente der Bildmenge auftreten ist "nicht surjektiv".
Dass die Quadratfunktion injektiv ist, ist falsch. Gerade weil es zu manchen Werten, z. B. 9, zwei x-Werte gibt, deren Funktionswert 9 ist, ist die Funktion nicht injektiv. Die Injektivität hast du eindeutig noch nicht verstanden. Guck dir doch mal den Wikipedia-Artikel dazu an!

Gruß MSS

17.10.2005, 22:17

Sunwater

Auf diesen Beitrag antworten »

hast recht - jetzt hab ich's geschnallt - es geht nicht darum, dass jedem x ein y zugeordnet werden kann, sondern dass die Zuordnung wieder eindeutig zurückführbar ist - also eineindeutig ist.
Wäre also die Tangensfunktion injektiv aber nicht surjektiv?

17.10.2005, 22:18

Mathespezialschüler

Auf diesen Beitrag antworten »

Nein, die Tangensfunktion ist surjektiv, aber nicht injektiv. unglücklich

Gruß MSS

18.10.2005, 09:41

Sunwater

Auf diesen Beitrag antworten »

ich glaub langsam hab ich's... is aber nicht easy...
also ist f(x) = x² weder injektiv noch surjektiv. betrachtet man aber nur den linken Ast der Parabel ( also x größergleich 0 ), dann ist die Funktion injektiv aber trotzdem noch nicht surjektiv - richtig?

18.10.2005, 09:46

Auf diesen Beitrag antworten »

Wenn man von surjektiv (oder nicht) sprechen will, muss man immer den Bildraum mit angeben! So ist z.B. $\begin{eqnarray*} f(x)=x^2 \end{eqnarray*}$ als Funktion

$\begin{eqnarray*} f:\; \mathbb{R} \to \mathbb{R} \end{eqnarray*}$ weder injektiv noch surjektiv,
$\begin{eqnarray*} f:\; [0,\infty) \to \mathbb{R} \end{eqnarray*}$ injektiv, aber nicht surjektiv,
$\begin{eqnarray*} f:\; \mathbb{R} \to [0,\infty) \end{eqnarray*}$ surjektiv, aber nicht injektiv,
$\begin{eqnarray*} f:\; [0,\infty) \to [0,\infty) \end{eqnarray*}$ injektiv und surjektiv, also bijektiv.

31.10.2005, 16:04

The_Lion

Auf diesen Beitrag antworten »

Ich habe eine ähnliche Aufgabe:
Zu endlichen Mengen M und N betrachten wir Abb(M,N):= {f: M-->N},
die Menge aller Abbildungen von M nach N.

a) Man schreibe Abb(M,N) für M={a,b} und die drei Fälle N={1},{1,2}{1,2,3}
komplett auf.

b) Man bestimme allgemein die Kardinalität von Abb(M,N).

c) Was ändert sich, wenn wir nur injektive Abbildungen betrachten?

Ich fange mal mit a) an.
M={a,b}, N={1}
Abb(M,N)= { f(a)=1 , f(b)=1 }

M={a,b}, N={1,2}
Abb(M,N)= { {a->1, b->1} ,{a->1,b->2},{a->2,b->1}, {a->2,b->2} }

M={a,b}, N={1,2,3}
Abb(M,N)= { {a->1, b->1} , {a->1,b->2}, {a->2,b->1}, {a->2,b->2}, {a->1,b->3}, {a->2,b->3}, {a->3,b->1}, {a->3,b->2}, {a->3,b->3} }

Hab ich soweit erstmal alles richtig verstanden ?
Zur Kardinalität poste ich später auch noch was.

31.10.2005, 19:23

Mathespezialschüler

Auf diesen Beitrag antworten »

Ja, das stimmt erstmal so.

Gruß MSS

01.11.2005, 20:36

The_Lion

Auf diesen Beitrag antworten »

zu Aufgabe b):
|Abb(M,N)| = |N|^|M|, wie aus a) folgt.

Dort steht, ich soll es allgemein beweisen. Mit vollständiger Induktion ist also nicht zu helfen, da das Ganze ja von ZWEI Variablen, |M|und |N| abhängt.

01.11.2005, 23:31

Mathespezialschüler

Auf diesen Beitrag antworten »

Nein, das folgt nicht aus a). Für a) gilt es zwar, aber du musst es ja für den allgemeinen Fall beweisen. Und da überlegst du dir einfach, wie viele Möglichkeiten du hast, ein Element aus $\begin{eqnarray*} M \end{eqnarray*}$ auf eines aus $\begin{eqnarray*} N \end{eqnarray*}$ abzubilden.

Gruß MSS

02.11.2005, 01:07

The_Lion

Auf diesen Beitrag antworten »

ok,

Sei |M| = m, |N| = n.

Jedes Element aus M kann auf n verschiedene Möglichkeiten nach N abgebildet werden.
Wie komme ich von hier auf |N|^|M| ?
Ich weiss, n*n*n*...*n mit insgesamt m Faktoren, aber den formalen Beweis bekomme ich nicht so hin momentan.
"kombinatorik" (in Klammern, weils ja nix schwieriges ist) ist nicht so mein Ding. Hab bisher damit nix zu tun gehabt.

02.11.2005, 19:03

Mathespezialschüler

Auf diesen Beitrag antworten »

Zitat:

Original von The_Lion
Wie komme ich von hier auf |N|^|M| ?
Ich weiss, n*n*n*...*n mit insgesamt m Faktoren, aber den formalen

*lol* Das ist doch grad $\begin{eqnarray*} n^m \end{eqnarray*}$ und damit bist du doch fertig.

Gruß MSS

02.11.2005, 19:23

The_Lion

Auf diesen Beitrag antworten »

ja, mir ist schon klar, dass das n^m ist, aber wie begründe ich die Multiplikation von n*n*...*n mit m Faktoren ?

02.11.2005, 23:41

Mathespezialschüler

Auf diesen Beitrag antworten »

Für jedes hast du $\begin{eqnarray*} n \end{eqnarray*}$ Möglichkeiten. Das insgesamt $\begin{eqnarray*} m \end{eqnarray*}$ -mal. Und daraus ergibt sich das sofort. Das ist einfach grundlegende Kombinatorik, da muss man nich viel mehr begründen.

Gruß MSS

03.11.2005, 14:55

The_Lion

Auf diesen Beitrag antworten »

Wenn man nur die injektiven Abbildungen betrachtet, dann müssten es n! (a Fakultät) Abbildungen sein, korrekt?

Könnte man nicht zustäzlich, statt {a->1,b->1} auch einfach {a->1} betrachten, dann hätte man wieder n^m Möglichkeiten.
Oder ist letzere Betrachtungsweise nicht möglich, da Abbildungen keine Definitionslücken haben dürfen ?
Es heisst ja in der Definition: JEDEM x€X wird genau ein y€Y zugeordnet.

03.11.2005, 20:07

Mathespezialschüler

Auf diesen Beitrag antworten »

Nein, es ist nicht. Zunächst müssen wir $\begin{eqnarray*} |M|\leq |N| \end{eqnarray*}$ voraussetzen, sonst haben wir keine Injektivität. Für das erste Element aus $\begin{eqnarray*} M \end{eqnarray*}$ hast du $\begin{eqnarray*} n \end{eqnarray*}$ Möglichkeiten, für das zweite $\begin{eqnarray*} n-1 \end{eqnarray*}$ Möglichkeiten. Das ganze geht aber nicht unbedingt bis $\begin{eqnarray*} 1 \end{eqnarray*}$ , sondern nur bis du alle Elemente von $\begin{eqnarray*} M \end{eqnarray*}$ durch hast.
Beim zweiten: Ja, natürlich musst du auch $\begin{eqnarray*} b \end{eqnarray*}$ ein Bild zuordnen.

Gruß MSS

Neue Frage »

Antworten »

Anzahl der eindeutigen Abbildungen

Verwandte Themen