ИНВЕРСИЯ

в комбинаторике, беспорядок, - перестановка из пэлементов, в к-рой элемент iне может занимать i-ю позицию, i=1, 2, . . ., п. Задача подсчета числа D_n инверсий известна как "задача о встречах". Справедлива следующая формула:

И.- частный случай перестановок, удовлетворяющих заданным ограничениям на позиции переставляемых элементов. Напр., известная задача "о супружеских парах" состоит в подсчете числа перестановок U_n, противоречивых двум перестановкам: (1, 2, . . ., п)и (га, 1, 2, . . ., п- 1). (Две перестановки из пэлементов противоречивы, если j-й элемент, i=l,2,...,n, занимает в них разные позиции.) Числа U_n вычисляются по формуле:

Через D_n и U_n подсчитываемая число L(r, п) латинских прямоугольников размера rп при r=2,3, а именно

Лит.:[1] Райзер Г. Дж., Комбинаторная математика, пер. с англ., М., 1966; [2] Риордан Дж., Введение в комбинаторный анализ, пер. с англ., М., 1963.

В. М. Михеев.