Permutationen & Binet < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 17:14 Fr 09.01.2009 | | Autor: | Tasel |
| Aufgabe 1 | | Wie viel Permutationen der Zahlen 1, 2, 3, ..., 2n gibt es, bei denen keine ungerade Zahl auf ihrem ursprünglichen Platz steht? |
| Aufgabe 2 | Beweise für die Fibonacci-Zahlen:
[mm] $F_{m} [/mm] = [mm] \lfloor \bruch{1}{\wurzel{5}}(\bruch{1+\wurzel{5}}{2})^{m}+\bruch{1}{2} \rfloor$ [/mm] |
Die Aufgabe 1 habe ich wie folgt gelöst:
S = # Permutationen der Zahlen 1,2,...2n, bei denen keine ungerade Zahl auf ihrem ursprünglichen Platz steht.
[mm] $\Rightarrow [/mm] |S| = (2n)!$
[mm] $\Rightarrow |A_{i}| [/mm] = (2n-1)!$
[mm] $|A_{i} \cap A_{j}| [/mm] = (2n-2)!$
[mm] $|A_{i} \cap A_{j} \cap A_{s}| [/mm] = (2n-s)!$
[mm] $D_{n} [/mm] = [mm] (2n)!-|A_{i}|+|A_{i} \cap A_{j}|-+...-|A_{i} \cap A_{j} \cap A_{s}|$
[/mm]
$= [mm] (2n)!-\summe_{s=1}^{n}|A_{i}|+\summe_{0\le i\le j\le n}^{n}|A_{i} \cap A_{j}|-+...-(-1)^{n}$
[/mm]
$= [mm] (2n)!-n(2n-1)!+\pmat{ n \\ 2 }(2n-1)!-+...-(-1)^{n}$
[/mm]
$= [mm] (2n)!+\summe_{s=1}^{n}\pmat{ n \\ 2 }(2n-s)!(-1)^{s}$
[/mm]
$= [mm] \summe_{s=0}^{n}\pmat{ n \\ 2 }(2n-s)!(-1)^{s}$
[/mm]
Für n=1,2,3 habe ich das ganze mal getestet und es scheint auch zu stimmen. Ich bin mir allerdings unsicher, wann es [mm] $(-1)^{n}$ [/mm] heißen muss und wann es [mm] $(-1)^{s}$ [/mm] heißen muss. Hoffe mir kann da einer helfen ob dies so stimmt.
Bei der Aufgabe 2 habe ich noch so meine Probleme. Die Form ähnelt der, der Binet-Form für Fibonaccizahlen. Nur wie um alles in der Welt bekomme ich aus der z.B. die Gaußklammern? Aus dem gegebenen könnte man sie mittels eines Faktors $k$ entfernen, nur was mache ich dann mit $k$? Vll. weiß auch hier einer Rat.
Auf alle Fälle schonmal ein dickes Danke!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:20 Mo 12.01.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
