Таблица инверсий

Пусть [math] P = (p_1,p_2,\dots,p_n)[/math] является перестановкой чисел [math] 1, 2,\dots, n[/math].

Определение:

Инверсией в перестановке [math]P[/math] называется всякая пара индексов [math]i, j[/math] такая, что [math]1\leqslant i\lt j\leqslant n[/math] и [math]P[i]\gt P[j][/math].

Определение:

Таблицей инверсий перестановки [math] P [/math] называют такую последовательность [math] T = (t_1,t_2,\dots,t_n)[/math], в которой [math]t_i[/math] равно числу элементов перестановки [math] P [/math], стоящих в [math] P [/math] левее числа [math]i[/math] и больших [math]i[/math].