Пересечение отрезков и прямых

Пусть в каждом ряду по точек. Способ соединить точки можно задать перестановкой чисел, первая точка верхнего ряда соединяется с точкой под номером вторая — с и так далее. Значит, всего возможных рисунков будет

Теперь берём пару отрезков. Пусть это отрезки с концами и считаем В каком случае они пересекается? В том, когда Учитывая, что могут быть любой парой, замечаем следующее: общее количество пересечений отрезков равно количеству случаев, когда в перестановке большее число стоит раньше меньшего (не обязательно по соседству). Как сказали бы старшие товарищи, число пересечений равно числу инверсий в перестановке. Так и будем говорить дальше.

Например, — нет инверсий и нет пересечений, — одна инверсия ( и — инверсий ( и и и и и и Наибольшее количество инверсий будет, если написать числа задом наперёд: какие два числа не выбери — большее будет стоять раньше. То есть инверсий в последнем примере а в общем случае —

Как посчитать число перестановок с заданным количеством инверсий? Подойдём к задаче индуктивно. В фигурных скобках будем указывать различные перестановки, а в квадратных перечислим количества перестановок, имеющих соответственно инверсий.

Итак, единственный элемент можно расположить единственным образом, и у нас есть одна перестановка с нулевым числом инверсий.

Добавляем двойку — её можно добавить в начало и в конец имеющейся перестановки Одна из полученных перестановок будет без инверсий, другая — с одной инверсией.

Добавляем тройку — её мы можем поставить в любое место каждой из имеющихся перестановок. Тройка больше всех имевшихся ранее чисел, поэтому если поставить её на последнее место — новых инверсий не добавится, если поставить на предпоследнее (на второе) — добавится одна инверсия, а если на первое — будет плюс две инверии. Одна перестановка с нулём инверсий, две перестановки с одной, две перестановки с двумя, одна перестановка с тремя. То есть:

Так же будет происходить добавление нового числа в общем случае: число можно поставить на любое место, и в зависимости от места к инверсиям добавится штук. То есть на новом шаге перестановка с инверсиями превращается в перестановок с инверсиями соответственно.

Посмотрим, какие числа получались в квадратных скобках. Напишем эти последовательности одну под другой:

Здесь в строке (нумерация начинается с ) приводятся числа для равные количеству перестановок из чисел с инверсиями.

Вспоминая, как происходит добавление нового получим

Действительно, — количество перестановок из (n-1) чисел, в которых уже есть инверсий. В них мы вынуждены поставить новое на последнее место ( инверсий). Раз мы ставим на единственно возможное место, количество перестановок не изменится.

Далее, — количество перестановок с инверсией, и, чтобы добавить недостающую, мы вынуждены ставить на предпоследнее место ( инверсия).

Продолжаем так вплоть до потому что добавить больше инверсии нельзя. Всего получается слагаемых. Из других перестановок предыдущей строки мы ничего нового получить не сможем.

Заметим, что так как не бывает перестановок с отрицательным числом инверсий, как и не может быть перестановок со слишком большим (больше чем ) количеством инверсий.

Итак, имеем следующий способ построения коллекции

Первая строчка:

По строчке ползёт «окно» шириной Попавшие в «окно» числа складываются и выписываются в следующую (2-ю) строку:

Вторая строка:

По ней будет ползти окно шириной Сложение попавших в окно чисел даст третью строку:

По ней поползёт окно шириной и так далее, чтобы получить строку, нужно складывать стоящих подряд чисел предыдущей строки.

Выпишем (без нулей) первые строк нашей коллекции и выберем в ней нужное нам

Получаем ответ