#3 Биекции и кодирование объектов

Подмножеству \(A\) сопоставим строку \(a_1\ldots a_n\), где \(a_i=1\), если \(i\in A\), и \(a_i=0\), если \(i\notin A\). По такой строке однозначно восстанавливается \(A=\{i:a_i=1\}\). Значит, это биекция. Бинарных строк длины \(n\) ровно \(2^n\).

Каждый путь состоит ровно из \(5\) шагов \(R\) и \(4\) шагов \(U\). Последовательность шагов задаёт слово длины \(9\), и обратно любое такое слово задаёт путь. Поэтому путей \(\binom{9}{4}=126\).

Решение соответствует строке из \(10\) звёздочек и \(2\) перегородок: количества звёздочек в трёх промежутках равны \(x_1,x_2,x_3\). Обратно, любая такая строка даёт решение. Всего \(\binom{12}{2}=66\) строк.

Так как \(x_i\ge1\), положим \(y_i=x_i-1\ge0\). Тогда \(y_1+y_2+y_3+y_4=13\). По stars and bars число решений равно \(\binom{13+4-1}{4-1}=\binom{16}{3}=560\).

Каждому \(k\)-подмножеству \(A\subseteq[n]\) сопоставим \([n]\setminus A\). Оно имеет \(n-k\) элементов. Обратное отображение — снова взятие дополнения, поэтому это биекция.

Зафиксируем элемент \(a\). Каждому подмножеству \(S\) сопоставим \(S\triangle\{a\}\): если \(a\) был в \(S\), удаляем его, если не был — добавляем. Размер меняется на \(1\), значит чётность размера меняется. Операция обратна сама себе, поэтому это биекция между чётными и нечётными подмножествами.

Все \(k\)-подмножества множества \([n]\) делятся на два класса. Если подмножество не содержит \(n\), оно является \(k\)-подмножеством \([n-1]\): \(\binom{n-1}{k}\) вариантов. Если содержит \(n\), то остальные \(k-1\) элементов выбираются из \([n-1]\): \(\binom{n-1}{k-1}\) вариантов. Эти классы не пересекаются и покрывают все объекты.

Путь до \((3,2)\) содержит \(3\) шагов \(R\) и \(2\) шагов \(U\), таких путей \(\binom{5}{2}=10\). От \((3,2)\) до \((7,5)\) нужно \(4\) шага \(R\) и \(3\) шага \(U\), таких путей \(\binom{7}{3}=35\). Части выбираются независимо, поэтому ответ \(10\cdot35=350\).

Положим \(y_1=x_1-2\), \(y_2=x_2-4\), \(y_3=x_3\), \(y_4=x_4-5\). Тогда \(y_i\ge0\), а сумма равна \(30-2-4-5=19\). Число неотрицательных решений \(y_1+\cdots+y_4=19\) равно \(\binom{19+4-1}{3}=\binom{22}{3}=1540\).

