Diskrete Mathmatik < Sonstiges < Hochschule < Mathe < Vorhilfe
|
Hallo vielleicht kann mir ja irgendein Mathegenie helfen
Aufgabe 1:
Ein Lehrer erzählt seinen Kollegen:" Meine Klasse hat 34 Schüler. 19 davon sind Jungen. 29 Schüler stehen im Schnitt 3 oder besser. Von diesen sind 16 Jungen. 27 haben Religion. Von diesen sind 17 Jungen und 15 stehen 3 oder besser. 13 Jungen stehen 3 oder besser und haben Religion"
Eine Kollegin stutzt:" Das geht doch gar nicht"
Hat sie oder er recht?
Aufgabe 2:
Bestimmen Sie: 1 <= k <= n
a) Die Anzahl der Permutationenvon n Objekten mit genau einem Fixpunkt
b) Die Anzahl der Permutation mit k Fixpunkten
Vielen Dank im Voraus!!
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
|
|
| |
|
Hallo!
Der Widerspruch schleicht sich hier ein:
Der Lehrer spricht von seinen Religionsschülern und sagt
> Von diesen sind 17 Jungen und 15 stehen 3 oder
> besser.
Und dann sagt er:
> 13 Jungen stehen 3 oder besser und haben Religion"
Was nun, 13 oder 15?!
Gruß, banachella
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:01 Do 19.05.2005 | | Autor: | Julius |
Hallo Fabian!
Es sei [mm] $\Omega$ [/mm] die Menge aller Permutationen von [mm] $\{1,2,\ldots,n\}$.
[/mm]
Wir definieren uns:
[mm] $A_j:=\{(a_1,a_2,\ldots,a_n) \in \Omega\, : \, a_j=j\}$.
[/mm]
Wegen
[mm] $|A_{i_1} \cap \ldots \cap A_{i_r}| [/mm] = (n-r)!$
kann man mit der ![[]](/images/popup.gif) Siebformel berechnen:
[mm] $\left| \bigcup\limits_{j=1}^n A_j \right| [/mm] = n! [mm] \sum\limits_{r=1}^n (-1)^{r-1} \cdot \frac{1}{r!}$.
[/mm]
Dementsprechend ist die Anzahl der fixpunktfreien Permuationen gleich
$n! - n! [mm] \sum\limits_{r=1}^n (-1)^{r-1} \cdot \frac{1}{r!} [/mm] = n! [mm] \sum\limits_{r=0}^n (-1)^r \cdot \frac{1}{r!}$.
[/mm]
Nun wollen wir die Anzahl der Permutationen von [mm] $1,2,\ldots,n$ [/mm] berechne, die genau $k$ Fixpunkte besitzen.
Dazu müssen wir die $k$ Fixpunkte wählen (dafür gibt es ${n [mm] \choose [/mm] k}$ Möglichkeiten) und für das $n-k$-elementige Komplement die Anzahl der fixpunktfreien Permutationen bestimmen (davon gibt es, siehe oben, $(n-k)! [mm] \sum\limits_{r=0}^{n-k} (-1)^r \cdot \frac{1}{r!}$ [/mm] Stück).
Es gibt demnach:
${n [mm] \choose [/mm] k} [mm] \cdot [/mm] (n-k)! [mm] \sum\limits_{r=0}^{n-k} (-1)^r \cdot \frac{1}{r!}$
[/mm]
Permutationen einer $n$-elementigen Menge mit genau $k$ Fixpunkten.
Viele Grüße
Julius
|
|
|
|
