E2 Биекция и инъекция

Идея метода: чтобы посчитать количество объектов в трудном множестве $A$, иногда удобно найти другое множество $B$, которое устроено проще, и установить взаимно однозначное соответствие (биекцию) между $A$ и $B$. Тогда $|A| = |B|$, и считать нужно уже $B$.

Метод состоит в том, что мы конструируем отображение $f: A \to B$ и доказываем, что оно биективно (каждый элемент $B$ получается ровно от одного элемента $A$). Если нужно только доказать $|A| \leq |B|$, достаточно инъекции — отображения, при котором разные элементы $A$ переходят в разные элементы $B$.

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

Метод особенно мощен, когда прямой подсчёт множества $A$ сложен (нет удобной формулы), но можно заметить, что объекты $A$ кодируются объектами из привычного множества $B$ (слова, пути в сетке, подмножества). Нестандартные биекции — одни из самых элегантных ходов в олимпиадной математике.

• Принцип биекции: $|A| = |B|$ тогда и только тогда, когда существует биекция $f: A \to B$. Условие: $A$ и $B$ — конечные множества. Когда использовать: когда $|B|$ легко считается, а $|A|$ — нет.

• Принцип инъекции (≤): если существует инъекция $f: A \hookrightarrow B$, то $|A| \leq |B|$. Когда использовать: чтобы оценить мощность сверху.

• Принцип сюръекции (≥): если существует сюръекция $f: A \twoheadrightarrow B$, то $|A| \geq |B|$. Когда использовать: чтобы оценить мощность снизу.

• Биекция «шары в ящики»: число способов разложить $n$ неразличимых шаров по $k$ различимым ящикам (ящики могут быть пустыми) равно $\binom{n+k-1}{k-1}$. Доказательство через биекцию: кодируем раскладку последовательностью из $n$ единиц и $k-1$ нулей.

• Кодирование двоичными словами: каждому объекту из $A$ сопоставить последовательность 0 и 1 длины $n$, описывающую его структуру.
• Кодирование путями в сетке: объектам $A$ сопоставить пути из одной точки сетки в другую (шаги «вправо» и «вверх»), затем посчитать пути биномиальным коэффициентом.
• «Звёзды и палки» (stars and bars): число решений $x_1 + x_2 + \ldots + x_k = n$ в неотрицательных целых = число способов поставить $k-1$ разделитель среди $n$ единиц = $\binom{n+k-1}{k-1}$.
• Дополнение и симметрия: построить биекцию «объект ↔ дополнение» или использовать симметрию множества (отражение, циклический сдвиг).
• Проверка биективности: явно описать обратное отображение $f^{-1}$ и убедиться, что $f \circ f^{-1} = \mathrm{id}$.

Поверхностные признаки (что буквально написано):
- «Докажите, что число ... равно числу ...».
- «Найдите число натуральных решений уравнения $x_1 + x_2 + \ldots = n$».
- «Сколько способов расставить / разбить / выбрать...» при неразличимых объектах.

Структурные признаки (форма выражения, объекты):
- Два разных на вид множества, которые «вдруг» оказываются одинакового размера.
- Объекты с естественным «кодированием»: последовательности, разбиения, пути.

Цель задачи (что от тебя хотят):
- Доказать равенство двух комбинаторных чисел без прямого вычисления обоих.
- Найти число решений уравнения с натуральными/неотрицательными переменными.

Задача 1. Докажите, что число способов выбрать $k$ элементов из $\{1, 2, \ldots, n\}$ с повторениями равно $\binom{n+k-1}{k}$.

Источник: классическая комбинаторика (стандартный тип ВсОШ заключительного)

Как думать (рассуждение ученика$):
1. $Что я вижу? Выборка с повторениями — нет очевидной формулы.$2. *$Метод: биекция. Нужно найти более знакомое множество того же размера.$3. *$Первый ход: закодируем каждую мультимножество $\{a_1 \leq a_2 \leq \ldots \leq a_k\}$ последовательностью нулей и единиц.$4. *$Ключевая идея:* замена $b_i = a_i + i - 1$ даёт строго возрастающую последовательность $1 \leq b_1 < b_2 < \ldots < b_k \leq n+k-1$, то есть $(k)$-элементное подмножество $\{1, \ldots, n+k-1\}$. Это биекция!

Решение:
Определим отображение: мультимножеству $\{a_1 \leq \ldots \leq a_k\} \subseteq \{1,\ldots,n\}$ сопоставим подмножество $\{a_1, a_2+1, a_3+2, \ldots, a_k+k-1\} \subseteq \{1,\ldots,n+k-1\}$. Это подмножество строго возрастающее (и значит, $k$-элементное). Обратное отображение: $k$-элементному подмножеству $\{b_1 < \ldots < b_k\}$ сопоставим $\{b_1, b_2-1, \ldots, b_k-k+1\}$ — нестрого возрастающая последовательность из $\{1,\ldots,n\}$. Биекция установлена, поэтому количество мультимножеств $= \binom{n+k-1}{k}$.

Ответ: $\binom{n+k-1}{k}$.

Что в этой задаче было главным: замена переменных $b_i = a_i + i - 1$ превратила нестрогое возрастание в строгое — это классический «сдвиговый» трюк биекции.

Задача 2. Найдите число решений уравнения $x + y + z = 10$ в натуральных числах ($x, y, z \geq 1$).

Источник: тренировочная (типичная задача на «stars and bars»)

Как думать (рассуждение ученика$):
1. $Что я вижу? Уравнение в натуральных числах — сразу думаю про «шары в ящики».$2. *$Метод: биекция через «звёзды и палки».$3. *$Первый ход: делаю замену $x' = x-1, y' = y-1, z' = z-1$, тогда $x' + y' + z' = 7$, $x',y',z' \geq 0$.$4. *$Ключевая идея:* число неотрицательных решений $x'+y'+z'=7$ равно числу способов расставить 2 разделителя среди 7 единиц = $\binom{9}{2} = 36$.

Решение:
Замена $x' = x-1 \geq 0$: задача сводится к числу неотрицательных целых решений $x'+y'+z'=7$. По методу «звёзд и палок» это $\binom{7+2}{2} = \binom{9}{2} = 36$.

Ответ: 36.

Что в этой задаче было главным: замена переменных (сдвиг) свела задачу к стандартной биекции со «звёздами и палками».

• Ошибка: утверждать биекцию, не проверив, что отображение сюръективно (каждый элемент $B$ достигается). → Почему неверно: отображение может быть инъективным, но не сюръективным. → Как избежать: явно описать обратное отображение.

• Ошибка: путать «выборку с повторениями» и «выборку без повторений» при применении формулы. → Почему неверно: формулы $\binom{n}{k}$ и $\binom{n+k-1}{k}$ дают разные ответы. → Как избежать: явно проверить, разрешены ли повторения в условии.

• Ошибка: применить замену «$b_i = a_i + i$» вместо «$b_i = a_i + i - 1$», сдвинув диапазон не туда. → Как избежать: проверить крайние случаи: при $a_1 = \ldots = a_k = 1$ что получается?

• Ошибка: в задаче «шары в ящики» забыть, что ящики различимы (или наоборот, считать неразличимые различимыми). → Как избежать: явно уточнить в условии, различимы ли объекты.