Таблица инверсий — различия между версиями
| Строка 1: | Строка 1: | ||
| + | Пусть <tex> P = (p_1,p_2,\dots,p_n)</tex> является перестановкой чисел <tex> 1, 2,\dots, n</tex>. | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
| − | '''Инверсией''' в [[Действие перестановки на набор из элементов, представление в виде циклов|перестановке]] <math>\ | + | '''Инверсией''' в [[Действие перестановки на набор из элементов, представление в виде циклов|перестановке]] <math>\P</math> называется всякая пара индексов <tex>i, j</tex> такая, что <tex>1\leqslant i<j\leqslant n</tex> и <tex>\P[i]>\P[j]</tex>. |
}} | }} | ||
| − | + | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
'''Таблицей инверсий''' перестановки <tex> P </tex> называют такую последовательность <tex> T = (t_1,t_2,\dots,t_n)</tex>, в которой <tex>t_i</tex> равно числу элементов перестановки <tex> P </tex>, стоящих в <tex> P </tex> левее числа <tex>i</tex> и больших <tex>i</tex>. | '''Таблицей инверсий''' перестановки <tex> P </tex> называют такую последовательность <tex> T = (t_1,t_2,\dots,t_n)</tex>, в которой <tex>t_i</tex> равно числу элементов перестановки <tex> P </tex>, стоящих в <tex> P </tex> левее числа <tex>i</tex> и больших <tex>i</tex>. | ||
}} | }} | ||
Версия 21:42, 18 ноября 2010
Пусть является перестановкой чисел .
| Определение: |
| Инверсией в перестановке называется всякая пара индексов такая, что и . |
| Определение: |
| Таблицей инверсий перестановки называют такую последовательность , в которой равно числу элементов перестановки , стоящих в левее числа и больших . |