Условие отсутствия соседних даёт \(a_{i+1}\ge a_i+2\). Тогда \(b_i=a_i-i+1\) образуют обычное \(5\)-подмножество множества \(\{1,\ldots,14\}\). Обратно, из \(b_1<\cdots

Разбиение не более чем на \(k\) частей изображается диаграммой с не более чем \(k\) строками. Транспонируем диаграмму: строки становятся столбцами. Теперь длина каждой строки не превосходит \(k\), то есть каждая часть нового разбиения не больше \(k\). Обратное преобразование — снова транспонирование, значит это биекция.

Запишем \(n\) единиц в ряд. Чтобы разбить их на \(k\) непустых групп, нужно выбрать \(k-1\) промежутков из \(n-1\) промежутков между соседними единицами и поставить там перегородки. Размеры групп и будут слагаемыми. Обратно, любая композиция задаёт такие перегородки. Ответ \(\binom{n-1}{k-1}\).

Всего путей \(\binom{2n}{n}\). Плохой путь впервые попадает выше диагонали шагом \(U\), в точку с \(y=x+1\). Отразим начальную часть до этого шага относительно прямой \(y=x+1\). Получается биекция плохих путей с путями из \((-1,1)\) в \((n,n)\), которых \(\binom{2n}{n-1}\). Значит, хороших путей

\[\binom{2n}{n}-\binom{2n}{n-1}=\frac{1}{n+1}\binom{2n}{n}.\]

Всего слов \(\binom{p+q}{q}\). Классическая отражательная биекция показывает, что число плохих слов равно \(\binom{p+q}{q-1}\): плохое слово впервые достигает равенства после начального преимущества \(A\), и отражение соответствующей начальной части меняет один \(A\) в лишний \(B\). Поэтому хороших слов

\[\binom{p+q}{q}-\binom{p+q}{q-1}=\frac{p-q}{p+q}\binom{p+q}{q}.\]

Возьмём открывающую скобку как шаг \(R\), закрывающую как шаг \(U\). В правильной скобочной последовательности в каждом префиксе открывающих скобок не меньше, чем закрывающих, то есть число \(U\) не превосходит числа \(R\). Это ровно условие \(y\le x\). Всего открывающих и закрывающих скобок по \(n\), значит путь идёт в \((n,n)\). Обратно, путь с \(y\le x\) даёт последовательность, в каждом префиксе которой открывающих не меньше закрывающих, то есть правильную скобочную последовательность.

Из разбиения на нечётные части сгруппируем одинаковые нечётные части \(q\). Если \(q\) встречается \(m\) раз, запишем \(m\) в двоичной системе: \(m=\sum 2^s\). Заменим эти \(m\) копий \(q\) на части \(2^s q\). Для каждого \(q\) получаются различные степени \(2^s q\), а для разных нечётных \(q\) части тоже различны. Получаем разбиение на различные части.

Обратно, каждую различную часть единственным образом записываем как \(2^s q\) с нечётным \(q\), и заменяем её на \(2^s\) копий \(q\). Это даёт разбиение на нечётные части. Две операции обратны.

Сумма считает чётные подмножества со знаком \(+\) и нечётные со знаком \(-\). Зафиксируем элемент \(1\). Отображение \(S\mapsto S\triangle\{1\}\) меняет чётность размера и является обратным самому себе. Значит, каждое чётное подмножество спарено с нечётным, и вклад пар сокращается. Сумма равна \(0\).

Из дерева строим последовательность длины \(n-2\): пока осталось больше двух вершин, удаляем лист с наименьшей меткой и записываем метку его соседа. Обратно, по последовательности \(c_1,\ldots,c_{n-2}\) восстанавливаем дерево: на каждом шаге берём наименьшую метку, которой нет в текущей последовательности, соединяем её с \(c_1\), затем удаляем эту метку из набора вершин и удаляем \(c_1\) из последовательности. В конце соединяем две оставшиеся вершины.

Эти процедуры обратны: удалённый на каждом шаге лист именно та наименьшая метка, которая больше не появится в коде. Поэтому деревья биективны последовательностям длины \(n-2\) над алфавитом из \(n\) меток. Таких последовательностей \(n^{n-2}\).

Фиксируем сторону многоугольника. В любой триангуляции есть единственный треугольник, прилегающий к этой стороне; его третья вершина делит многоугольник на две меньшие части. Аналогично правильная скобочная последовательность единственно записывается как \((A)B\), где \(A\) и \(B\) — правильные последовательности. Сопоставим третью вершину так, чтобы число пар в \(A\) равнялось числу треугольников в левой части, а \(B\) — в правой. Рекурсивно применяя то же правило, получаем взаимно однозначное соответствие. База \(n=0\) очевидна.

Всего путей \(\binom{a+b}{b}\). Плохой путь впервые нарушает условие шагом в точку на прямой \(y=x+1\). Отразим начальную часть до этого шага относительно прямой \(y=x+1\). Получится путь из \((-1,1)\) в \((a,b)\). Такой путь должен иметь \(a+1\) шагов \(R\) и \(b-1\) шагов \(U\), поэтому плохих путей \(\binom{a+b}{b-1}\). Следовательно, хороших путей

\[\binom{a+b}{b}-\binom{a+b}{b-1}=\frac{a-b+1}{a+1}\binom{a+b}{b}.\]