Każda transpozycja jest nieparzytsa

[yorgin]

Ok, łopatologicznie, jak za przeproszeniem dla idioty (wszystko to tylko definicje, które powinny być znane!)

Transpozycja \(\displaystyle{ (i,j)}\) to odwzorowanie bijektywne \(\displaystyle{ f:\{1,\ldots, n\}\to \{1,\ldots, n\}}\) takie, że

\(\displaystyle{ f(i)=j, \qquad f(j)=i, \qquad f(k)=k, k\neq i \wedge k\neq j}\)

[myszka9]

Wiem to, ale mi chodzi o powiązanie z inwersją.

[yorgin]

To ja Cię prosiłem o porównanie definicji transpozycji i inwersji. 2 godziny temu. Dostrzeżenie pewnych podobieństw. Jak widać straciłem czas...

[myszka9]

Inwersje w podanym "przykładzie"

\(\displaystyle{ (i,j),(i,i+1),...,(i,j-1),(i+1,j),...,(j-1,j)}\) , skąd mam pewność, że będzie ich nieparzysta ilość? O to mi chodzi.

Nie tracisz czasu, pomagasz mi, może tego nie odczuwasz, ale pomagasz.

[yorgin]

Inwersje w podanym "przykładzie"

\(\displaystyle{ (i,j),(i,i+1),...,(i,j-1),(i+1,j),...,(j-1,j)}\)

Nie rozumiem tego zapisu.

[myszka9]

\(\displaystyle{ I(f) = \{(i,j),(i,i+1),...,(i,j-1),(i+1,j),...,(j-1,j)\}}\)

Może tak lepiej?

Wpadłam na taki pomysł..
Korzystając z def transpozycji :

1)Ilość inwersji, gdy \(\displaystyle{ j-i +1\in Par}\)

Od \(\displaystyle{ i+1}\) do \(\displaystyle{ j-1}\) ilość inwersji \(\displaystyle{ \in NPar}\)

\(\displaystyle{ Par+NPar = NPar}\)

2)Ilość inwersji, gdy \(\displaystyle{ j-i +1\in NPar}\)

Od \(\displaystyle{ i+1}\) do \(\displaystyle{ j-1}\) ilość inwersji \(\displaystyle{ \in Par}\)

\(\displaystyle{ NPar+Par=NPar}\)

NPar - liczby nieparzyste
Par - liczby parzyste

Dodaję 1 , bo chodzi o dł przedziału.
Heh, pewnie załamiesz się tym dowodem , ale jakoś bardziej widzę w ten sposób znak tej permutacji.

[yorgin]

Powiem Ci, że coś jest w tym, co napisałaś. W zasadzie parzystości i nieparzystości to dobre podejście. Ja bym robił to tak samo. Oczywiście zakładając, że inwersja polega na zamianie dwóch sąsiednich elementów permutacji. Bo czasem można niesąsiadujące zamienić.

Przy rozumieniu jako zamianie sąsiadujących zamian jest:

\(\displaystyle{ j-i}\) na sprowadzenie \(\displaystyle{ i}\) na miejsce \(\displaystyle{ j}\).

\(\displaystyle{ j-i-1}\) na sprowadzenie \(\displaystyle{ j}\) z miejsca \(\displaystyle{ j-1}\) na \(\displaystyle{ i}\).