This chapter hasn’t been translated into English yet, so here is the Russian original. Your browser can translate the page; the formulas and widgets work the same. Back to the English contents →

Решатель

Комбинаторика онлайн: перестановки, размещения и сочетания с решением

Ответьте на три вопроса — берём все или часть, важен ли порядок, можно ли повторять — и решатель выберет формулу, объяснит её, посчитает и для небольших задач выпишет все варианты.

Примеры: сочетания из 10 по 3 размещения из 8 по 3 анаграммы МАТЕМАТИКА 10 одинаковых шаров в 4 ящика, в каждом хотя бы 1 трёхзначные чётные числа из цифр 0, 1, 2, 3, 4, 5 без повторений от 1 до 1000 делятся на 2, 3 или 5 всего 30, A = 18, B = 15, A∩B = 7 C(10,3)·C(5,2)

Загружаем решатель…

Три вопроса вместо таблицы формул

В комбинаторике почти нет трудных вычислений: $10 \cdot 9 \cdot 8$ умножит любой. Трудно другое — понять, какую формулу брать. Сочетания и размещения отличаются одним словом, а ответы у них различаются в $k!$ раз. Поэтому решатель начинает не с формулы, а с трёх вопросов к задаче.

Берём все элементы или только часть? Рассадить шестерых на шесть стульев — все. Выбрать троих из десяти — часть.
Важен ли порядок? Проверка простая: поменяйте двух выбранных местами. Если получилось другое (золото и серебро поменялись, код 172 стал 712), порядок важен. Если ничего не изменилось (та же команда, тот же букет), не важен.
Можно ли брать один элемент несколько раз? Цифры в коде повторяются, люди в комиссии — нет.

Ответы сразу ведут к формуле:

Все или часть	Порядок	Повторы	Что это	Формула
все $n$	важен	нет	перестановки	$P_n = n!$
$k$ из $n$	важен	нет	размещения	$A_n^k = \frac{n!}{(n-k)!}$
$k$ из $n$	не важен	нет	сочетания	$C_n^k = \frac{n!}{k!\,(n-k)!}$
$k$ мест	важен	да	размещения с повторениями	$\bar A_n^k = n^k$
$k$ штук	не важен	да	сочетания с повторениями	$\bar C_n^k = C_{n+k-1}^k$

Сочетания в учебниках пишут двумя способами: $C_n^k$ и $\binom{n}{k}$ — это одно и то же число. В английских текстах размещения обозначают $P(n, k)$ или ${}^nP_k$, а на калькуляторах им соответствуют кнопки nPr и nCr.

Откуда берутся формулы

Все формулы таблицы выводятся из одного правила — правила произведения: если первый выбор можно сделать $a$ способами, а после него второй — $b$ способами, то пару выборов можно сделать $a \cdot b$ способами. Возьмём три призовых места и десять спортсменов. На золото претендуют все десять. Когда золото отдано, на серебро остаются девять, на бронзу — восемь. Итого $10 \cdot 9 \cdot 8 = 720$ пьедесталов.

Из скольких выбираем.

Сколько мест заполняем. Каждое следующее место — на один вариант беднее, потому что взятый элемент выбывает.

Пример: $A_{10}^3 = 10 \cdot 9 \cdot 8 = 720$. Через факториалы то же самое: $\frac{10!}{7!}$ — в $10!$ отрезаем «хвост» $7 \cdot 6 \cdots 1$, который нам не нужен.

Теперь спросим о другом: сколькими способами выбрать из тех же десяти троих в сборную, где все равны? Возьмём одну тройку — Аню, Бориса и Веру. Среди 720 пьедесталов она встречается шесть раз: АБВ, АВБ, БАВ, БВА, ВАБ, ВБА — это $3! = 6$ перестановок трёх человек. Так с каждой тройкой. Значит, троек в шесть раз меньше, чем пьедесталов.

Из скольких выбираем.

Сколько берём.

