---
# System prepended metadata

title: Domácí úkol 6.1 - pinv

---

# 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í.
