Как найти число инверсий в перестановке

Определение 1. Количество инверсий (беспорядка) в перестановке – это количество пар элементов (не обязательно соседних), в которых следующий элемент имеет меньший номер, чем предыдущий.
 

Пример 1.6. Найти количество инверсий в перестановке
(2, 3, 1, 6, 4, 5, 7).

Решение. ... Смотреть решение »

Правило сложения (принцип сложения, правило "или"):

Если элемент A можно выбрать из некоторого множества m способами, а другой элемент B – n способами, причем выборы А и В таковы, что взаимно исключают друг друга и не могут быть выбраны одновременно, то выбор какого-либо одного из этих элементов ( А или В) можно осуществить (m+n) способами.

Поясним на простом примере:  ... Смотреть решение »

Правило умножения

Одним из основных правил комбинаторики применяемых для решения комбинаторных задач является правило умножения.

Правило умножения  (принцип умножения, правило "и"): 

пусть имеется две группы элементов,

если  элемент из первой группы можно выбрать k₁ способами,

после чего элемент из второй группы – k₂ способами,

то общее число комбинаций N из двух элементов будет

N = ... Смотреть решение »