Abbildungen < Sonstiges < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Bestimmen Sie für k,n [mm] \in \IN [/mm] die Anzahl
a) aller Abbildungen {1...k} [mm] \to [/mm] {1...n}
b) aller injektiven Abbildungen {1...k} [mm] \to [/mm] {1...n}
c) aller bijektiven Abbildungen {1...k} [mm] \to [/mm] {1...n} |
Hi, hab hier so meine Schwierigkeiten.
c) da gilt ja k=n und dann müssten das alle Permutationen sein, also k!=n!
b) hier weiß ich, dass n [mm] \ge [/mm] k ist und das kein Element aus {1...k} das gleiche Bild haben darf.
also k! * [mm] \vektor{n\\ k-n}
[/mm]
(da immer ein (n-k)-Tupel aus {1...n} ohne Urbild bleibt und für jedes dieser Tupel hab ich ja wieder k! Möglichkeiten eine Abb. zu definieren)
a) bei der a) steh ich aber ziemlich auf dem schlauch. (K={1...k};N={1...n})
Hab mir überlegt:
Ich kann ja ganz K einem einzigen Element von N zuordnen [mm] \Rightarrow [/mm] n Mögl.
Dann kann ich ganz K einem Paar aus N zuordnen, dabei kann ich aber ja alle Elemente aus K beliebig auf jedes einzelne Paar verteilen...
Dann gehts weiter mit 3-Tupel .........
Ich hoffe mir kann jmd helfen.
mfg
ConstantinJ
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:32 So 06.05.2012 | | Autor: | Marcel |
Hallo,
> Bestimmen Sie für k,n [mm]\in \IN[/mm] die Anzahl
> a) aller Abbildungen {1...k} [mm]\to[/mm] {1...n}
> a) bei der a) steh ich aber ziemlich auf dem schlauch.
> (K={1...k};N={1...n})
> Hab mir überlegt:
> Ich kann ja ganz K einem einzigen Element von N zuordnen
> [mm]\Rightarrow[/mm] n Mögl.
> Dann kann ich ganz K einem Paar aus N zuordnen, dabei kann
> ich aber ja alle Elemente aus K beliebig auf jedes einzelne
> Paar verteilen...
> Dann gehts weiter mit 3-Tupel .........
schreibe eine Abbildung $f: [mm] \{1,...,k\} \to \{1,...,n\}$ [/mm] mal als [mm] $k\,$-Tupel [/mm] mit Werten in [mm] $\{1,...,n\}$ [/mm] (die Menge solcher Tupel ist gleichmächtig zu der Menge der Abbildungen wie oben - kannst Du eine Bijektion angeben? Bzw. wenn Du genau liest, findest Du sie hier eigentlich - aber dann ist noch zu zeigen, dass das wirklich eine injektive und surjektive Abbdildung ist (was sehr schnell geht)!):
Das heißt wir identifizieren [mm] $f:\{1,...,k\} \to \{1,...,n\}$ [/mm] mit
[mm] $$(f(1),...,f(k))\,,$$
[/mm]
wobei $f(j) [mm] \in \{1,...,n\}$ [/mm] gefordert wird.
Wieviele solcher [mm] $k\,$-Tupel [/mm] gibt es?
Naja, für $f(1)$ kommen [mm] $n\,$ [/mm] Werte in Frage, für [mm] $f(2)\,$ [/mm] dann nochmal [mm] $n\,$-Werte, [/mm] d.h. für [mm] $k=2\,$ [/mm] gäbe es also [mm] $n*n=n^2$ [/mm] solcher Tupel. (Mach' Dir das am besten an einem Baumdiagramm klar: Jeder der [mm] $n\,$ [/mm] Werte für [mm] $f(2)\,$ [/mm] kann man ja mit dem für [mm] $f(1)\,$ [/mm] kombinieren!)
Für [mm] $k=3\,$ [/mm] kämen für [mm] $f(3)\,$ [/mm] dann erneut [mm] $n\,$ [/mm] mögliche Werte hinzu: [mm] $n^2*n=n^3$ [/mm] solcher Tupel...
Gruß,
Marcel
|
|
|
| |
|
Vielen Dank für die schnelle Antwort.
Die leuchtet mir auch direkt ein. Mit meiner Überlegung wäre ich wohl nie fertig geworden.
Zur b) und c) stimmen da die Antworten ?
Gruß
ConstantinJ
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:37 So 06.05.2012 | | Autor: | Marcel |
Hallo,
> Vielen Dank für die schnelle Antwort.
>
> Die leuchtet mir auch direkt ein. Mit meiner Überlegung
> wäre ich wohl nie fertig geworden.
>
> Zur b) und c) stimmen da die Antworten ?
schauen wir nochmal rein:
> c) da gilt ja k=n und dann müssten das alle Permutationen sein, also k!=n!
> b) hier weiß ich, dass n $ [mm] \ge [/mm] $ k ist und das kein Element aus {1...k} das gleiche Bild haben darf.
> also k! * $ [mm] \vektor{n\\ \red{k-n}} [/mm] $
bei b) war das die Menge der injektiven Abbildungen [mm] $\{1,...,k\} \to \{1,..,n\}$. [/mm] In Tupelnotation komme ich mit ähnlichen Überlegungen zu dem Schluss, dass es derer
[mm] $$n*(n-1)*...*(n-k+1)=(\produkt_{\ell=1}^n \ell)/\produkt_{p=1}^{n-k}p=n!/(n-k)!=n!/(k!(n-k)!)*k!={n \choose k}*k!$$
[/mm]
geben muss. Bei Dir steht das gleiche da (wegen ${n [mm] \choose [/mm] k}={n [mm] \choose [/mm] n-k}$) - also stimmt das!
(Ich gehe mal davon aus, dass Du nicht ${n [mm] \choose \red{k-n}}*k!\,,$ [/mm] sondern ${n [mm] \choose \blue{n-k}}*k!$ [/mm] gemeint hast - ansonsten wäre das Deinige doch falsch!)
Bei c) ist es, ohne groß irgendwas weiter überlegen zu müssen, das gleiche Spiel wie in b) mit [mm] $k=n\,.$ [/mm] Also: Auch da stimmt Deine Überlegung. (Weil $n!={n [mm] \choose n}*n!\,.$)
[/mm]
Fazit: Ja!
Gruß,
Marcel
|
|
|
| |
|
Ok, Danke.
Ich versuch es dann mit ordentlicher Begründung aufzuschreiben.
Gruß
ConstantinJ
|
|
|
|
