# Domácí úkol 6.1 - pinv ## 1. Počet permutací Inverze se zde dá chápat tak, že levý prvek v permutaci $>$ pravý prvek v permutaci, přičemž i,j však značí pořadí prvku, nikoli jeho hodnotu. - $i = 1, \pi (i) = 2$: $j \in \{4\}, \pi (j) \in \{1\}$ - $i = 2, \pi (i) = 3$: $j \in \{4\}, \pi (j) \in \{1\}$ - $i = 3, \pi (i) = 9$: $j \in \{4,5,6,7,8,9\}, \pi (j) \in \{1,4,5,7,6,8\}$ ... - Dále již má inverzi pouze sedmička (tzn. $i = 7, j = 8, \pi (7) = 7, \pi (8) = 6)$ Celkový počet inverzí: $9$ Lze určit počet inverzí obecně? Zřejmě ne, protože ve vzestupně setříděné permutaci bude existovat 0 inverzí, ale v sestupné jich bude $\frac{n*(n-1)}{2}$. ## 2. Proč jsou inverze transitivní? Obecně jsme nalezli tyto dvě dvojice: $(i,j),(j,k)$. Platí, že $i<j \land j<k$, a tedy i $i<k$ (porovnávání je transitivní). Aby dané dvě dvojice mohly být v množině všech inverzí, musí platit, že $\pi (i)>\pi(j) \land \pi (j) > \pi(k)$. To ale znamená, že $\pi (i) > \pi (k).$ Dostáváme, že $i<k \land \pi(i)>\pi(k)$, takže dvojice $(i,k)$ bude také v množině všech inverzí.