Столькими способами можно упорядочить один выбранный набор. Каждый набор среди размещений посчитан ровно $k!$ раз, поэтому делим.

Пример: $C_{10}^3 = \frac{720}{6} = 120$. Считать удобно так: $\frac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1}$ — сверху $k$ убывающих множителей, снизу $k!$. А если $k$ больше половины $n$, пользуйтесь тем, что $C_n^k = C_n^{n-k}$: выбрать 7 из 10 — всё равно что выбрать 3, которых не берём.

Та же идея — «посчитаем с лишним, а потом поделим на число повторов» — работает и для слов с одинаковыми буквами, и для круглого стола. В слове МАТЕМАТИКА десять букв, но три «А», две «М» и две «Т». Если бы все буквы были разными, перестановок было бы $10!$. Переставляя одинаковые буквы между собой, нового слова не получишь, поэтому делим на $3! \cdot 2! \cdot 2!$. За круглым столом делят на $n$: все $n$ поворотов одной рассадки — одна и та же рассадка, и остаётся $(n-1)!$.

Одинаковые предметы: шары и перегородки

Сколькими способами разложить 10 одинаковых конфет по 4 коробкам? Конфеты неотличимы, поэтому раскладка — это просто четыре числа с суммой 10, например $(5, 1, 2, 2)$. Выложим конфеты в ряд и поставим между ними три перегородки: до первой — первая коробка, между первой и второй — вторая, и так далее. Строка из 13 символов целиком определяется тем, на каких местах стоят перегородки.

Сколько одинаковых предметов раскладываем.

Сколько различных ящиков. Перегородок на одну меньше.

Пример: $n = 10$, $k = 4$ — это $\binom{13}{3} = 286$. Если в каждой коробке должна быть хотя бы одна конфета, сначала кладём по одной, а оставшиеся шесть раскладываем как угодно: $\binom{9}{3} = 84$. Та же формула считает решения уравнения $x_1 + x_2 + x_3 + x_4 = 10$ в неотрицательных целых числах и сочетания с повторениями.

Если же предметы различимы — десять разных открыток по четырём адресатам, — каждая открытка выбирает свой ящик независимо от других, и ответ $4^{10}$. Спутать эти две задачи — одна из самых частых ошибок.

Включения-исключения

Сколько чисел от 1 до 1000 делятся на 2, 3 или 5? Кратных двум — 500, трём — 333, пяти — 200. Но сложить их нельзя: число 6 попало и к «двоечникам», и к «троечникам». Вычтем кратные 6, 10 и 15. Теперь число 30 сначала прибавили трижды, потом трижды вычли — оно выпало из счёта. Вернём кратные 30. Знаки чередуются: одиночки со знаком плюс, пары с минусом, тройки с плюсом.

Размеры множеств: каждый элемент из двух множеств тут посчитан дважды, из трёх — трижды.

Попарные пересечения убирают двойной счёт, но элементы из всех трёх множеств вычтены трижды.

Возвращаем их. Теперь каждый элемент объединения посчитан ровно один раз.

Пример: $500 + 333 + 200 - 166 - 100 - 66 + 33 = 734$. Число кратных $d$ среди чисел от 1 до $N$ равно $\lfloor N/d \rfloor$, а «делится и на 2, и на 3» значит «делится на $\text{НОК}(2, 3) = 6$».

Разобранные примеры

Пример 1. Сборная и пьедестал

В классе 25 учеников. Сколькими способами выбрать троих на олимпиаду? Берём часть, порядок не важен (тройка — это тройка), повторов нет: сочетания, $C_{25}^3 = \frac{25 \cdot 24 \cdot 23}{3 \cdot 2 \cdot 1} = \frac{13\,800}{6} = 2300$.

А если нужно выбрать старосту, заместителя и казначея? Должности разные, поменять двух людей местами — получится другой вариант. Порядок важен: $A_{25}^3 = 25 \cdot 24 \cdot 23 = 13\,800$. Ровно в $3! = 6$ раз больше.

