Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » Anzahl der Abbildungen von 2 Mengen bestimmen

Anzahl der Abbildungen von 2 Mengen bestimmen

Universität / Fachhochschule

Binomialkoeffizienten

Lineare Abbildungen

Tags: Abbildung, Monotonie

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
saty24

saty24 aktiv_icon

19:48 Uhr, 17.11.2018

Antworten
Es seien m,n ∈ ℕ ohne {0} Eine Abbildung α:[m] → [n] heißt:
• monoton wachsend, falls α(i)≤α(j) für alle i,j ∈ [m] mit i≤j;
• monoton fallend, falls α(i)≥α(j) für alle i,j ∈ [m] mit i≤j;
• streng monoton wachsend, falls α(i)<α(j) für alle i,j ∈ [m] mit i<j;
• streng monoton fallend, falls α(i)>α(j) für alle i,j ∈ [m] mit i<j.
Bestimmen Sie für jedes Paar ( m,n) jeweils die Anzahl der (streng) monoton wachsenden/fallenden Abbildungen von [m] nach [n].

Leider komme ich bei dieser Aufgabe nicht sehr weit. Ich weiß, was die Monotonie einer Funktion bedeutet, aber wie soll ich die Anzahl der Abbildungen bestimmen ?

Allgemein ist die Anzahl aller Abbildungen zwischen 2 endliche Mengen von N nach M gleich |M||N|. Das ist aber hier nicht den Fall denke ich. Dann habe ich mir überlegt...die Anzahl der bijektiven Abbildungen ist n! und die Anzahl der injektiven Abbildungen, falls |M|≤|N| ist n!(n-m)!

Falls die Abbildung α:[m] nach [n] monoton wachsend ist, dann ist es injektiv ? Ich weiß nicht wie man die Mächtigkeit von [m] und [n] bestimmen soll. Ein Beispiel wäre:
1<1<3=3<4<5=5<6

ist dann die Mächtigkeit von [m]=6?


Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."
Hierzu passend bei OnlineMathe:
Monotonieverhalten (Mathematischer Grundbegriff)
Online-Nachhilfe in Mathematik
Antwort
Ginso

Ginso aktiv_icon

17:38 Uhr, 19.11.2018

Antworten
Kannst du kurz erklären, was [m] ist? mir ist die Notation gerade nicht geläufig
saty24

saty24 aktiv_icon

17:50 Uhr, 19.11.2018

Antworten
Laut meinem Tutor soll [m] die eine Menge in der Art sein: x∈ NN\{0}: 1≤x≤m}

So Weit ich das verstanden habe, wenn es streng monoton wachsend ist, z.B:1<2<3. Dann muss man 3 Fälle unterscheiden, falls m<n,m=n und m>n. Also wenn m<n ist, dann gibt es (nm) injektive Abbildungen. Das weiß ich aber nicht genau wie man das Formal beweisen soll. Ich habe mir einfach als Beispiel für |n|=4 dann falls |m|=1 gibt es 4 injektive Abbildungen, für |m|=2 gibt es 6 dann für |m|=3 gibt es 4 und für |m|=4 gibt es 1.
Falls |m|=|n| dann gibt es nur eine einzige bijektive Abbildung und für |m|>|n| gibt es surjektive Abbildungen, also keine injektive bzw bijektive Abbildungen. Die Anzahl von surjektiven Abbildungen haben wir aber noch nicht gemacht. Analog für streng monoton fallend.

Für monoton wachsende und fallende Abbildungen, dachte ich mir so was wie 1<2<3=3<4<5=5<6. Dann kann |m|≤|n| sein. also dann gibt es n!(m-n)! injektive Abbildungen. Zumindest so habe ich es mir überlegt. Für |m|=|n| gibt es dann n! bijektive Abbildungen. Und wie früher für |m|>|n| ist es nur surjektive Abbildungen.

Wie kann ich also beweisen dass für streng monoton wachsend/fallende Abbildungen (nm) stimmt ?
Antwort
Ginso

Ginso aktiv_icon

18:57 Uhr, 19.11.2018

Antworten
Also zuerst: injektive Abbildungen gibt es mehr als (nm).

Nimm eine beliebige Teilmenge von [n] mit Mächtigkeit m, sortiere sie aufsteigend und du hast eine streng Monotone Abbildung von [m] nach [n], wobei unterschiedliche Teilmengen auch unterschiedliche Abbildungen ergeben.
Umgekehrt ergibt die Bildmenge einer solchen Abbildung immer eine Teilmenge [n] mit Mächtigkeit m und zwar für unterschiedliche Abbildungen auch unterschiedliche Mengen.
Die Anzahl der streng monotonen Abbildungen ist also genau die Zahl der Teilmengen von [n] mit Mächtigkeit m. Wie viele Möglichkeiten gibt es, m elemente von [n] zu wählen?
genau (|[n]|m) also (nm)
Für m>n gibt es natürlich keine und für m=n genau eine streng monotone Abbildung.

