Permutation, Zykel < Kombinatorik < Stochastik < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:27 Mi 29.10.2014 | | Autor: | YuSul |
| Aufgabe | Sei [mm] $\Xi=\{1,...,n\}$ [/mm] mit [mm] $n\in\mathbb{N}$ [/mm] und es bezeichne [mm] $\Sigma_{\Xi}$ [/mm] die Menge der Permutationen auf [mm] $\Xi$ [/mm]
Wie viele Permutationen gibt es auf [mm] $\Xi$, [/mm] die einen Zykel mit Länge [mm] $k\in\mathbb{N}$ [/mm] haben, wobei [mm] $k>\frac{n}{2}$ [/mm] |
Hi,
ich habe eine begriffliche Frage zu dieser Aufgabe.
Was ist hier mit Zykel der Länge k gemeint?
Danke.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 05:25 Fr 31.10.2014 | | Autor: | tobit09 |
Hallo YuSul!
> Sei [mm]\Xi=\{1,...,n\}[/mm] mit [mm]n\in\mathbb{N}[/mm] und es bezeichne
> [mm]\Sigma_{\Xi}[/mm] die Menge der Permutationen auf [mm]\Xi[/mm]
>
> Wie viele Permutationen gibt es auf [mm]\Xi[/mm], die einen Zykel
> mit Länge [mm]k\in\mathbb{N}[/mm] haben, wobei [mm]k>\frac{n}{2}[/mm]
> Was ist hier mit Zykel der Länge k gemeint?
Eine mögliche Definition:
Eine Permutation [mm] $\sigma\in\Sigma_\Xi$ [/mm] hat einen Zykel der Länge $k$, falls paarweise verschiedene [mm] $x_1,x_2\ldots,x_k\in\Xi$ [/mm] existieren mit
[mm] $\sigma(x_i)=x_{i+1}$ [/mm] für alle [mm] $i=1,\ldots,k-1$
[/mm]
und
[mm] $\sigma(x_k)=x_1$.
[/mm]
Veranschaulichung:
[mm] $x_1\mapsto x_2\mapsto x_3\mapsto\ldots\mapsto x_{k-1}\mapsto x_k\mapsto x_1$.
[/mm]
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 04:37 Sa 01.11.2014 | | Autor: | YuSul |
Danke.
Wenn ich mal ein Beispiel nehme:
[mm] $\{1,2,3,4,5\}$ [/mm] dann ist $n=5$ und [mm] $k\geq [/mm] 3$ ein möglicher Zyklus wäre dann
1,2,3,1,2,3 .... oder
1,3,2,1,3,2 usw. Zyklen der Länge 3.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:30 Sa 01.11.2014 | | Autor: | tobit09 |
> Wenn ich mal ein Beispiel nehme:
>
> [mm]\{1,2,3,4,5\}[/mm] dann ist [mm]n=5[/mm] und [mm]k\geq 3[/mm] ein möglicher
> Zyklus wäre dann
>
> 1,2,3,1,2,3 .... oder
>
> 1,3,2,1,3,2 usw. Zyklen der Länge 3.
Ich habe zwar nicht definiert, was ein Zyklus ist (sondern nur, wann eine Permutation einen Zyklus einer gewissen Länge hat).
Aber die Anschauung ist völlig richtig.
Etwa die Permutation
[mm] $\sigma\colon\Xi\to\Xi,\quad\sigma(i)=\begin{cases}2&\text{ für }n=1\\3&\text{ für }n=2\\1&\text{ für }n=3\\5&\text{ für }n=4\\4&\text{ für }n=5\end{cases}$
[/mm]
(Kurzschreibweise: [mm] \sigma=\pmat{1&2&3&4&5 \\ 2&3&1&5&4})
[/mm]
hat einen Zykel der Länge $3$ (und einen der Länge 2).
|
|
|
|
