Три формулы, которые закрывают почти всю школьную и прикладную комбинаторику. Разбираем, чем они отличаются, откуда берётся факториал и почему в сочетаниях мы делим на k!. С интерактивным конструктором, который показывает не только число вариантов, но и сами варианты.
Если нужен только ответ — вот он. Всюду n — сколько всего элементов, k — сколько выбираем.
Что считаем
Формула
Порядок
Пример
Перестановки берём все элементы
P(n) = n!
важен
P(5) = 120
Размещения выбираем k из n
A(n,k) = n! / (n−k)!
важен
A(5,3) = 60
Сочетания выбираем k из n
C(n,k) = n! / (k!·(n−k)!)
не важен
C(5,3) = 10
// Связь между ними
Все три — одна формула в разных состояниях. Перестановки — это размещения, когда берут всё: A(n,n) = n!. А сочетания — это размещения, из которых убрали порядок: C(n,k) = A(n,k) / k!. Запоминать три формулы по отдельности не нужно.
Мысленная модель
Два вопроса, из которых следуют все формулы
Главная ошибка в комбинаторике — не арифметика, а выбор формулы. Причём выбирать почти не приходится: достаточно ответить на два вопроса про условие задачи.
Вопрос 1. Важен ли порядок? Возьмите два исхода, которые отличаются только порядком: «первый баннер A, второй B» и «первый B, второй A». Если по условию это разные результаты — порядок важен. Если один и тот же — не важен.
Вопрос 2. Можно ли брать элемент повторно? Пароль из букв — можно (AAB допустим). Три победителя из десяти участников — нельзя, один человек не займёт два места.
Два вопроса дают четыре комбинации ответов — и ровно четыре формулы:
// Как выбрать формулу
Дальше разбираем три основные ветки по очереди, а к повторениям вернёмся в отдельном блоке.
Формула 1
Перестановки: P(n) = n!
Перестановка — способ расставить все элементы по порядку, ничего не выбрасывая. Ничего не выбираем — только меняем очерёдность.
// Перестановки без повторений
Число перестановок из n элементов
P(n) = n! = 1 · 2 · 3 · … · n
Читается «эн факториал». Растёт чудовищно быстро: 5! = 120, а 10! = 3 628 800. Именно поэтому «перебрать все варианты» — почти всегда плохой план.
Откуда берётся факториал
Представь, что расставляешь 3 карточки — A, B и C — по трём позициям. На первую позицию есть 3 кандидата. Когда первая занята, на вторую остаётся 2. На третью — единственный оставшийся. Итого 3 · 2 · 1 = 6.
Никакой магии: на каждом шаге выбор сужается ровно на один элемент, а варианты перемножаются. Вот все шесть, если нарисовать выбор деревом:
// Дерево перестановок для n = 3
Ширина дерева на каждом уровне — это множитель в факториале. Для n = 4 листьев было бы уже 24, для n = 5 — 120.
// Крайний случай
0! = 1, и это не условность ради удобства. Пустой набор можно упорядочить ровно одним способом — оставить пустым. Без этого сломались бы формулы на границах: например, C(n,n) = n!/(n!·0!) = 1.
Формула 2
Размещения: A(n,k) = n! / (n−k)!
Размещение — выбираем k элементов из n и расставляем их по порядку. От перестановок отличается тем, что берём не всё; от сочетаний — тем, что порядок всё ещё важен.
// Размещения без повторений
Число размещений из n по k
A(n,k) = n! / (n−k)! = n · (n−1) · … · (n−k+1)
Правая часть удобнее для счёта: это просто k убывающих множителей, начиная с n. Факториалы целиком считать не нужно.
Пример: топ-3 баннера из 5
У тебя 5 баннеров, а на главной три слота: первый, второй и третий. Баннер в первом слоте увидят чаще, чем в третьем, — значит, порядок важен.
На первый слот — 5 кандидатов, на второй — 4 оставшихся, на третий — 3. Итого 5 · 4 · 3 = 60. Через формулу: A(5,3) = 5! / 2! = 120 / 2 = 60.
// Зачем деление на (n−k)!
Мы хотим оборвать произведение 5 · 4 · 3 · 2 · 1 после третьего множителя. Деление на (n−k)! = 2! = 2 · 1 ровно это и делает — сокращает «хвост». Формула не изобретает новое действие, а записывает обрыв произведения.
Формула 3
Сочетания: C(n,k) = n! / (k!·(n−k)!)
Сочетание — выбираем k элементов из n, и порядок не имеет значения. Результат — набор, а не последовательность: {A, B, C} и {C, A, B} — это одно и то же.
// Сочетания без повторений
Число сочетаний из n по k
C(n,k) = n! / (k! · (n−k)!)
Его же называют биномиальным коэффициентом и записывают как C(n,k), Cⁿₖ или (n над k) — это одно и то же число.
Почему мы делим на k!
Это главный затык темы, и он снимается одной картинкой. Посчитаем размещения из 4 элементов по 3: A(4,3) = 4 · 3 · 2 = 24. Теперь сгруппируем эти 24 варианта по составу — то есть по тому, какие именно буквы в них входят, без учёта порядка:
// 24 размещения группируются в 4 сочетания
{A,B,C}
ABCACBBACBCACABCBA
{A,B,D}
ABDADBBADBDADABDBA
{A,C,D}
ACDADCCADCDADACDCA
{B,C,D}
BCDBDCCBDCDBDBCDCB
Каждая строка — одно сочетание, внутри неё 6 = 3! перестановок одних и тех же букв. Строк ровно 4, значит C(4,3) = 24 / 6 = 4.
Отсюда и деление. Размещения посчитали каждый набор по k! раз — по одному разу на каждый его порядок. Чтобы получить число наборов, делим на это k!:
C(n,k) = A(n,k) / k! = n! / (k! · (n−k)!)
Проверка на нашем примере: C(5,3) = A(5,3) / 3! = 60 / 6 = 10. Из пяти баннеров можно составить 60 упорядоченных троек, но всего 10 разных наборов.
// Два свойства, которые экономят время
Симметрия:C(n,k) = C(n, n−k). Выбрать 7 элементов из 10 — то же самое, что решить, какие 3 останутся. Поэтому C(10,7) считают как C(10,3) = 120.
Счёт без факториалов:C(8,3) = (8 · 7 · 6) / (1 · 2 · 3) = 336 / 6 = 56. Никогда не считай 8! целиком — это лишняя работа и переполнение на больших числах.
Попробовать
Конструктор: покрути формулу руками
Формулы запоминаются, когда видишь не только число, но и сами варианты. Двигай n и k, переключай два условия — блок пересчитает формулу и покажет, что за ней стоит.
// Комбинаторный конструктор
Набор: A B C D E
Размещения без повторенийчастный случай размещений
A(n,k) = n! / (n−k)!
A(5,3) = 5! / 2! = 120 / 2
60 вариантов
// Все варианты
// Что стоит попробовать
Поставь k = n при включённом порядке — увидишь, как размещения превращаются в перестановки. Потом выключи «порядок важен» и посмотри, во сколько раз упало число вариантов: ровно в k! раз.
Четвёртый случай
Если элементы можно повторять
Всё, что было выше, предполагало: взял элемент — он кончился. Но бывает иначе. Пароль может содержать две одинаковые буквы, пользователь может купить два одинаковых товара, кубик может дважды выпасть шестёркой.
Формулы меняются, а логика остаётся той же — всё те же два вопроса:
Без повторений
С повторениями
Порядок важен
A(n,k) = n!/(n−k)! A(5,3) = 60
nᵏ 5³ = 125
Порядок не важен
C(n,k) = n!/(k!(n−k)!) C(5,3) = 10
C(n+k−1, k) C(7,3) = 35
Размещения с повторениями — самая простая формула из всех. Каждая из k позиций заполняется независимо, и на каждой доступны все n элементов: n · n · … · n = nᵏ. Отсюда классическая задача про пароль: три символа из 26 букв дают 26³ = 17 576 комбинаций.
Сочетания с повторениями встречаются реже, и формула C(n+k−1, k) выглядит взятой с потолка. Смысл такой: мы раскладываем k одинаковых шариков по n корзинам, а для этого нужна n−1 перегородка. Всего объектов в ряду n+k−1, и остаётся выбрать, какие k из них будут шариками.
Чек
Как не перепутать размещение и сочетание
Проверяй порядок на двух исходах. Не рассуждай абстрактно — возьми ABC и ACB и спроси: по условию это разные результаты? Ответ и есть выбор формулы.
«Команда» и «призовые места» — разное. Выбрать 3 человек в команду — сочетания. Раздать золото, серебро и бронзу — размещения.
Не считай факториалы целиком. Уже 21! не помещается в 64-битное целое, а в JavaScript точность теряется на 19!. Умножай k убывающих множителей и дели на k!.
Слово «выбрать» не означает сочетания. «Выбрать первого и второго» — это уже порядок. Смотри на условие, а не на глагол.
Проверяй крайние случаи. Формула должна давать C(n,0) = 1 и C(n,n) = 1. Если нет — ошибка в подстановке.
Прикидывай масштаб ответа. Сочетаний всегда меньше размещений, а размещений — не больше nᵏ. Ответ вне этих границ — сигнал.
Применение
Где это нужно продуктовому аналитику
Комбинаторику легко списать в школьную программу — до первого собеседования, где просят посчитать вероятность. Три места, где она возникает в работе:
// Вероятности
Задачи на собесе
Классическая вероятность — это отношение числа благоприятных исходов к общему числу. Оба числа обычно считаются сочетаниями.
// Статистика
Биномиальное распределение
Формула вероятности k конверсий из n показов начинается с C(n,k). На ней стоит весь анализ конверсий в A/B.
// Эксперименты
Множественные сравнения
Число попарных сравнений вариантов теста равно C(k,2) — от него зависит поправка уровня значимости.
Пример: сколько сравнений в A/B/n-тесте
Ты запускаешь тест с пятью вариантами лендинга. Сколько пар нужно сравнить? Порядок не важен — «A против B» и «B против A» это одно сравнение. Значит, сочетания: C(5,2) = 10 пар.
Дальше начинается статистика. Каждое сравнение с α = 0.05 даёт 5% шанс ложного срабатывания. На десяти сравнениях вероятность поймать хотя бы один ложный результат вырастает примерно до 40%. Поправка Бонферрони делит уровень значимости на число сравнений: 0.05 / 10 = 0.005.
// Нюанс, который отличает мидла
Десять пар — если сравниваешь все варианты между собой. Но чаще нужно сравнивать только с контролем, и тогда сравнений всего 4, а поправка мягче: 0.05 / 4 = 0.0125. Прежде чем делить α, реши, какие сравнения вообще входят в гипотезу — это разговор про дизайн эксперимента, а не про формулу. Подробнее про интерпретацию — в статье про p-value.
Практика
5 задач с решениями
Сначала ответь на два вопроса из схемы, и только потом подставляй числа. Решения — под спойлерами.
1
На дашборде 4 виджета. Сколько существует способов расставить их сверху вниз?
Показать решение
Берём все элементы, порядок важен, повторений нет — перестановки. P(4) = 4! = 1 · 2 · 3 · 4 = 24 способа.
2
Есть 6 баннеров и 3 слота на главной: первый, второй и третий. Сколько вариантов заполнения слотов?
Показать решение
Выбираем 3 из 6, слоты различимы → порядок важен, повторений нет — размещения. A(6,3) = 6 · 5 · 4 = 120 вариантов.
3
В беклоге 8 фич, в релиз войдут 3. Порядок разработки пока не обсуждается. Сколько вариантов состава релиза?
Показать решение
Порядок не важен, повторений нет — сочетания. C(8,3) = (8 · 7 · 6) / (1 · 2 · 3) = 336 / 6 = 56 вариантов. Обрати внимание: если бы порядок релизов имел значение, ответ был бы в 3! = 6 раз больше — 336.
4
Промокод состоит из 3 латинских букв (26 букв, буквы могут повторяться). Сколько всего промокодов?
Показать решение
Порядок важен (AB≠BA), повторения разрешены — размещения с повторениями. 26³ = 17 576 промокодов. Если бы повторы запретили, было бы A(26,3) = 26 · 25 · 24 = 15 600.
5
В корзине 8 товаров, из них 3 со скидкой. Наугад берём 2 товара. Какова вероятность, что оба окажутся со скидкой?
Показать решение
Порядок взятия не важен → всюду сочетания. Всего способов взять 2 товара из 8: C(8,2) = (8 · 7) / 2 = 28. Благоприятных — взять 2 из 3 скидочных: C(3,2) = 3. Вероятность: 3 / 28 ≈ 0.107, то есть ≈ 10.7%. Это самый частый шаблон вероятностных задач на собеседовании: посчитать сочетаниями числитель и знаменатель.
FAQ
Частые вопросы про формулы комбинаторики
Чем отличается размещение от сочетания?
Порядком. В размещениях порядок важен: ABC и ACB — два разных размещения. В сочетаниях порядок не важен: ABC и ACB — одно сочетание {A, B, C}. Поэтому размещений всегда больше ровно в k! раз: A(n,k) = C(n,k) · k!. Например, из 5 элементов по 3: размещений 60, а сочетаний 10, потому что каждое сочетание можно упорядочить 3! = 6 способами.
Что такое перестановки простыми словами?
Перестановка — способ расставить все имеющиеся элементы по порядку, ничего не выбрасывая. Число перестановок из n элементов равно n! = 1 · 2 · … · n. Для 5 элементов это 120 способов. По сути перестановки — частный случай размещений при k = n.
Как понять, важен ли порядок в задаче?
Возьмите два конкретных исхода, которые отличаются только порядком, — например, «первый баннер A, второй B» и «первый B, второй A». Если по условию задачи это разные результаты, порядок важен и нужны размещения или перестановки. Если это один и тот же результат — нужны сочетания. Приём работает и на сложных условиях, где формулировка запутана.
Чему равен 0! и почему?
0! = 1. Пустой набор можно упорядочить ровно одним способом — оставить его пустым. Кроме того, это значение нужно, чтобы формулы работали на границах: C(n,n) = n!/(n!·0!) = 1, то есть выбрать все n элементов из n можно ровно одним способом.
Как посчитать число сочетаний без калькулятора?
Не считайте факториалы целиком — они растут слишком быстро. Умножайте k убывающих множителей и делите на k!: C(8,3) = (8 · 7 · 6) / (1 · 2 · 3) = 56. Помогает и симметрия C(n,k) = C(n, n−k): считать C(10,7) неудобно, а равное ему C(10,3) = 120 — легко.
Зачем комбинаторика продуктовому аналитику?
Три применения. Первое: задачи на вероятность на собеседовании почти всегда сводятся к отношению благоприятных исходов к общему числу, то есть к сочетаниям. Второе: биномиальное распределение, на котором стоит анализ конверсий в A/B-тестах, начинается с коэффициента C(n,k). Третье: при k вариантах теста число попарных сравнений равно C(k,2), и от него зависит поправка уровня значимости.
Комбинаторика — это не три формулы для заучивания, а два вопроса: важен ли порядок и можно ли повторять элементы. Ответы дают формулу автоматически.
Перестановки n! — расставляем всё. Размещения n!/(n−k)! — выбираем k и расставляем. Сочетания n!/(k!(n−k)!) — выбираем k, порядок не нужен. Третья формула получается из второй делением на k!, потому что размещения считают каждый набор по одному разу на каждый его порядок.
Практика: возьми задачу 5 из блока выше и пересчитай её для 10 товаров, из которых 4 со скидкой. Если получилось C(4,2)/C(10,2) = 6/45 ≈ 13.3% — формулы уложились.
АТ
Андрей Тарасенко
// Продуктовый аналитик · Авито · Ментор
Комбинаторику я вспомнил не в школе, а когда впервые считал поправку на множественные сравнения и понял, что не могу с ходу сказать, сколько пар получается из шести вариантов. С тех пор отношусь к ней как к рабочему инструменту, а не к абстрактной математике.
Задачи на вероятность — не последнее, что спросят на собесе
Комбинаторику на интервью аналитика спрашивают между делом, а SQL — всерьёз и подолгу. В тренажёре 20 бесплатных задач с проверкой решения прямо в браузере.