proszę o pomoc przy obliczeniu inwersji w permutacjach, tylko tak krok po kroku bardzo proszę
a) (2,1,4,3,6,5,...,2n,2n-1)
b) (n,n-1,n-2,...,k,1,2,...,k-1) dla n>k
oblicz liczbę inwersji w permutacjach
-
beciaaa1990
- Użytkownik
- Posty: 2
- Rejestracja: 26 paź 2009, o 15:59
- Płeć: Kobieta
- Lokalizacja: Wałbrzych
oblicz liczbę inwersji w permutacjach
nie znam się na tym, ale z tego co zrozumiałam na ćwiczeniach to:
a) jest to permutacja liczb od 1 do 2n, gdzie poprzestawiane zostały kolejne pary liczb, z których to liczb pierwsza tworzy 1 inwersję a kolejna 0 inwersji, czyli 2 tworzy 1, 1-> 0, 4 ->1, 3-> 0 i tak aż do 2n, które tworzy 1 inwersję, a 2n-1 tworzy 0 inwersji
wydaje mi się (ale nie bierz tego za pewnik), że skoro liczb jest 2n, a inwersję tworzy tylko połowa z nich to liczba inwersji wynosi n
b) jest to permutacja liczb od 1 do n, gdzie są jakby dwa uporządkowane zbiory (jeśli można tak w ogóle powiedzieć). Pierwszy: n,n-1,n-2,...,k, i drugi: 1,2,...,k-1 (gdzie liczb jest k-1, a każda z nich tworzy 0 inwersji)
no i w tym momencie dobijam do granic mojego pojmowania, więc nie wiem jak wyjaśnić liczbę inwersji w "pierwszym zbiorze"
pewnym jest, że gdy już ustali się tę liczbę (czego Ci i sobie życzę), trzeba skorzystać ze wzroru
\(\displaystyle{ S _{n}= \frac{a _{1}+a _{n} }{2} \cdot n}\)
a) jest to permutacja liczb od 1 do 2n, gdzie poprzestawiane zostały kolejne pary liczb, z których to liczb pierwsza tworzy 1 inwersję a kolejna 0 inwersji, czyli 2 tworzy 1, 1-> 0, 4 ->1, 3-> 0 i tak aż do 2n, które tworzy 1 inwersję, a 2n-1 tworzy 0 inwersji
wydaje mi się (ale nie bierz tego za pewnik), że skoro liczb jest 2n, a inwersję tworzy tylko połowa z nich to liczba inwersji wynosi n
b) jest to permutacja liczb od 1 do n, gdzie są jakby dwa uporządkowane zbiory (jeśli można tak w ogóle powiedzieć). Pierwszy: n,n-1,n-2,...,k, i drugi: 1,2,...,k-1 (gdzie liczb jest k-1, a każda z nich tworzy 0 inwersji)
no i w tym momencie dobijam do granic mojego pojmowania, więc nie wiem jak wyjaśnić liczbę inwersji w "pierwszym zbiorze"
pewnym jest, że gdy już ustali się tę liczbę (czego Ci i sobie życzę), trzeba skorzystać ze wzroru
\(\displaystyle{ S _{n}= \frac{a _{1}+a _{n} }{2} \cdot n}\)