Комбинаторика и рекурсия — это два взаимосвязанных инструмента, которые помогают считать количество вариантов и строить эффективные рассуждения в задачах по информатике. Именно они лежат в основе множества типичных заданий школьного курса и ЕГЭ: от подсчета паролей и кодов до анализа деревьев перебора и построения оптимальных алгоритмов. Комбинаторика отвечает на вопрос «сколько существует объектов, удовлетворяющих условиям», а рекурсия формулирует ответ через «как величина для n связана с меньшими значениями». Понимание этих идей формирует системное мышление: вместо грубого перебора мы используем правила счета и рекуррентные формулы, получая точный и проверяемый результат.

Основа комбинаторики — два базовых правила: принцип суммы и принцип произведения. Принцип суммы: если объект выбирается из нескольких непересекающихся множеств, то общее количество равно сумме чисел в каждом множестве. Пример: номерной знак формата либо А123ВС, либо А1234В (два разных шаблона). Сначала считаем варианты для первого шаблона, затем для второго, и складываем — потому что эти множества вариантов не пересекаются. Принцип произведения: если объект определяется последовательностью независимых выборов, то число вариантов равно произведению числа возможностей на каждом шаге. Пример: четырехсимвольный пароль из 26 заглавных букв и 10 цифр, при этом на каждой позиции можно ставить любой из 36 символов; итого 36 × 36 × 36 × 36. Важно прямо проговаривать «шаги» и проверять независимость выборов: если есть запреты (например, символы не повторяются), то число возможностей меняется на каждом шаге, и произведение будет иным.

Классические конструкции комбинаторики — перестановки, размещения и сочетания. Перестановки — это упорядоченные расстановки всех n различных элементов на n позициях; их число равно n! (произведение 1 × 2 × ... × n). Размещения без повторений из n по k — это упорядоченные k-длины последовательности из различных элементов множества, их число: n × (n − 1) × ... × (n − k + 1), то есть n! / (n − k)!. Сочетания без повторений из n по k — это выбор k элементов без учета порядка; их количество задают биномиальные коэффициенты, которые обозначаются C(n, k) и вычисляются как n! / (k! (n − k)!). Как отличать? Если порядок важен — используем перестановки или размещения; если порядок не важен — сочетания. Типичная стратегия решения: 1) определить, повторяются ли элементы, 2) важен ли порядок, 3) есть ли ограничения (например, запрет на соседние буквы). После этого выбрать соответствующую формулу и аккуратно расписать шаги.

Отдельный блок — подсчеты с повторениями. Размещения с повторениями из n по k — когда на k позициях можно использовать элементы из n-алфавита многократно; это классическая модель паролей: n в степени k. Перестановки с повторениями применимы, когда среди элементов есть одинаковые. Пример: сколько разных «слов» можно составить, переставив буквы слова МАТЕМАТИКА? Всего 10 букв, но символы повторяются: буква А встречается 3 раза, М — 2 раза, Т — 2 раза, остальные по одному. Формула: 10! / (3! 2! 2!). Логика проста: если бы все буквы были различны, получили бы 10! вариантов; но перестановки одинаковых букв не дают новых слов, поэтому делим на количество перестановок блоков одинаковых символов. Частая ошибка — забыть учесть все группы повторов. Для слов, где запрещены какие-то позиции (например, «буквы А не соседствуют»), удобны смешанные подходы: принцип включения-исключения, разбиение по случаям или рекуррентная формулировка по числу позиций.

Биномиальные коэффициенты C(n, k) обладают мощной структурой, отраженной в треугольнике Паскаля и в формуле бинома Ньютона. Важное рекурсивное свойство: C(n, k) = C(n − 1, k) + C(n − 1, k − 1) при k от 1 до n − 1, с базами C(n, 0) = 1 и C(n, n) = 1. Комбинаторный смысл таков: чтобы выбрать k элементов из n, рассмотрим один выделенный элемент; либо он не выбран (тогда осталось выбрать k из оставшихся n − 1), либо выбран (тогда добираем k − 1 из оставшихся n − 1). Пример для закрепления: C(5, 2) = 10. Интерпретация: количество пар учеников из пяти. Пересчеты на пальцах или через треугольник Паскаля помогают быстро проверить ответ и заметить типичные ошибки. Здесь впервые появляется естественная рекурсия: мы выражаем величину через меньшие значения — это мост между комбинаторикой и рекурсивной логикой алгоритмов.