schwieriger wird es mit den montonen, da muss ich nochmal drüber nachdenken. Deine Überlegung ist schon mal fehlerhaft, zb kann n größer, kleiner oder gleich sein wie m es gibt immer monotone folgen(zb a(i)=1 für alle i∈[m])
Antwort
Ginso

Ginso aktiv_icon

20:24 Uhr, 19.11.2018

Antworten
Ich bin leider zu keiner schönen Lösung gekommen. Ich kann ja mal meinen Ansatz zeigen, vielleicht kannst du oder jemand anderes was damit anfangen:

Ich bin induktiv herangegangen. Sei A[m,n] die anzahl der monoton steigenden Abbildungen von [m] nach [n].
Schauen wir uns mal für ein beliebiges m und n alle monoton steigenden Abbildungen von [m+1] nach [n] an und achten auf das letzte Element
Wenn das letzte Element einer solchen Abbildung k ist, dann ist die Abbildung ja eine fortsetzung einer monoton steigenden Folge von [m] nach [k]. Umgekehrt kann man jede Folge von [m] nach [k] mit einem k fortsetzen.
Es gibt also genau A[m,k] folgen von [m+1] nach [n] die mit einem k enden.
Also gilt A[m+1,n]=∑i=1nA[m,i]

Anders ausgedrückt:

für m=1 ist(trivialerweise) A[m,n]=n und für m>1 ist A[m,n]=∑i=1nA[m-1,i]

schauen wir uns nun A[n+1,m] an:
Wenn m=1 ist, dann ist das natürlich n+1, ansonsten gilt wie oben:
A[m,n+1]=∑i=1n+1A[m-1,i]=∑i=1nA[m-1,i]+A[m-1,n+1]=A[m,n]+A[m-1,n+1]

Wenn m=2 ist, können wir es damit bereits ausrechen, ansonsten wenden wir den Schritt nochmal auf den letzten Summanden an:
A[m,n]+A[m-1,n+1]=A[m,n]+A[m-10n]+A[m-2,n+1]

den Schritt können wir solange machen, bis wir am Ende A[1,n+1]=n+1=A[1,n] erreichen. Also gilt:
A[m,n+1]=∑j=2mA[j,n]+A[1,n+1]=∑j=2mA[j,n]+A[1,n]+1=1+∑j=1mA[j,n]

für n>1 gilt damit
A[m,n]=1+∑j=1mA[j,n-1]

wir wissen von vorhin, dass
A[m,n]=∑i=1nA[m-1,i]=A[m,1]+∑i=2nA[m-1,i]=1+∑i=1n-1A[m-1,i+1] ist.

Wenn wir da jetzt unsere neue gleichung einsetzen erhalten wir
A[m,n]=1+∑i=1n-1A[m-1,i+1]=1+∑i=1n-11+∑j=1m-1A[j,i]=n+∑i=1n-1∑j=1m-1A[j,i]

Da A[m,1]=1 und A[1,n]=n offensichtlich immer gilt, können wir mit dieser formel jedes A[n,m] ausrechnen. Falls man noch eine explizite Formel findet kann man diese hier benutzen um sie per induktion zu beweisen.
Frage beantwortet
saty24

saty24 aktiv_icon

20:34 Uhr, 19.11.2018

Antworten
Vielen Dank für deine Hilfe. Ich muss mir deinen Ansatz noch genauer anschauen damit ich alles auch selber lösen kann.
Antwort
pwmeyer

pwmeyer aktiv_icon

12:21 Uhr, 20.11.2018

Antworten
Hallo,

man kann die Frage nach den monotonen Abbildungen durch folgenden Trick auf die Frage der streng montonen Abbildung zurückführen:

Wenn α monoton wachsend ist, dann ist folgende Abbildung β streng monoton ( mit anderem Bildbereich):

β(i):=α(i)+i-1

Gruß pwm
Antwort
HAL9000

HAL9000

13:43 Uhr, 20.11.2018

Antworten
Das ganze ist elementare Zählkombinatorik:

Die Anzahl der monoton wachsenden Abbildungen [m]→[n] entspricht der Anzahl Kombinationen mit Wiederholung von m aus n Elementen, das ist n+m-1m. Denn jeder solche Auswahl entspricht den m Funktionswerten, was wegen der Monotonieforderung dann aber genau einer möglichen Funktion mit genau diesen Funktionswerten (in der entsprechenden Vielfachheit gemäß Auswahl) entspricht. Genau dieselbe Anzahl bekommen wir für die monoton fallenden Abbildungen [m]→[n].

Dasselbe Spiel bei den streng monoton wachsenden Abbildungen [m]→[n], nur dass hier die Zuordnung zu Kombinationen ohne Wiederholung von m aus n Elementen erfolgt, das sind nm. Genau dieselbe Anzahl hat man dann für die streng monoton fallenden Abbildungen [m]→[n].

Insbesondere das erste Szenario "Kombinationen mit Wiederholung" mag vielleicht manchem nicht so vertraut sein. Die Verbindung zur wohl bekannteren Anzahlformel "Kombinationen ohne Wiederholung" kann man über eine solche Bijektion α↔β ziehen, wie sie pwmeyer gerade eben angegeben hatte.