Комбинаторика считает, сколько результатов возможно, когда мы выбираем или упорядочиваем объекты. Сначала спросите, важен ли порядок и берём ли мы все объекты: перестановки упорядочивают всё, размещения выбирают и упорядочивают часть, а сочетания выбирают часть без порядка. Это различие определяет формулу и защищает от большинства ошибок.
Например, порядок карт в колоде — это перестановка, капитан и заместитель — размещение, а команда без ролей — сочетание. В каждом случае важно назвать объекты различимыми и заранее решить, разрешены ли повторы.
Как выбрать формулу по условию
Комбинаторика — раздел дискретной математики, который занимается подсчётом количества способов выбрать или упорядочить объекты. Три её главные операции — это перестановки (расставить всё), размещения (выбрать и расставить часть) и сочетания (просто выбрать без порядка). А базовый принцип, на котором они все построены, — правило умножения.
Перед формулой ответьте на три вопроса: все ли объекты используются, меняет ли перестановка выбранных объектов результат и разрешено ли брать один объект повторно. Если хотя бы одно условие не названо, сначала уточните модель: одна и та же история может привести к разным ответам.
💡 Удивительно: число вариантов перетасовки колоды из 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 способов.
История: как Паскаль и Ферма поделили ставку
Комбинаторные задачи существовали задолго до XVII века, но важный европейский этап связан с перепиской Паскаля и Ферма в 1654 году. Они обсуждали не отвлечённую формулу, а практический вопрос об остановленной игре.
Одна из задач, которые обсуждали в XVII веке, звучала так: как справедливо разделить ставку, если игру до заранее оговорённого числа побед пришлось остановить раньше? В 1654 году Блез Паскаль и Пьер Ферма переписывались о такой «задаче о разделении ставки». Их рассуждения стали важным этапом ранней теории вероятностей: вместо гадания нужно было перечислить возможные продолжения игры и посчитать благоприятные исходы.
Комбинаторные идеи существовали задолго до этой переписки. Паскаль позднее систематически исследовал арифметический треугольник, но сама числовая схема была известна в других математических традициях раньше. Связь здесь не в красивой легенде об одном моменте рождения науки, а в общем приёме: разбить неопределённость на конечные случаи и честно посчитать их.
Удивительный финал: комбинаторика внутри клетки
Комбинаторная модель полезна и для последовательностей. Если в каждой позиции разрешены четыре символа A, T, G и C, то для последовательности длины n существует 4ⁿ возможных записей. Это подсчёт вариантов модели, а не описание того, какие последовательности жизнеспособны или встречаются в природе.
Например, при n = 10 получается 4¹⁰ = 1 048 576 вариантов. Уже этот небольшой пример показывает, почему полный перебор быстро становится непрактичным. В реальных задачах ограничения модели и данные определяют, какие варианты вообще рассматривают.
Тот же принцип работает в алгоритмах: сначала задают допустимые варианты, затем используют ограничения, чтобы не перечислять заведомо неподходящие случаи. Так правило умножения превращается из примера с одеждой в способ оценить размер задачи.
Часто задаваемые вопросы
Чем сочетание отличается от размещения?
В размещении важен порядок выбранных элементов: «капитан и зам» — это размещение. В сочетании порядок не важен: «команда из трёх человек» — это сочетание. Сочетание всегда меньше размещения в k! раз — на число способов переставить выбранные k элементов.
Что такое факториал и зачем он нужен?
Факториал n! — это произведение всех натуральных чисел от 1 до n. По договорённости 0! = 1. Факториал растёт стремительно: 5! = 120, 10! ≈ 3,6 миллиона, 20! уже 2,4 квинтиллиона. Поэтому простые задачи комбинаторики дают очень большие числа, и без формул их не посчитать.
Где встречается комбинаторика в реальной жизни?
Комбинаторика нужна везде, где сначала задают конечный набор вариантов: при оценке числа возможных паролей, сравнении маршрутов, составлении расписаний и подсчёте пар участников турнира. Она показывает размер пространства вариантов; чтобы выбрать лучший или оценить вероятность, затем добавляют правила конкретной задачи.
Связан ли треугольник Паскаля с комбинаторикой?
Напрямую. На n-й строке (нумерация с 0) и k-й позиции стоит ровно число C(n, k). То есть весь треугольник — это таблица сочетаний. Поэтому коэффициенты разложения (a + b)ⁿ — это числа сочетаний из той же строки. Алгебра и комбинаторика встречаются ровно в этой точке.
Как считать, если элементы могут повторяться?
Для размещений с повторами формула простая: nᵏ. Для сочетаний с повторами — формула «звёзд и палочек»: C(n + k − 1, k). Например, сколько способов выбрать 3 шарика мороженого из 5 видов, если один и тот же вид можно брать несколько раз? Ответ: C(7, 3) = 35.
Сначала выбрать модель
Отличите команду без ролей от набора назначений?
В задачах на математическое мышление сначала фиксируют, что меняет результат: порядок, повтор или ограничение. Затем формула становится проверкой решения, а не угадыванием.
Читайте также
- Треугольник Паскаля: правило, формулы и где он встречается
- Бесконечность в математике: что это такое и почему бывает разного размера
- Фракталы: что это, примеры в природе и формула красоты
- Парадокс дня рождения: почему 23 человек хватит для совпадения
- Магический квадрат — что это такое, виды и как составить