Abbildungen und Injektionen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:14 Fr 28.08.2009 | | Autor: | hilado |
| Aufgabe | Sei N eine n-Menge, R eine r-Menge und K eine k-Teilmenge von R.
1. Wie viele Abbildungen von N nach R lassen die k Punkt von K aus?
Wie viele Injektionen von N nach R lassen die k Punkte von K aus?
2. Wie viele Abbildungen von N nach R lassen genau die k Punkte von K aus?
Wie viele Injektionen von N nach R lassen genau die k Punkte von K aus?
3. Wie viele Abbildungen von N nach R lassen k Punkte aus?
Wie viele Injektionen von N nach R lassen k Punkte aus? |
Bei allen drei Fragestellungen ist doch die Lösung:
[mm] n^{r-k} [/mm] (für die Abbildungen, denn jedes n kann auf ein Element in der Menge R \ K abgebildet werden, sprich r - k)
n! * [mm] \vektor{r - k \\ n}
[/mm]
Stimmt das?
|
|
| |
|
> Sei N eine n-Menge, R eine r-Menge und K eine k-Teilmenge
> von R.
mit "n-Menge" ist wohl eine Menge mit n Elementen gemeint
> 1. Wie viele Abbildungen von N nach R lassen die k Punkte von K aus?
> Wie viele Injektionen von N nach R lassen die k Punkte von K aus?
>
> 2. Wie viele Abbildungen von N nach R lassen genau die k Punkte von K aus?
> Wie viele Injektionen von N nach R lassen genau die k Punkte von K aus?
>
> 3. Wie viele Abbildungen von N nach R lassen k Punkte aus?
> Wie viele Injektionen von N nach R lassen k Punkte aus?
> Bei allen drei Fragestellungen ist doch die Lösung:
> [mm] n^{r-k} [/mm] ![[notok]](/images/smileys/notok.gif "[notok]")
> (für die Abbildungen, denn jedes n kann auf ein
> Element in der Menge R \ K abgebildet werden, sprich r - k)
>
> n! * [mm]\vektor{r - k \\ n}[/mm]
>
> Stimmt das?
Hallo hilado,
es ist wohl doch nicht ganz so einfach.
In (1.a) sind alle Abbildungen von N nach [mm] R\backslash{K} [/mm]
gefragt. Davon gibt es [mm] (r-k)^n, [/mm] denn jedem der n
Elemente von N kann ein beliebiges Element aus
[mm] R\backslash{K} [/mm] als Funktionswert zugeordnet werden.
In (1.b) geht es um die injektiven Abbildungen
von N nach [mm] R\backslash{K} [/mm] . Solche Abbildungen sind nur
dann möglich, wenn [mm] n\le{r-k} [/mm] . Ihre Anzahl hast
du oben richtig angegeben.
In (2.) sollen genau die Punkte von K ausgelas-
sen werden. Dies bedeutet, dass die Abbildung
[mm] N\to R\backslash{K} [/mm] surjektiv sein soll.
Die Anzahl der Abbildungen in (2.a) ist also wohl
kleiner als die Anzahl in (1.a), da i.A. nicht
alle dort gezählten Abbildungen surjektiv sind.
Die Abbildungen in (2.b) bilden N injektiv und
surjektiv, also bijektiv auf [mm] R\backslash{K} [/mm] ab. Dies
ist nur dann möglich, wenn $n=r-k$ ist, und in
diesem Falle sind es genau n! Abbildungen.
Vorerst einmal so weit.
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 06:48 Sa 29.08.2009 | | Autor: | felixf |
Hallo!
> 3. Wie viele Abbildungen von N nach R lassen k Punkte aus?
> Wie viele Injektionen von N nach R lassen k Punkte aus?
Nun, wenn $n [mm] \le [/mm] r - k$ ist, dann laesst jede Abbildung von $N$ nach $R$ (mindestens) $k$ Punkte aus.
Sei also $n > r - k$. In dem Fall gibt es keine Injektion von $N$ nach $R$, die $k$ Punkte auslaesst.
Bei den "normalen" Abbildungen sieht es anders aus. Ist $r - k < 1$ und $n > 0$, so gibt es keine solche Abbildung. Ist $r - k < 0$, sowieso nicht. Ist $r - k = 0$ und $n = 0$, so gibt es genau eine solche Abbildung.
Sei also $n > r - k [mm] \ge [/mm] 1$. Vielleicht ist es einfacher, die Abbildungen zu erzaehlen, die die Bedingung nicht erfuellen. Dazu schaue die Abbildungen [mm] $\varphi [/mm] : N [mm] \to [/mm] R$ an mit [mm] $|\varphi(N)| [/mm] = r - [mm] \ell$, $\ell [/mm] = 0, [mm] \dots, [/mm] k-1$. Die Anzahl der Abbildungen [mm] $\varphi$ [/mm] mit [mm] $|\varphi(N)| [/mm] = r - [mm] \ell$ [/mm] entspricht der Anzahl der surjektiven Abbildungen von $N$ auf eine $r - [mm] \ell$-Menge [/mm] mal die Anzahl der $r - [mm] \ell$-Teilmengen [/mm] von $R$ (also [mm] $\binom{r}{r - \ell} [/mm] = [mm] \binom{r}{\ell}$). [/mm] Ist [mm] $S_{n,r-\ell}$ [/mm] die Anzahl der surjektiven Abbildungen von einer $n$-Menge auf eine [mm] $r-\ell$-Menge, [/mm] so ist die Anzahl der Abbildungen, die wir nicht haben wollen, also [mm] $\sum_{\ell=0}^{k-1} \binom{r}{r - \ell} S_{n,r-\ell}$ [/mm] und somit die Anzahl der Abbildungen, die wir haben wollen, [mm] $r^n [/mm] - [mm] \sum_{\ell=0}^{k-1} \binom{r}{r - \ell} S_{n,r-\ell}$.
[/mm]
Aber wie bestimmt man nun [mm] $S_{n,t}$? [/mm] Das kannst du z.B. ![[]](/images/popup.gif) hier oder hier nachlesen.
LG Felix
|
|
|
|
