Inwersje w permutacjach liczb 1,2,...,n

[darlove]

Witam. Nie mam polskich czcionek, wiec z gory przepraszam. Zadanko jest proste. Niech bedzie dany ciag liczb \(\displaystyle{ a_1,a_2,\ldots,a_n}\) takich, ze sa one permutacja ciagu \(\displaystyle{ 1,2,\ldots,n}\). Oznaczmy \(\displaystyle{ [n] = \left\{1,2,\ldots,n\right\}}\). Inwersja nazywamy pare liczb \(\displaystyle{ (i,j)\in [n]\times[n]}\) taka, ze \(\displaystyle{ i<j \wedge a_i>a_j}\). Niech \(\displaystyle{ |\Delta_n|}\) bedzie liczba takich par w ciagu \(\displaystyle{ (a_i)_{i=1}^{n}}\), a \(\displaystyle{ \Delta_n}\) ich zbiorem. Przestawieniem nazywamy operacje przestawienia dwoch sasiednich wyrazow ciagu, to znaczy przestawiamy kolejne wyrazy miejscami, tzn. z ciagu \(\displaystyle{ \ldots,a_i,a_{i+1},\ldots}\), otrzymujemy ciag \(\displaystyle{ \ldots,a_{i+1},a_i\ldots}\). Trzeba pokazac, ze dla kazdej takiej permutacji prawdziwe jest twierdzenie, ze minimalna liczba przestawien potrzebna do tego, aby z danego ciagu otrzymac ciag \(\displaystyle{ 1,2,\ldots,n}\) wynosi dokladnie \(\displaystyle{ |\Delta_n|}\). Drugie twierdzenie do udowodnienia jest takie, ze jakkolwiek bedziemy przestawiac poczatkowy ciag w celu otrzymania ciagu docelowego, to zawsze liczba przestawien bedzie miala parzystosc minimalnej liczby przestawien. To znaczy, ze jesli mozna to wykonac w 5 przestawieniach (nieparzysta liczba przestawien), to NIE DA SIE TEGO WYKONAC w np. 6, albo 10, przestawieniach, bo 6 i 10 sa parzyste.

[norwimaj]

1. Przez indukcję po \(\displaystyle{ |\Delta_n|}\). Pokaż najpierw, że jeśli w permutacji istnieje inwersja, to istnieje inwersja sąsiednich elementów (czyli \(\displaystyle{ j=i+1}\)).