Ψ Die Informatikseite

Menü
Informatik » Bachelor » Lineare Algebra » Permutationen » Fehlstellen
Anzahl der möglichen Permutationen Permutationen

Fehlstellen

Wenn die Permutation eine kleinere Stelle nach einer größeren Stelle abbildet, werden Fehlstellen erzeugt. Ist $j<k$ und $\sigma(k)<\sigma(j)$, so handelt es sich um eine Fehlstelle.
Z.B. hat eine Transposition $(ab)$ eine Fehlstelle, da $b>a$ und $\{a,b\}\mapsto\{b,a\}$ gilt. $a$, steht zu $b$ fehl.
oder $\displaystyle\left(\begin {array}{c}1\\ 3\\ \end {array}\begin {array}{c}2\\ 2\\ \end {array}\begin {array}{c}3\\ 1\\ \end {array}\right)=(13)$:
$3$ steht vor $2$,
$3$ steht vor $1$,
$2$ steht vor $1$.
$\Rightarrow$ 3 Fehlstellen $\Rightarrow sign(\sigma)=-1$.
Hat nun eine Permutation gerade viel Fehlstellen, so ist $sign(\sigma)=1$, andernfalls $-1$. Das Signum kann man mit folgender Formel bestimmen:

\begin{displaymath}sign(\sigma)=\prod_{j<k}\frac{k-j}{\sigma(k)-\sigma(j)}\end{displaymath}


Anzahl der möglichen Permutationen Permutationen