Комбинаторика

Комбинаторика — раздел математики, изучающий способы выбора и расположения элементов множества. Отвечает на вопросы: сколько способов выбрать k объектов из n? В каком порядке можно расставить элементы?

Сколько способов перемешать колоду из 52 карт? 52! ≈ 8×10⁶⁷ — больше атомов в Млечном Пути. Вероятность дважды получить одинаковую раскладку практически нулевая. Комбинаторика считает невозможное — варианты, которые никогда не перебрать вручную.

Почему подсчёт вариантов изменил мир

Древние знали перестановки интуитивно — санскритские поэты в V веке считали метрические схемы стихов. Но строгая теория началась с азартных игр. Блез Паскаль и Пьер де Ферма в 1654 году решали задачу о разделе ставки — если игру прервали, кому сколько?

Паскаль построил треугольник биномиальных коэффициентов: каждое число — сумма двух верхних. Строка n даёт коэффициенты (a+b)ⁿ. Например, (a+b)³ = a³ + 3a²b + 3ab² + b³ — числа 1, 3, 3, 1 из третьей строки. Простая схема породила теорию вероятностей.

На практике комбинаторика решает задачи безопасности. Сколько паролей из 8 символов? Если брать только цифры — 10⁸ = 100 млн (взломают за минуты). Добавить буквы и знаки — 95⁸ ≈ 6×10¹⁵ вариантов (годы перебора). Каждый дополнительный символ умножает стойкость в 95 раз.

Три кита комбинаторики

Перестановки (permutations) — порядок важен. Сколько способов рассадить 5 человек на 5 стульев? P(5) = 5! = 120. Факториал растёт безумно быстро: 10! = 3,6 млн, 20! = 2,4×10¹⁸. Задача коммивояжёра для 20 городов имеет (20-1)!/2 ≈ 1,2×10¹⁷ маршрутов — перебрать невозможно.

Размещения (arrangements) — выбор k из n с учётом порядка. Сколько способов выбрать председателя и секретаря из 10 человек? A(10,2) = 10×9 = 90. Формула: A(n,k) = n!/(n-k)!. Пароль из 4 разных цифр — A(10,4) = 5040 вариантов. Если цифры могут повторяться — 10⁴ = 10000 (это размещения с повторениями).

Сочетания (combinations) — порядок не важен. Сколько способов выбрать 5 карт из 52? C(52,5) = 52!/(5!×47!) = 2,6 млн. Биномиальный коэффициент C(n,k) = n!/[k!(n-k)!] встречается везде: в вероятности, статистике, генетике (число генотипов), квантовой механике (состояния фермионов).

Принципы, которые упрощают подсчёт

Правило произведения: если событие A происходит m способами, а B — n способами, вместе — m×n. Пример: 5 рубашек и 3 галстука дают 5×3 = 15 комбинаций. Кажется тривиально, но это основа всех формул комбинаторики.

Принцип включения-исключения (ПВВ) считает пересекающиеся множества. Сколько чисел от 1 до 100 делятся на 2 или 3? |A ∪ B| = |A| + |B| - |A ∩ B| = 50 + 33 - 16 = 67. Для трёх множеств формула усложняется, для n — становится рекурсией. Применяется в теории вероятностей (формула полной вероятности) и комбинаторной оптимизации.

Метод производящих функций кодирует последовательности в степенные ряды. Количество разбиений числа n (способов представить как сумму натуральных) не имеет простой формулы, но производящая функция даёт рекуррентное соотношение. Эйлер использовал это в теории чисел.

От карт до квантовых компьютеров

Комбинаторика долго считалась развлечением математиков. Эйлер решал задачу о кёнигсбергских мостах (1736) — можно ли пройти все 7 мостов ровно по разу? Ответ: нет (граф не эйлеров). Это породило теорию графов, но казалось оторванным от жизни.

XX век всё изменил. Криптография RSA (1977) поставила безопасность интернета на факторизацию больших чисел — задачу комбинаторной сложности. Число способов разложить 2048-битное число на множители астрономическое, перебор займёт миллиарды лет.

Квантовые компьютеры атакуют комбинаторику. Алгоритм Шора (1994) разлагает числа за полиномиальное время — RSA под угрозой. Но квантовая криптография (распределение ключей через запутанные фотоны) снова использует комбинаторику — число квантовых состояний растёт экспоненциально.

Где комбинаторика работает сегодня

Генетика — число генотипов для n генов с двумя аллелями каждый: 3ⁿ (AA, Aa, aa). Для 10 генов — 59 тысяч вариантов. Биоинформатика анализирует комбинаторные пространства последовательностей ДНК.

Машинное обучение перебирает гиперпараметры. Grid search для 5 параметров по 10 значений — 10⁵ = 100 тысяч комбинаций. Случайный поиск сэмплирует умнее, но комбинаторный взрыв остаётся проблемой.

Логистика оптимизирует маршруты. Число вариантов для развозки по 30 точкам — 30! ≈ 2,6×10³². Эвристики (генетические алгоритмы, имитация отжига) находят хорошие решения без полного перебора. Это уже не чистая математика — инженерия на стыке комбинаторики и информатики.

Границы вычислимости

Не всё считается эффективно. P vs NP — нерешённая проблема: можно ли проверить решение быстро (NP), значит ли это, что его можно быстро найти (P)? Большинство математиков верит: P ≠ NP, т.е. существуют задачи с экспоненциальной сложностью.

Контринтуитивный факт: парадокс дней рождения. В группе из 23 человек вероятность совпадения дней рождения у двоих — 50%. Кажется мало? Но пар — C(23,2) = 253, это много сравнений. Комбинаторика объясняет, почему интуиция врёт.