Пример 2. Анаграммы слова МАТЕМАТИКА

Букв 10, из них «А» — три, «М» — две, «Т» — две, остальные по одной. Если бы все буквы были разными, вышло бы $10! = 3\,628\,800$ перестановок. Каждое настоящее слово посчитано $3! \cdot 2! \cdot 2! = 24$ раза, поэтому

$$\frac{10!}{3!\,2!\,2!} = \frac{3\,628\,800}{24} = 151\,200.$$

Проверка другим способом: выберем места для трёх «А» — $C_{10}^3 = 120$, затем для двух «М» из оставшихся семи — $C_7^2 = 21$, для «Т» — $C_5^2 = 10$, а три разные буквы расставим на последние три места $3! = 6$ способами. $120 \cdot 21 \cdot 10 \cdot 6 = 151\,200$.

Пример 3. Чётные трёхзначные числа из цифр 0, 1, 2, 3, 4, 5 без повторений

Ноль мешает дважды: он не может стоять первым, но может стоять последним и сделать число чётным. Поэтому разберём два случая.

Последняя цифра 0. Тогда первая — любая из пяти остальных, средняя — любая из четырёх, что остались: $5 \cdot 4 = 20$.

Последняя цифра 2 или 4. Первая — не ноль и не та, что стоит последней: 4 варианта. Средняя — любая из четырёх оставшихся (теперь и ноль можно): $4 \cdot 4 \cdot 2 = 32$.

Случаи не пересекаются, поэтому складываем: $20 + 32 = 52$. Если обойтись без случаев и сразу написать $5 \cdot 4 \cdot 3$, ответ получится неверным: сколько вариантов остаётся для первой цифры, зависит от того, не занял ли последнее место ноль.

Пример 4. Кружки в классе

В классе 30 человек, 18 ходят на футбол, 15 — на шахматы, 7 — и туда, и туда. Сколько человек не ходят никуда? Хотя бы в один кружок ходят $18 + 15 - 7 = 26$ человек: семерых, которые ходят в оба, мы иначе посчитали бы дважды. Значит, никуда не ходят $30 - 26 = 4$. На диаграмме Венна это видно сразу: 11 только на футболе, 8 только на шахматах, 7 в пересечении и 4 снаружи — всего 30.

Типичные ошибки

Сочетания вместо размещений и наоборот. Прежде чем считать, поменяйте двух выбранных местами. Изменилось что-то — порядок важен.
Правило произведения там, где нужна сумма. «Поехать поездом (3 рейса) или самолётом (2 рейса)» — это $3 + 2$, а не $3 \cdot 2$. Умножают, когда делают первый выбор и второй, складывают — когда один или другой.
Забытый ноль в числах из цифр. Трёхзначное число не начинается с нуля. А если есть условие на последнюю цифру, почти всегда приходится разбирать случаи.
Деление на $k!$ «на всякий случай». Делят, только когда один и тот же вариант действительно посчитан $k!$ раз. В задаче про код из четырёх цифр делить не на что: 1234 и 4321 — разные коды.
Одинаковые и разные предметы. Одинаковые конфеты по коробкам — шары и перегородки, разные открытки — $k^n$.
Сложили количества пересекающихся множеств. Если объект может обладать двумя свойствами сразу, простое сложение считает его дважды — нужна формула включений-исключений.

Что ещё посмотреть

Откуда взялись все эти формулы и как устроен треугольник Паскаля, рассказано в главе «Комбинаторика»: перестановки — в разделе «Кто где сядет», размещения — «Пьедестал», сочетания — «Раздача», шары и перегородки — «Фишки и перегородки», включения-исключения и беспорядки — «Тринадцать». Чаще всего комбинаторика нужна, чтобы считать шансы: число благоприятных исходов, делённое на число всех, — это классическая вероятность, её решает решатель задач по теории вероятностей. А НОК, без которого не обходится формула включений-исключений для делимости, найдёт решатель НОД и НОК.