Kombinatorik < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 11:54 Mo 30.07.2012 | | Autor: | nadine85 |
| Aufgabe | Für alle n ∈ N sei im Folgenden Sn := {f : {1, . . . , n} → {1, . . . , n} : f bijektiv} die
Menge aller Bijektionen auf der Menge {1, . . . , n} und Fn := {f ∈ Sn : ∀ x ∈ {1, . . . , n} :
f(x) 6= x} die Menge aller fixpunktfreien Bijektionen.
(a) Füllen Sie zunächst folgende Tabelle aus, indem Sie die Elemente von S1, S2, S3 und
ggf. auch von S4 explizit hinschreiben und auf Fixpunktfreiheit untersuchen (hierbei ist für jede Menge A mit |A| die Mächtigkeit von A bezeichnet).
n |Sn| |Fn|
1
2
3
4
(b) Zeigen Sie, dass für alle n ∈ N \ {1, 2} gilt
|Fn| = (n − 1) · |Fn−1| + |Fn−2|. (1)
(c) Folgern Sie aus der Formel (1) die Identität
|Fn| = n · |Fn−1| + (−1)n, n ∈ N \ {1}. (2)
(d) Folgern Sie aus der Formel (2) die Identität
|Fn| = n! · die Summe aus [mm] ((-1)^k)/k! [/mm] über n bis k=0, n ∈ N. (3)
Hinweis: Vollständige Induktion.
(e) Angenommen, auf einer Tanzparty seien n Pärchen (A1,B1), . . . , (An,Bn). Zu einem der Tanzlieder werde jeder der Personen A1, . . . ,An zufällig jeweils eine der Personen B1, . . . ,Bn zugelost. Bestimmen Sie die Wahrscheinlichkeit pn, mit der dabei nur
Tanzpaarungen (Ai,Bj) mit i, j ∈ {1, . . . , n} und i 6= j entstehen (d.h., dass die beiden Tanzpartner kein Paar bilden). Wie verhält sich diese Wahrscheinlichkeit für
n → ∞?
Hinweis: Formel (3) |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Ich habe leider überhaupt keine Idee und wäre für jeden Kommentar dankbar.
|
|
| |
|
> Für alle [mm] n\in \IN [/mm] sei im Folgenden
> [mm] S_n [/mm] := {f : {1, . . . , n} → {1, . . . , n} : f bijektiv}
> die
> Menge aller Bijektionen auf der Menge {1, . . . , n} und
> [mm] F_n [/mm] := {f ∈ Sn : ∀ x ∈ {1, . . . , n} :f(x) [mm] \not= [/mm] x} die Menge aller fixpunktfreien Bijektionen.
> (a) Füllen Sie zunächst folgende Tabelle aus, indem Sie
> die Elemente von [mm] S_1, S_2, S_3 [/mm] und
> ggf. auch von [mm] S_4 [/mm] explizit hinschreiben und auf
> Fixpunktfreiheit untersuchen (hierbei ist für jede Menge A
> mit |A| die Mächtigkeit von A bezeichnet).
>
> n |Sn| |Fn|
> 1
> 2
> 3
> 4
> [...]
>
> Ich habe leider überhaupt keine Idee und wäre für jeden
> Kommentar dankbar.
Hallo,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") .
Auch wenn Du ideenlos bist: wir erwarten von Dir Lösungsansätze.
Beginnen wir mit Aufgabe a).
Woran scheitert es?
Vielleicht erklärst Du mal, was Dich daran hindert, die Mengen [mm] S_1, S_2, S_3 [/mm] aufzuschreiben. Nur wenn wir das wissen, können wir nämlich helfen.
LG Angela
|
|
|
|
