Возьмите обычную колоду из 36 карт и тщательно её перетасуйте. А теперь представьте: если бы каждый из восьми миллиардов жителей Земли с самого Большого взрыва тасовал по одной колоде в секунду, не останавливаясь, — мы до сих пор не повторили бы ни одного расклада. Каждая ваша тасовка с почти полной уверенностью создаёт порядок карт, которого не существовало никогда в истории Вселенной.
Откуда такие безумные числа? Их считает комбинаторика — раздел математики, который отвечает на вопрос «сколькими способами можно расставить, выбрать или собрать что-то». На вид — школьная скучища про «расставить шахматные фигуры». На деле — фундамент криптографии, генетики и любой современной лотереи.
Короткий ответ
Комбинаторика — раздел дискретной математики, который занимается подсчётом количества способов выбрать или упорядочить объекты. Три её главные операции — это перестановки (расставить всё), размещения (выбрать и расставить часть) и сочетания (просто выбрать без порядка). А базовый принцип, на котором они все построены, — правило умножения.
💡 Удивительно: число вариантов перетасовки колоды из 36 карт — примерно 3,7 × 10⁴¹. Это в миллион раз больше, чем количество атомов во всей Земле. И тем не менее это число можно записать одной короткой формулой: 36!.
Пример из жизни: сколько нарядов у Маши
У школьницы Маши в шкафу 3 футболки и 4 юбки. Сколько разных образов она может собрать? Вспомните школьный рефлекс: «3 + 4 = 7». Это ловушка. Правильный ответ — 12.
Логика: каждую футболку Маша может надеть с любой из 4 юбок. Значит, 3 футболки дают 3 × 4 = 12 образов. Этот принцип — самый главный в комбинаторике, и называется он правилом умножения: если первое решение можно принять m способами, а второе — независимо от первого — n способами, то всего вариантов будет m · n.
Три кита комбинаторики
Когда объектов мало, можно нарисовать дерево. Когда их 30 — уже не получится. Поэтому в комбинаторике придумали три формулы для трёх типов задач.
1. Перестановки: расставить ВСЁ
На скамейке должны сесть 5 человек. Сколько разных «рассадок»? Первое место — 5 вариантов. Второе — уже 4 (один человек занял первое). Третье — 3, потом 2, потом 1. Перемножаем: 5 · 4 · 3 · 2 · 1 = 120.
Произведение всех чисел от 1 до n называется факториалом и записывается как n!. Так что число перестановок n предметов — это просто n!.
2. Размещения: выбрать и расставить часть
В классе 10 человек, нужно выбрать капитана и его заместителя. Капитана — 10 способов. Заместителя — 9. Всего 10 · 9 = 90 пар. Здесь важен порядок: «Маша-капитан, Петя-зам» и «Петя-капитан, Маша-зам» — это разные результаты.
В общем виде формула размещений: A(n, k) = n! / (n − k)!. Для нашего примера A(10, 2) = 10! / 8! = 10 · 9 = 90.
3. Сочетания: просто выбрать, без порядка
А теперь нужно из тех же 10 человек собрать команду из 3 — без должностей, просто состав. Тут «Маша-Петя-Ваня» и «Ваня-Маша-Петя» — одна и та же команда. Порядок не важен.
Берём размещения и делим на число «лишних» перестановок внутри команды: формула сочетаний C(n, k) = n! / (k!(n−k)!). Для нашего примера C(10, 3) = 10!/(3!·7!) = 120 команд.
Различие легко запомнить так: размещения — это «выбрать и поставить на полки», сочетания — «выбрать и сложить в пакет».
Два разных способа подойти к одной задаче
Сколько 4-значных PIN-кодов можно составить из цифр 0–9, если цифры могут повторяться?
- Через правило умножения: 10 вариантов на каждой из 4 позиций → 10 · 10 · 10 · 10 = 10 000 кодов.
- Через формулу размещений с повторами: A с повторами по формуле n^k = 10⁴ = 10 000.
Оба способа дают один ответ. Это типичная вещь в комбинаторике: одну задачу часто можно решить и «руками», и формулой. На простых случаях оба способа работают, на сложных — формулы экономят часы. Ровно поэтому их и придумали.
Пример из жизни: почему лотерея — не лучшая инвестиция
Классическая лотерея «6 из 49»: вытаскивают 6 шаров из 49. Чтобы выиграть джекпот, ваши 6 чисел должны совпасть со всеми 6 выпавшими — порядок не важен. Сколько различных билетов нужно проверить?
Это типичные сочетания: C(49, 6) = 49!/(6!·43!) = 13 983 816. Почти 14 миллионов комбинаций. Купив один билет, вы выигрываете джекпот с вероятностью 1 / 13 983 816 ≈ 0,000007%. Это меньше, чем шанс быть убитым молнией дважды за жизнь.
А теперь финансовая хитрость: чтобы гарантированно выиграть, нужно купить все 13,98 млн уникальных билетов. По 100 рублей за каждый — около 1,4 млрд рублей. Поэтому организатор всегда выставляет джекпот меньше этой суммы — даже если кто-то скупит все билеты, он останется в минусе. Так комбинаторика прямо определяет, какой максимальный приз можно нарисовать в рекламе, и сколько в реальности заработает организатор.
Попробуйте сами
Задача 1. В чемпионате школы по шахматам участвуют 8 человек. Каждый играет с каждым по одной партии. Сколько всего будет партий?
Партия — это пара игроков, в которой порядок не важен (партия Маша–Петя — та же, что Петя–Маша). Значит, нужны сочетания.
C(8, 2) = 8!/(2!·6!) = (8·7)/2 = 28 партий.
Задача 2. Сколько разных 5-буквенных «слов» можно составить из букв слова «ШКОЛА» (все буквы разные, каждую используем по разу)?
Это перестановки 5 различных букв.
5! = 5 · 4 · 3 · 2 · 1 = 120 «слов». Большинство, конечно, бессмысленные, но математически — это всё разные комбинации.
Задача 3. В кошельке 5 монет: 1, 2, 5, 10 и 50 рублей. Сколькими способами можно достать одну монету за другой, чтобы получилась последовательность из 3 монет?
Здесь важен порядок (10 → 50 → 1 и 1 → 50 → 10 — разные действия), и из 5 монет выбираем 3. Это размещения.
A(5, 3) = 5!/2! = 5 · 4 · 3 = 60 способов.
История: как Паскаль и Ферма поделили ставку
Считать комбинации люди начали ещё в Древней Индии — в трактате VI века «Bhāskara II» уже была формула сочетаний. Но настоящий расцвет комбинаторики начался во Франции в 1654 году, и поводом стала пьянка.
Кавалер де Мере, заядлый игрок, спросил у математика Блеза Паскаля: если двое играют в азартную игру до 5 побед, и игру прервали при счёте 4:3, как справедливо разделить ставку? Паскаль написал письмо Пьеру Ферма — и эта переписка двух гениев стала началом сразу двух наук: теории вероятностей и современной комбинаторики. В тех же письмах появился и треугольник Паскаля — таблица, в которой все числа сочетаний C(n, k) выстраиваются в красивую геометрическую фигуру.
Так что весь раздел математики родился из обычной игры в кости. Каждый раз, когда современный казино-калькулятор считает «справедливый» коэффициент ставки, он повторяет работу Паскаля и Ферма — только в миллион раз быстрее.
Удивительный финал: комбинаторика внутри клетки
Главное применение комбинаторики сегодня — не игра и не лотерея. Это биология. Молекула ДНК — это последовательность из четырёх «букв»: A, T, G, C. Длина человеческой ДНК — около 3 миллиардов букв. Сколько различных ДНК-последовательностей такой длины математически возможно?
4 в степени 3 000 000 000. Это число невозможно записать обычным образом — в нём около 1,8 миллиарда знаков. Если бы каждый атом во Вселенной хранил по одному варианту, нам бы не хватило вселенных. Эволюция перебирает крошечную долю этого пространства — и за 4 миллиарда лет «нащупала» работающие комбинации, которые мы называем живыми существами.
Когда биоинформатики ищут лекарство от рака или новый антибиотик, они ровно этим и занимаются: умной комбинаторной перебиркой среди космического числа возможностей. Тот же 3 × 4 = 12, что у Маши с футболками — только размах в 10⁴⁰⁰⁰⁰⁰⁰⁰⁰⁰ раз шире.
Часто задаваемые вопросы
Чем сочетание отличается от размещения?
В размещении важен порядок выбранных элементов: «капитан и зам» — это размещение. В сочетании порядок не важен: «команда из трёх человек» — это сочетание. Сочетание всегда меньше размещения в k! раз — на число способов переставить выбранные k элементов.
Что такое факториал и зачем он нужен?
Факториал n! — это произведение всех натуральных чисел от 1 до n. По договорённости 0! = 1. Факториал растёт стремительно: 5! = 120, 10! ≈ 3,6 миллиона, 20! уже 2,4 квинтиллиона. Поэтому простые задачи комбинаторики дают очень большие числа, и без формул их не посчитать.
Где встречается комбинаторика в реальной жизни?
В криптографии (число возможных паролей), в генетике (число вариантов ДНК), в логистике (число маршрутов курьера), в азартных играх и страховании (расчёт вероятностей), в дизайне меню и шкафа (сколько комбинаций блюд / нарядов), в спортивных турнирах (число матчей). Без комбинаторики не сосчитать ни число IP-адресов, ни число возможных партий в шахматах.
Связан ли треугольник Паскаля с комбинаторикой?
Напрямую. На n-й строке (нумерация с 0) и k-й позиции стоит ровно число C(n, k). То есть весь треугольник — это таблица сочетаний. Поэтому коэффициенты разложения (a + b)ⁿ — это числа сочетаний из той же строки. Алгебра и комбинаторика встречаются ровно в этой точке.
Как считать, если элементы могут повторяться?
Для размещений с повторами формула простая: nᵏ. Для сочетаний с повторами — формула «звёзд и палочек»: C(n + k − 1, k). Например, сколько способов выбрать 3 шарика мороженого из 5 видов, если один и тот же вид можно брать несколько раз? Ответ: C(7, 3) = 35.