Рекурсия в информатике — это способ определения объектов и функций через самих себя, но для меньшего размера. Любая корректная рекурсия имеет две части: база рекурсии (простые случаи, считаемые напрямую) и рекурсивный шаг (правило перехода от меньших значений к большим). Классические примеры: факториал n! можно определить как 0! = 1 и n! = n × (n − 1)! при n ≥ 1. Последовательность Фибоначчи задается базами F(0) = 0, F(1) = 1 и правилом F(n) = F(n − 1) + F(n − 2). Число перестановок n! тоже удобно понимать рекурсивно: чтобы построить перестановку из n элементов, возьмем перестановку из n − 1 элемента и вставим новый элемент во все возможные позиции — это и дает умножение на n. В задачах ЕГЭ часто требуется построить дерево вариантов и аккуратно просуммировать листья; правильнее оформить это как рекуррентную формулу, указав базу и переход, что экономит время и снижает риск ошибок.

Рекурсивные формулы особенно полезны, когда прямой учет блокируется сложными ограничениями. Пример: количество двоичных строк длины n без двух единиц подряд. Обозначим f(n) — число таких строк. Рассмотрим первый символ. Если он ноль, оставшаяся часть — любая допустимая строка длины n − 1 (f(n − 1) вариантов). Если он единица, следующий символ обязан быть нулем, а оставшаяся часть — любая допустимая строка длины n − 2 (f(n − 2) вариантов). Получаем рекуррентную формулу f(n) = f(n − 1) + f(n − 2). Базы: f(1) = 2 (строки 0, 1), f(2) = 3 (00, 01, 10). Дальше легко наращивать значения: 2, 3, 5, 8, 13, ... — известная последовательность Фибоначчи. Еще пример — плитка домино на доске 2×n: число раскладок g(n) также удовлетворяет g(n) = g(n − 1) + g(n − 2) при g(1) = 1, g(2) = 2. Такие задачи иллюстрируют типичный шаблон: разделить по первому шагу (или по положению левого края), выписать независимые случаи, сложить (принцип суммы), и получить рекурсию.

Рекурсию удобно связывать с динамическим программированием — это та же рекурсия, но с запоминанием промежуточных значений, чтобы не пересчитывать одно и то же. Это критично для рекурсий вида F(n) = F(n − 1) + F(n − 2), где наивная реализация порождает экспоненциальное дерево вызовов. В комбинаторике такой подход применяется к биномиальным коэффициентам, числу путей на решетке с препятствиями, количеству слов с ограничениями. Мы создаем таблицу, задаем базовые значения, затем заполняем по рекуррентному правилу слева направо или сверху вниз. Такой метод прозрачен и легко проверяется: достаточно сверить несколько ячеек и проследить логику переходов. Когда нужно не просто посчитать число, но и перечислить решения (например, все перестановки), применяют рекурсивный перебор с возвратом (backtracking) — строим решение по позиции, пробуем допустимые варианты, при нарушении условий возвращаемся и пробуем следующий. Важно уметь заранее выделить критерии отсечения, чтобы резко уменьшить дерево перебора.

Рассмотрим типичные ошибки и приемы самопроверки. Во-первых, путаница «учитывается порядок или нет». Если порядок важен, нельзя использовать сочетания; если не важен, нужно делить на число перестановок. Во-вторых, неправильное применение принципа произведения при зависимых этапах: если предметы не возвращаются, то множители уменьшаются. В-третьих, забытые ограничения: соседние символы, запреты на первую позицию, минимальное число цифр и т. п. В-четвертых, неверно заданные базы рекурсии: забыли нулевую длину или единичный случай — и все последующие значения сдвигаются. Хорошая привычка — проверять результат на малых n. Если ответ для n = 1 или n = 2 очевиден, ваши формулы обязаны воспроизвести его. Дополнительно используйте независимые способы проверки: пересчитайте через треугольник Паскаля, через альтернативное разбиение по случаям или через маленькое ручное дерево вариантов.

Пошаговая методика решения комбинаторных задач, оптимизированная под формат ЕГЭ и олимпиадных тренировок, выглядит так:

