Anzahl von Permutationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Wieviele Permutationen [mm] \pi [/mm] von [mm] \{1, 2, . . . , n\} [/mm] gibt es, mit [mm] \pi [/mm] (k) [mm] \le [/mm] k+1 für alle 1 [mm] \le [/mm] k [mm] \le [/mm] n−1? |
Hallo!
Wie kommt man auf die Anzahl der möglichen Permutationen?
Danke im Voraus!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:10 Mo 23.02.2009 | | Autor: | pelzig |
Sei [mm] $\Omega_n:=\{\pi\in S_n\mid \pi(k)\le k+1\text{ für alle }1\le k\le n-1\}$. [/mm] Es ist [mm] $|\Omega_n|=2\cdot|\Omega_{n-1}|$.
[/mm]
Man kann es sich aber auch so plausibel machen: Für ein festes [mm] $n\in\IN$ [/mm] will ich ein [mm] $\pi\in\Omega_n$ [/mm] konstruieren. Es muss gelten [mm] $\pi(1)\le [/mm] 2$ (also zwei Möglichkeiten), [mm] $\pi(2)\le [/mm] 3$ (Nach Wahl von [mm] $\pi(1)$ [/mm] wieder nur zwei Möglichkeiten), usw...
Gruß, Robert
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:18 Mo 23.02.2009 | | Autor: | statler |
Zitat:
> Es ist [mm]|\Omega_n|=2\cdot|\Omega_{n-1}|[/mm]!
Hallo Robert,
mir fällt gerade auf, daß es nicht günstig ist, bei Sätzen, die von Permutationen handeln und mit einer nat. Zahl oder einer Unbekannten, die eine nat. Zahl darstellt, enden, als Satzabschluß ein Ausrufezeichen zu wählen. Das könnte verwirren.
Gruß aus HH-Harburg
Dieter
|
|
|
|
