Математическая энциклопедия - инверсия

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

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

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

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

В. М. Михеев.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985