Počet inverzí v permutaci
Inverze v kombinatorice je počet párů prvků, ve kterých má další položka menší číslo než předchozí. Někdy je důležité kvantifikovat stupeň rozlišování libovolné permutace od lexigraficky nejmenšího počtu porušení rostoucího řádu hodnot jejích prvků. Každý pár prvků, kde dochází k takovému porušení jejich vzájemné pozice v permutaci, se nazývá inverze.
.Inverze permutací
Pro kompaktní zápis inverze na prvky permutace se používá vektor inverze (V1,…Vj,…Vn) a tabulka inverzí (W1,…Wj,…Wn). Tyto obě formy záznamu identifikují čísla inverze pro všechny položky permutace.
Složení vektoru a inverzních tabulek pro digitální permutace P=(5,9,1,8,2,6,4,7,3) ukazuje se v následujícím příkladu, kde jsou pro přehlednost indexovány pozice všech prvků:
| j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | pj | 5 | 9 | 1 | 8 | 2 | 6 | 4 | 7 | 3 | Vj | 0 | 0 | 2 | 1 | 3 | 2 | 4 | 2 | 6 | Wj | 2 | 3 | 6 | 4 | 0 | 2 | 2 | 1 | 9 |
Konkrétně v tomto příkladu V8=2, protože vlevo od prvku P8=7 V přeskupení jsou 2 prvky P2=9 a P4=8 s větší hodnotou než 7. Na druhé straně, W8=1, protože vlevo od položky s hodnotou 8 (to P4)permutace obsahuje pouze 1 prvek (P2=9),hodnota, která je větší než 8. Stejně tak můžete v tomto příkladu zdůvodnit výběr hodnot ostatních složek vektoru a tabulky inverzí. Je také třeba poznamenat, že pro jakékoli permutace jsou hodnoty součástí vektoru a inverzních tabulek spojeny následujícími poměry:
V1 = Wn = 0; Vj = Wi | i = Pj; Wj = Vi | Pi = j.
Při návratu k integračním odhadům je třeba poznamenat, že součet hodnot všech složek vektoru nebo tabulky inverzí určuje celkový počet inverzí i permutací. Konkrétně pro uvažovaný příklad se rovná 20:
I(5, 9, 1, 8, 2, 6, 4, 7, 3) = 20.