Kardinalität < Sonstiges < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:49 Mo 04.04.2011 | | Autor: | Mandy_90 |
| Aufgabe | | Seien M und N endliche Mengen der Kardinalität m bzw. n, [mm] n\ge [/mm] m.Man beweise, dass es [mm] \bruch{n!}{(n-m)!} [/mm] injektive Abbildungen von M nach N gibt. |
Hallo^^
Ich komme bei dieser Aufgabe nicht mehr weiter und hoffe jemand kann mir helfen. Die Abbildungen sehen zunächst so aus f:M [mm] \to [/mm] N. Wenn die jetzt injektiv sein sollen, muss gelten: [mm] f(m_{i})=f(m_{j}) [/mm] --> [mm] m_{i}=m_{j}, [/mm] i,j [mm] \in \{1,...,m\} [/mm] mit [mm] M=\{m_{1},...m_{m}\} [/mm] und [mm] N=\{n_{1},...,n_{n}\}.
[/mm]
Jetzt hab ich für [mm] m_{1} [/mm] n Möglichkeiten,die das Bild von [mm] m_{1} [/mm] sein können. Für [mm] m_{2} [/mm] sind es nur noch (n-1) Möglichkeiten usw. Für [mm] m_{m} [/mm] hab ich noch n-(m-1) Möglichkeiten, d.h. n-m+1.
So, bis hierhin bin ich gekommen, aber wie man jetzt auf den Bruch kommt,verstehe ich nicht.
lg
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:33 Mo 04.04.2011 | | Autor: | statler |
> Seien M und N endliche Mengen der Kardinalität m bzw. n,
> [mm]n\ge[/mm] m.Man beweise, dass es [mm]\bruch{n!}{(n-m)!}[/mm] injektive
> Abbildungen von M nach N gibt.
Mahlzeit!
> Ich komme bei dieser Aufgabe nicht mehr weiter und hoffe
> jemand kann mir helfen. Die Abbildungen sehen zunächst so
> aus f:M [mm]\to[/mm] N. Wenn die jetzt injektiv sein sollen, muss
> gelten: [mm]f(m_{i})=f(m_{j})[/mm] --> [mm]m_{i}=m_{j},[/mm] i,j [mm]\in \{1,...,m\}[/mm]
> mit [mm]M=\{m_{1},...m_{m}\}[/mm] und [mm]N=\{n_{1},...,n_{n}\}.[/mm]
Es ist irgendwie unglücklich, den Buchstaben m (und n) für 2 verschiedene Dinge zu verwenden.
> Jetzt hab ich für [mm]m_{1}[/mm] n Möglichkeiten,die das Bild von
> [mm]m_{1}[/mm] sein können. Für [mm]m_{2}[/mm] sind es nur noch (n-1)
> Möglichkeiten usw. Für [mm]m_{m}[/mm] hab ich noch n-(m-1)
> Möglichkeiten, d.h. n-m+1.
> So, bis hierhin bin ich gekommen, aber wie man jetzt auf
> den Bruch kommt,verstehe ich nicht.
Um alle Möglichkeiten zu zählen, mußt du jetzt das Produkt bilden. Und dann rechne mal den Bruch aus, indem du für die Fakultät die Definition einsetzt und kräftig kürzt.
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:10 Di 05.04.2011 | | Autor: | Mandy_90 |
> > Seien M und N endliche Mengen der Kardinalität m bzw. n,
> > [mm]n\ge[/mm] m.Man beweise, dass es [mm]\bruch{n!}{(n-m)!}[/mm] injektive
> > Abbildungen von M nach N gibt.
>
> Mahlzeit!
>
> > Jetzt hab ich für [mm]m_{1}[/mm] n Möglichkeiten,die das Bild von
> > [mm]m_{1}[/mm] sein können. Für [mm]m_{2}[/mm] sind es nur noch (n-1)
> > Möglichkeiten usw. Für [mm]m_{m}[/mm] hab ich noch n-(m-1)
> > Möglichkeiten, d.h. n-m+1.
> > So, bis hierhin bin ich gekommen, aber wie man jetzt
> auf
> > den Bruch kommt,verstehe ich nicht.
>
> Um alle Möglichkeiten zu zählen, mußt du jetzt das
> Produkt bilden. Und dann rechne mal den Bruch aus, indem du
> für die Fakultät die Definition einsetzt und kräftig
> kürzt.
Ok. Ich habe n*(n-1)*(n-2)*...*(n-m+1)=n*(n-1)*(n-2)*...*(n-m)+n*(n-1)*(n-2)*...*1=n*(n-1)*(n-2)*...*(n-m)+n!.
Obwohl, ich kann eigentlich auch schreiben:
n*(n-1)*(n-2)*...*(n-m+1)=n!*(n-m+1).
Was ich sonst noch kürzen kann, seh ich nicht.
Vielen Dank
lg
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:38 Di 05.04.2011 | | Autor: | statler |
Hallo!
> > > Seien M und N endliche Mengen der Kardinalität m bzw. n,
> > > [mm]n\ge[/mm] m.Man beweise, dass es [mm]\bruch{n!}{(n-m)!}[/mm] injektive
> > > Abbildungen von M nach N gibt.
> >
> > Mahlzeit!
> >
> > > Jetzt hab ich für [mm]m_{1}[/mm] n Möglichkeiten,die das Bild von
> > > [mm]m_{1}[/mm] sein können. Für [mm]m_{2}[/mm] sind es nur noch (n-1)
> > > Möglichkeiten usw. Für [mm]m_{m}[/mm] hab ich noch n-(m-1)
> > > Möglichkeiten, d.h. n-m+1.
> > > So, bis hierhin bin ich gekommen, aber wie man jetzt
> > auf
> > > den Bruch kommt,verstehe ich nicht.
> >
> > Um alle Möglichkeiten zu zählen, mußt du jetzt das
> > Produkt bilden. Und dann rechne mal den Bruch aus, indem du
> > für die Fakultät die Definition einsetzt und kräftig
> > kürzt.
>
> Ok. Ich habe
> n*(n-1)*(n-2)*...*(n-m+1)=n*(n-1)*(n-2)*...*(n-m)+n*(n-1)*(n-2)*...*1=n*(n-1)*(n-2)*...*(n-m)+n!.
Das ist ziemlich falsch!
> Obwohl, ich kann eigentlich auch schreiben:
> n*(n-1)*(n-2)*...*(n-m+1)=n!*(n-m+1).
Das ist genauso falsch, die rechte Seite ist größer als die linke. Nimm mal m=2.
n*(n-1)*(n-2)*...*(n-m+1) = [mm] \bruch{n*(n-1)*(n-2)*...*(n-m+1)*(n-m)* ... *2*1}{(n-m)* ... *2*1}, [/mm] und das ist der gesuchte Bruchterm.
Gruß
Dieter
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:26 Mi 06.04.2011 | | Autor: | Mandy_90 |
> Hallo!
>
> > > > Seien M und N endliche Mengen der Kardinalität m bzw. n,
> > > > [mm]n\ge[/mm] m.Man beweise, dass es [mm]\bruch{n!}{(n-m)!}[/mm] injektive
> > > > Abbildungen von M nach N gibt.
> >
> n*(n-1)*(n-2)*...*(n-m+1)=n*(n-1)*(n-2)*...*(n-m)+n*(n-1)*(n-2)*...*1=n*(n-1)*(n-2)*...*(n-m)+n!.
>
> Das ist ziemlich falsch!
>
> > Obwohl, ich kann eigentlich auch schreiben:
> > n*(n-1)*(n-2)*...*(n-m+1)=n!*(n-m+1).
>
> Das ist genauso falsch, die rechte Seite ist größer als
> die linke. Nimm mal m=2.
>
> n*(n-1)*(n-2)*...*(n-m+1) =
> [mm]\bruch{n*(n-1)*(n-2)*...*(n-m+1)*(n-m)* ... *2*1}{(n-m)* ... *2*1},[/mm]
> und das ist der gesuchte Bruchterm.
Ok. Es ist doch (n-m)*...*2*1=(n-m)!,also hab ich im Nenner schonmal (n-m)!. Dann müsste der Term im Zähler =n! sein.
Richtig?
Vielen Dank
lg
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:51 Mi 06.04.2011 | | Autor: | statler |
> > Hallo!
> >
> > > > > Seien M und N endliche Mengen der Kardinalität m bzw. n,
> > > > > [mm]n\ge[/mm] m.Man beweise, dass es [mm]\bruch{n!}{(n-m)!}[/mm] injektive
> > > > > Abbildungen von M nach N gibt.
> > >
> >
> n*(n-1)*(n-2)*...*(n-m+1)=n*(n-1)*(n-2)*...*(n-m)+n*(n-1)*(n-2)*...*1=n*(n-1)*(n-2)*...*(n-m)+n!.
> >
> > Das ist ziemlich falsch!
> >
> > > Obwohl, ich kann eigentlich auch schreiben:
> > > n*(n-1)*(n-2)*...*(n-m+1)=n!*(n-m+1).
> >
> > Das ist genauso falsch, die rechte Seite ist größer als
> > die linke. Nimm mal m=2.
> >
> > n*(n-1)*(n-2)*...*(n-m+1) =
> > [mm]\bruch{n*(n-1)*(n-2)*...*(n-m+1)*(n-m)* ... *2*1}{(n-m)* ... *2*1},[/mm]
> > und das ist der gesuchte Bruchterm.
Hallo!
> Ok. Es ist doch (n-m)*...*2*1=(n-m)!,also hab ich im Nenner
> schonmal (n-m)!. Dann müsste der Term im Zähler =n!
> sein.
Er müßte das nicht nur sein, er ist es! Offenbar doch!
> Richtig?
Ja.
Gruß
Dieter
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:54 Mi 06.04.2011 | | Autor: | pelzig |
Man kann das auch noch etwas anders sehr leicht einsehen: Jede Injektion [mm]f[/mm] von [mm]M[/mm] nach [mm]N[/mm] ist ja, eigeschränkt auf ihr Bild [mm]f(M)[/mm] eine Bijektion. Es gibt [mm]\binom{n}{m}[/mm] verschiedene mögliche Bilder, nämlich genau die [mm]m[/mm]-elementigen Teilmengeen von [mm]N[/mm] und für jede dieser Mengen gibt es [mm]m![/mm] mögliche Bijektionen, also insgesamt [mm]m!\cdot\binom{n}{m}[/mm] Möglichkeiten.
Gruß, Robert
|
|
|
|
