Ломоносов, 2023, 11 класс, задача 8

Ответ:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заметим, что сумма чисел в каждой строке равна (общее число перестановок).