• Шаг 1. Перевод условия на язык множеств. Что выбираем? Из какого алфавита? Какая длина? Есть ли запреты на позиции, повторы, соседства?
• Шаг 2. Определение модели. Перестановки, размещения, сочетания; с повторами или без; или более сложная структура с ограничениями, требующая рекурсивной формулы.
• Шаг 3. Разбиение на случаи. По первому символу, по числу определенных элементов, по позиции ограничения; случаи должны быть непересекающимися (для принципа суммы).
• Шаг 4. Применение принципа произведения. На каждом шаге перечислить, сколько вариантов выбора доступно; аккуратно менять множители при запретах и невозвратах.
• Шаг 5. Фиксация баз и рекуррентного перехода. Если составлена рекурсия, ясно выписать базовые значения и формулу; для динамики — схему заполнения таблицы.
• Шаг 6. Проверка на малых размерах и альтернативная оценка. Сверить с известными примерами, простыми переборами, треугольником Паскаля, формулой C(n, k).
• Шаг 7. Интерпретация ответа. Убедиться, что единицы измерения корректны, нет дробных результатов там, где их быть не может, и нет противоречий ограничениям.

Применим методику на коротких примерах. Пример 1: Сколько четырехзначных чисел без повторяющихся цифр и не начинающихся с нуля? Шаги: первая позиция — 9 вариантов (1–9), вторая — 9 (все, кроме уже выбранной и нуля, если не использован), точнее лучше считать последовательно: после выбора первой цифры 9 вариантов остаются для второй (0 допустим, если не использован ранее), затем 8 для третьей, 7 для четвертой; итог: 9 × 9 × 8 × 7. Пример 2: Сколько слов длины 5 из букв A, B, C без подряд идущих одинаковых? Рекурсия: обозначим h(n) — число слов длины n. Первый символ выбирается тремя способами, далее каждый следующий — двумя (все, кроме повторения). Итого прямой подход дает 3 × 2^(n − 1) и проверки не требует рекурсии. Но если добавим условие «не более двух одинаковых подряд», тогда разумнее завести рекурсию с состояниями: количество строк, оканчивающихся на одиночную букву, и количество строк, оканчивающихся на пару одинаковых символов. Это пример, где автоматы состояний и динамика по состояниям упрощают задачу.

Полезно видеть, как комбинаторика порождает красивые числовые последовательности. Помимо биномиальных коэффициентов и чисел Фибоначчи часто встречаются числа Каталана — они считают количество правильных скобочных последовательностей, способов разбить многоугольник диагоналями на треугольники и мн. др. Их можно определить рекурсией: Catalan(0) = 1, Catalan(n) = сумма по i от 0 до n − 1 Catalan(i) × Catalan(n − 1 − i). Похожим образом вводятся числа Стирлинга второго рода — количество разбиений множества на k непустых подмножеств, они подчиняются рекурсии S(n, k) = S(n − 1, k − 1) + k × S(n − 1, k). Важно не столько запомнить формулы, сколько понять логику: каждый объект рождается из меньшего объекта плюс ясный закон добавления нового элемента. Это и есть «душа» рекурсии в комбинаторике.

Связь с вероятностью возникает естественно: многие вероятностные задачи сводятся к подсчету отношений «благоприятные исходы» к «всего исходов», а «всего исходов» часто считают через размещения и сочетания. Например, вероятность вытащить из колоды 5 карт без тузов — это C(48, 5) / C(52, 5). Если добавляются ограничения (например, «не менее двух тузов»), удобно использовать разбиение по числу тузов и сумму соответствующих сочетаний. Здесь снова работают и принцип суммы, и сочетания, и проверка через маленькие n.

Подводя итог, отметим ключевые ориентиры. В комбинаторике важны четкие вопросы: «существуют ли повторы», «важен ли порядок», «как влияют ограничения на шаги выбора». В рекурсии важны правильно заданные базы и честный рекурсивный переход. Многие сложные на вид задачи разрушаются на простые случаи, и вместо изнурительного полного перебора вы строите стройную формулу или лаконичную рекурсию. Чем точнее вы формализуете условия, тем проще становится решение. Тренируйтесь переводить слова задачи в комбинаторные модели, рисовать дерево вариантов, выбирать между прямой формулой и рекурсией/динамикой, и обязательно проверяйте себя на простых примерах. Это и есть профессиональный подход, который одинаково востребован и в школьных заданиях, и в реальном программировании.