Anzahl Inversionen bei Produkt von Permutationen

11.06.2009, 21:49	Dunkit	Auf diesen Beitrag antworten »
Anzahl Inversionen bei Produkt von Permutationen Eine Frage aus der Informatik, aber denke ich in diesem Forum richtig aufgehoben. Als Grundlage wähle ich die Folge (1, 2, 3, ..., n). Wenn ich zwei Permutationen $\begin{eqnarray} \pi \end{eqnarray}$ und $\begin{eqnarray} \pi' \end{eqnarray}$ habe und dann das Produkt dieser Permutationen (ich nehme an das heißt ich wende zunächst die eine Permutation an und dann die andere?) betrachte, soll $\begin{eqnarray} inv(\pi \pi') \leq inv(\pi) + inv(\pi') \end{eqnarray}$ sein, wobei $\begin{eqnarray} inv(\pi) \end{eqnarray}$ die Anzahl der Inversionen von $\begin{eqnarray} \pi \end{eqnarray}$ ist. Ich bin mir nicht sicher, ob ich das direkt zeigen sollte, oder ob sich hier eine Induktion eignet?!
12.06.2009, 11:13	AD	Auf diesen Beitrag antworten »
Das kannst du direkt beweisen: $\begin{eqnarray} (i,j) \end{eqnarray}$ ist eine Inversion von $\begin{eqnarray} \pi\pi' \end{eqnarray}$ , falls $\begin{eqnarray} i<j \end{eqnarray}$ und $\begin{eqnarray} \pi'(\pi(i)) > \pi'(\pi(j)) \end{eqnarray}$ gilt. Daraus folgt nun, dass entweder $\begin{eqnarray} (i,j) \end{eqnarray}$ eine Inversion von $\begin{eqnarray} \pi \end{eqnarray}$ ist, oder aber andernfalls $\begin{eqnarray} (\pi(i),\pi(j)) \end{eqnarray}$ eine Inversion von $\begin{eqnarray} \pi' \end{eqnarray}$ ist...

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »