Задача 8. Непересекающиеся отрезки

Четыре номера вместо двух отрезков

Два отрезка без общих точек на прямой не налегают друг на друга: один целиком левее другого. Поэтому выбор — это четыре номера $p_1 < p_2 < p_3 < p_4$ из $1, \ldots, 18$: левый отрезок $A_{p_1}A_{p_2}$, правый $A_{p_3}A_{p_4}$. И наоборот, четыре таких номера задают ровно один выбор (отрезки не упорядочены, но левый и правый не перепутать).

Условия задачи в этих номерах:

Первое и третье — длины отрезков, второе — у отрезков нет даже общего конца.

Сжатие

Считать четвёрки с разными ограничениями на разности неудобно; удобно, когда все разности просто не меньше $1$, то есть числа просто разные. Поэтому уберём «лишние» единицы: внутри каждого отрезка разность должна быть на $1$ больше, чем у соседних различных чисел. Положим

Тогда $q_2 - q_1 = p_2 - p_1 - 1 \geqslant 1$, $q_3 - q_2 = p_3 - p_2 \geqslant 1$, $q_4 - q_3 = p_4 - p_3 - 1 \geqslant 1$, то есть $q_1 < q_2 < q_3 < q_4$, причём $q_1 \geqslant 1$ и $q_4 = p_4 - 2 \leqslant 16$. Получились четыре разных числа от $1$ до $16$.

Сжатие можно отменить

Чтобы считать выборы через четвёрки $q$, нужно, чтобы разные выборы давали разные четвёрки и каждая четвёрка получалась. Это так: по любым $1 \leqslant q_1 < q_2 < q_3 < q_4 \leqslant 16$ восстанавливаем $p_1 = q_1$, $p_2 = q_2 + 1$, $p_3 = q_3 + 1$, $p_4 = q_4 + 2$ — все условия шага 1 выполнены, и $p_4 \leqslant 18$. Значит, выборов отрезков столько же, сколько способов выбрать $4$ точки из $16$.

Подсчёт и общая формула

То же рассуждение работает в общем случае: для $k$ отрезков длины не меньше $L$ на $n$ точках вычитаем по $L - 1$ на каждый отрезок, и получается $2k$ разных чисел от $1$ до $n - k(L - 1)$. Ответ $C_{n - k(L-1)}^{2k}$.