Signum bestimmen < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:58 Do 13.01.2011 | | Autor: | Coup |
| Aufgabe | n>=1 , Für folgende Permutationen gilt es aus S2n das Signum zu bestimmen
[mm] \pmat{ 1 & 2&3&...&n&n+1&n+2&...&2n \\ 1 & 3 &5&...&2n-1&2&4&...&2n } [/mm] |
Hallo,
Ich habe in einigen Aufgaben zuvor das Signum bestimmen können.
Doch hier finde ich es leicht verwirrend.
Über Vollständige Induktion wollte ich jetzt nicht gehen.
Kann es sein das es hier n+1 Fehlstände gibt ?
Wenn nein..
Wie kann ich hier die Fehlstände bestimmen ?
lg
Florian
|
|
| |
|
Hallo Florian,
> n>=1 , Für folgende Permutationen gilt es aus S2n das
> Signum zu bestimmen
> [mm]\pmat{ 1 & 2&3&...&n&n+1&n+2&...&2n \\ 1 & 3 &5&...&2n-1&2&4&...&2n }[/mm]
>
>
> Hallo,
> Ich habe in einigen Aufgaben zuvor das Signum bestimmen
> können.
> Doch hier finde ich es leicht verwirrend.
> Über Vollständige Induktion wollte ich jetzt nicht
> gehen.
> Kann es sein das es hier n+1 Fehlstände gibt ?
Nein.
> Wenn nein..
> Wie kann ich hier die Fehlstände bestimmen ?
Wenn man die Darstellung etwas ändert wird es vielleicht klarer.
Die genannte Permutation nenne ich [mm] $\sigma$.
[/mm]
Es gilt:
[mm] $\sigma [/mm] (k) = [mm] \begin{cases}2k-1 & k \in \{1,\ldots,n\}\\2k-2n& k \in \{n+1,\ldots,2n\} \end{cases}$
[/mm]
Jetzt solltest Du die Definition eines Fehlstandes heranziehen und die relevanten Fälle für die Fehlstände $(i,j) [mm] \in \{1,\ldots,2n\}^2$ [/mm] betrachten.
> lg
> Florian
LG mathfunnel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:29 Sa 15.01.2011 | | Autor: | Coup |
Hi, danke schonmal für den Tipp. Doch irgendwie komme ich damit nicht weiter. Um das Sigma über die Anzahl der Fehlstände zu bestimmen konnte ich in der Vergangenheit solche ja ganz einfach abzählen und auswerten, grade/ungerade . Ich weis mit deinem Hinweis noch nicht umzugehen : / mag mir wer unter die arme greifen ?
|
|
|
| |
|
Hallo Florian!
> Hi, danke schonmal für den Tipp. Doch irgendwie komme ich
> damit nicht weiter. Um das Sigma über die Anzahl der
Du meinst wohl Signum statt Sigma.
> Fehlstände zu bestimmen konnte ich in der Vergangenheit
> solche ja ganz einfach abzählen und auswerten,
> grade/ungerade . Ich weis mit deinem Hinweis noch nicht
> umzugehen : / mag mir wer unter die arme greifen ?
Hier hängt es von $n$ ab, ob die Anzahl der Fehlstände gerade oder ungerade ist.
Betrachte die folgenden Fälle für $i < j$ (zwei Fälle liefern keine Fehlstände):
a) $i,j [mm] \in \{1,\ldots,n\}$
[/mm]
b) $i,j [mm] \in \{n+1,\ldots,2n\}$
[/mm]
c) $i [mm] \in \{1,\ldots,n\}$ [/mm] und $j [mm] \in \{n+1,\ldots,2n\}$
[/mm]
Wann gilt also [mm] $\sigma(i) [/mm] > [mm] \sigma(j)$ [/mm] in den jeweiligen Fällen?
Dann muss man noch ein bisschen die Tupel $(i,j)$, die Fehlstände sind zählen, um auf die Formel für die Anzahl der Fehlstände zu kommen.
LG mathfunnel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:38 So 16.01.2011 | | Autor: | Coup |
Also sich die untere Zeile anzuschauen sollte ja genügen. Zwischen den ungeraden und geraden Zahlen jeweils gibt es keine Fehlstände !
Also müssten nur die ungeraden mit den graden Zahlen verglichen werden..
Demnach sollten doch Fehlstände sein
1: 0 Fehlstände
3:32 1 Fehlstand
5:52,54 2 Fehlstände
7: 72,74,76 mit 3 Fehlständen
usw..
Doch wie drücke ich das als Formel aus ?lg
Flo
|
|
|
| |
|
Hallo Coup,
> Also sich die untere Zeile anzuschauen sollte ja genügen.
> Zwischen den ungeraden und geraden Zahlen jeweils gibt es
> keine Fehlstände !
> Also müssten nur die ungeraden mit den graden Zahlen
> verglichen werden..
> Demnach sollten doch Fehlstände sein
> 1: 0 Fehlstände
> 3:32 1 Fehlstand
> 5:52,54 2 Fehlstände
> 7: 72,74,76 mit 3 Fehlständen
> usw..
>
> Doch wie drücke ich das als Formel aus ?lg
Das sieht doch so aus,
als ob es für die Zahl 2k-1 genau k-1 Fehlstände gibt.
> Flo
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:34 So 16.01.2011 | | Autor: | Coup |
Also kann ich sagen das mein Signum k-1 ist ?
|
|
|
| |
|
Hallo Flo!
> Also kann ich sagen das mein Signum k-1 ist ?
Nein, für das Signum [mm] $\text{Sign}(\sigma)$ [/mm] gilt natürlich [mm] $\text{Sign}(\sigma) \in \{1,-1\}$.
[/mm]
In deiner vorherigen Antwort hast Du erkannt wie der Hase läuft, und MathePower hat die Formel $a(k)=(k-1)$ für die Anzahl $a(k)$ der Fehlstände der Form $(k,j)$ gegeben. Jetzt muss nur noch summiert werden:
Ich fasse mal zusammen:
[mm] $\sigma(k) [/mm] = [mm] \begin{cases}2k-1 & k \in \{1,\ldots,n\} \\
2k-2n& k \in \{n+1,\ldots,2n\} \end{cases}$
[/mm]
Ein Tupel [mm] $(i,j)\in \{1,\ldots,n\}\times \{n+1,\ldots,2n\}$
[/mm]
ist genau dann ein Fehlstand von [mm] $\sigma$, [/mm] wenn
[mm] $\sigma(i) [/mm] = 2i-1 > 2j-2n = [mm] \sigma(j)$ [/mm] (also, ganau dann, wenn $i > j-n$).
Hieraus ergibt sich $a(i) = i-1$.
Damit gilt für die Anzahl [mm] $a(\sigma)$ [/mm] der Fehlstände von [mm] $\sigma$:
[/mm]
[mm] $a(\sigma)=\sum\limits_{k=1}^n [/mm] a(k) = [mm] \sum\limits_{k=1}^n k-1=\sum\limits_{k=0}^{n-1} [/mm] k = [mm] \frac{n(n-1)}{2}$
[/mm]
und das gesuchte Ergebnis lautet:
[mm] $\text{Sign}(\sigma)= (-1)^{a(\sigma)}= (-1)^{\frac{n(n-1)}{2}}$
[/mm]
LG mathfunnel
|
|
|
|
