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

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

Комбинаторика — это раздел математики, который отвечает на вопрос «сколькими способами?». Её изучают в 9 классе и возвращаются к ней в 11-м перед НМТ, потому что без неё не работает теория вероятностей: чтобы посчитать вероятность, сначала нужно посчитать количество вариантов. Формул здесь всего три, и они простые. Сложность в другом — ученики не могут определить, какую именно из трёх брать. На занятиях в Tutor-Math мы ставим этот вопрос ребром с самого начала: сначала критерий выбора формулы, потом сами формулы.

Два базовых правила: сумма и произведение

Вся комбинаторика выводится из двух правил. Если их понять, остальные формулы можно получить самостоятельно.

Правило суммы. Если объект \(A\) можно выбрать \(m\) способами, а объект \(B\) — \(n\) способами, и эти выборы взаимно исключают друг друга, то выбрать «\(A\) или \(B\)» можно \(m + n\) способами.

Правило произведения. Если объект \(A\) можно выбрать \(m\) способами, а после этого объект \(B\) — \(n\) способами, то пару «\(A\) и \(B\)» можно выбрать \(m \cdot n\) способами.

Ключевое слово-маркер: «или» — складываем, «и» — умножаем. Правило произведения естественно распространяется на любое число шагов: если действие выполняют в \(k\) этапов и на \(i\)-м этапе есть \(n_i\) вариантов, то всего способов \(n_1 \cdot n_2 \cdot \ldots \cdot n_k\).

Например, в столовой 3 салата, 4 первых блюда и 5 десертов. Обед из трёх позиций можно составить \(3 \cdot 4 \cdot 5 = 60\) способами — это чистое произведение, ведь нужно взять салат и суп и десерт.

Факториал и почему \(0! = 1\)

Определение. Факториалом натурального числа \(n\) называют произведение всех натуральных чисел от 1 до \(n\): \(n! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n\). Отдельно договариваются, что \(0! = 1\).

Факториал растёт очень быстро: \(1! = 1\), \(2! = 2\), \(3! = 6\), \(4! = 24\), \(5! = 120\), \(6! = 720\), а уже \(10! = 3\,628\,800\).

Главное рабочее свойство — рекуррентное: \(n! = n \cdot (n-1)!\). Именно оно и объясняет равенство \(0! = 1\). Подставим \(n = 1\):

\[ 1! = 1 \cdot 0! \quad \Longrightarrow \quad 1 = 1 \cdot 0! \quad \Longrightarrow \quad 0! = 1 \]

То есть \(0! = 1\) — не прихоть и не «договорённость ради красоты», а единственное значение, при котором рекуррентная формула не ломается на единице. Есть и содержательное объяснение: \(n!\) — это количество способов упорядочить \(n\) предметов. Пустое множество можно упорядочить ровно одним способом — не взяв ничего. Поэтому \(0! = 1\).

Практически важно ещё одно: в задачах постоянно приходится сокращать дроби с факториалами. Делайте это не через вычисление, а через рекуррентность, иначе числа станут неуправляемыми:

\[ \frac{10!}{7!} = \frac{10 \cdot 9 \cdot 8 \cdot 7!}{7!} = 10 \cdot 9 \cdot 8 = 720 \]

Перестановки

Перестановки из \(n\) элементов — это упорядоченные наборы, в которые входят все \(n\) элементов и которые отличаются только порядком. Их количество \(P_n = n!\).

Почему именно \(n!\)? Правило произведения: на первое место можно поставить любой из \(n\) элементов, на второе — любой из оставшихся \(n-1\), далее \(n-2\), и так до последнего места, где выбора уже нет. Значит, \(P_n = n(n-1)(n-2)\cdot\ldots\cdot 1 = n!\).

Перестановки — это «рассадить всех», «расставить все книги», «составить расписание из всех уроков». Ничего не отбрасываем, ничего не оставляем вне набора.

Размещения

Размещения из \(n\) элементов по \(k\) — это упорядоченные наборы из \(k\) различных элементов, взятых из \(n\) имеющихся. Их количество \[ A_n^k = \frac{n!}{(n-k)!} = n(n-1)(n-2)\cdot\ldots\cdot(n-k+1) \] (ровно \(k\) множителей, каждый следующий на единицу меньше).

Вывод тот же: первое место — \(n\) вариантов, второе — \(n-1\), и так \(k\) раз. Обратите внимание на частный случай: при \(k = n\) получаем \(A_n^n = \dfrac{n!}{0!} = n!\) — то есть перестановки являются частным случаем размещений. Вот здесь и работает договорённость \(0! = 1\): без неё формула размещений при \(k = n\) просто не имела бы смысла.

Размещения — это «призовые места», «должности в комитете», «различные по роли позиции»: набор тот же, но кто именно первый, а кто второй — важно.

Сочетания

Сочетания из \(n\) элементов по \(k\) — это подмножества из \(k\) различных элементов, взятых из \(n\) имеющихся, без учёта порядка. Их количество \[ C_n^k = \frac{n!}{k!\,(n-k)!} = \frac{A_n^k}{k!} \]

Вторая форма записи объясняет формулу лучше всего. Возьмём все размещения \(A_n^k\). Каждая конкретная группа из \(k\) элементов посчитана в них столько раз, сколькими способами эту группу можно упорядочить, то есть \(k!\) раз. Делим на \(k!\) — и каждая группа остаётся посчитанной ровно один раз.

Сочетания — это «выбрать команду», «выбрать дежурных», «выбрать букет из цветов»: все выбранные равноправны, порядок ничего не меняет.

Как выбрать формулу: алгоритм-вопросник

Это ядро всей темы. Формулы вы выучите за десять минут, а путаться в них будете годами — если не иметь чёткого критерия. Критерий состоит из двух вопросов, которые нужно задавать именно в таком порядке.

Вопрос 1. Все ли \(n\) элементов входят в набор, или мы берём только часть (\(k < n\))?
Вопрос 2. Меняет ли дело порядок элементов в наборе?

Ответы дают решение:

• Берём все \(n\) элементов, порядок важен → перестановки, \(P_n = n!\).
• Берём часть (\(k\) из \(n\)), порядок важен → размещения, \(A_n^k\).
• Берём часть (\(k\) из \(n\)), порядок не важен → сочетания, \(C_n^k\).

Четвёртой клетки — «все элементы, порядок не важен» — не существует: взять все элементы без учёта порядка можно ровно одним способом. Формально это согласовано: \(C_n^n = 1\).

Самое сложное — второй вопрос. Вот надёжный способ его проверить, не полагаясь на интуицию.

Тест на порядок. Возьмите два конкретных набора из одних и тех же элементов, записанных в разном порядке. Спросите себя: это два разных результата или один и тот же? Разные — порядок важен (размещения). Один и тот же — порядок не важен (сочетания).

Пример работы теста. Из класса выбирают старосту и заместителя. Наборы «Аня — староста, Богдан — заместитель» и «Богдан — староста, Аня — заместитель» — это очевидно разные результаты. Порядок важен, значит, размещения. Теперь из того же класса выбирают двух дежурных. «Аня и Богдан» и «Богдан и Аня» — это одна и та же пара дежурных. Порядок не важен, значит, сочетания.

Ещё одна подсказка из текста задачи. Слова «место», «должность», «подряд», «шифр», «номер», «расписание», «расставить», «рассадить» почти всегда означают порядок. Слова «группа», «команда», «подмножество», «набор», «выбрать нескольких» — почти всегда означают его отсутствие. Но слова — лишь подсказка; решает тест.

И отдельное предостережение: все три формулы действуют, только когда элементы не повторяются. Если в задаче можно брать один и тот же элемент дважды (цифры в коде, цвета во флажке), формулы не работают — там напрямую применяют правило произведения, и ответ имеет вид \(n^k\).

Свойства сочетаний и треугольник Паскаля

У сочетаний есть несколько свойств, заметно сокращающих вычисления.

\[ C_n^k = C_n^{n-k}, \qquad C_n^0 = C_n^n = 1, \qquad C_n^1 = n \]

Первое — свойство симметрии, и оно очевидно содержательно: выбрать \(k\) элементов «в команду» — то же самое, что выбрать \(n-k\) элементов, которые остаются вне команды. Каждому выбору соответствует ровно один «антивыбор». Проверим на числах: \(C_{10}^{3} = 120\) и \(C_{10}^{7} = 120\). Практическая польза: если \(k\) больше половины \(n\), считайте \(C_n^{n-k}\) — множителей будет меньше.

Второе ключевое свойство — тождество Паскаля:

\[ C_n^k = C_{n-1}^{k-1} + C_{n-1}^{k} \]

Именно оно порождает треугольник Паскаля: по краям стоят единицы, а каждое внутреннее число равно сумме двух соседей сверху.

• \(n=0\): \(1\)
• \(n=1\): \(1\quad 1\)
• \(n=2\): \(1\quad 2\quad 1\)
• \(n=3\): \(1\quad 3\quad 3\quad 1\)
• \(n=4\): \(1\quad 4\quad 6\quad 4\quad 1\)
• \(n=5\): \(1\quad 5\quad 10\quad 10\quad 5\quad 1\)
• \(n=6\): \(1\quad 6\quad 15\quad 20\quad 15\quad 6\quad 1\)

Строка с номером \(n\) — это все числа \(C_n^0, C_n^1, \ldots, C_n^n\). Симметрия строк — это и есть свойство \(C_n^k = C_n^{n-k}\). А сумма чисел строки равна \(2^n\): для \(n = 5\) имеем \(1+5+10+10+5+1 = 32 = 2^5\) — см. степень с натуральным показателем.

Связь с биномом Ньютона

Числа \(C_n^k\) называют ещё биномиальными коэффициентами, потому что именно они стоят в разложении степени двучлена.

\[ (a+b)^n = C_n^0 a^n + C_n^1 a^{n-1}b + C_n^2 a^{n-2}b^2 + \ldots + C_n^n b^n \]

Причина комбинаторная: раскрывая \(n\) одинаковых скобок, слагаемое с \(b^k\) образуется каждый раз, когда мы выбираем \(b\) ровно из \(k\) скобок из \(n\). Количество таких выборов — \(C_n^k\).

Проверка при \(n=5\): коэффициенты \(1, 5, 10, 10, 5, 1\) — это ровно шестая строка треугольника Паскаля, и \((a+b)^5 = a^5 + 5a^4b + 10a^3b^2 + 10a^2b^3 + 5ab^4 + b^5\). Так же \(C_6^2 = 15\) — это коэффициент при \(a^4b^2\) в разложении \((a+b)^6\).

Примеры

Пример 1 (правила суммы и произведения). Из города A в город B ведут 3 дороги, из B в C — 4 дороги. Кроме того, есть 2 прямых рейса из A в C. Сколькими способами можно добраться из A в C?

Два взаимно исключающих варианта: через B или прямым рейсом. Маршрут через B — это «дорога A–B и дорога B–C», то есть произведение: \(3 \cdot 4 = 12\). Прямых рейсов 2. По правилу суммы: \(12 + 2 = 14\).

Ответ: 14 способов.

Пример 2 (порядок есть, с повторениями и без). Сколько трёхзначных чисел можно составить из цифр 1, 2, 3, 4, 5, если: а) цифры могут повторяться; б) цифры должны быть различными?

а) Повторения разрешены — никакая формула не нужна, работает правило произведения: на каждый из трёх разрядов есть 5 вариантов, всего \(5 \cdot 5 \cdot 5 = 5^3 = 125\).

б) Повторений нет, берём 3 цифры из 5, порядок важен (числа 123 и 321 разные) — размещения:

\[ A_5^3 = \frac{5!}{(5-3)!} = \frac{120}{2} = 5 \cdot 4 \cdot 3 = 60 \]

Ответ: а) 125; б) 60.

Пример 3 (перестановки с ограничением). На полку ставят 6 различных книг. Сколькими способами это можно сделать так, чтобы две конкретные книги не стояли рядом?

Всего расстановок: \(P_6 = 6! = 720\). Посчитаем «плохие» — те, где книги стоят рядом. Склеим две книги в один блок: тогда переставляем 5 объектов, это \(P_5 = 5! = 120\) способов, и внутри блока книги можно поменять местами \(2! = 2\) способами. «Плохих» расстановок \(120 \cdot 2 = 240\). Искомое количество: \(720 - 240 = 480\).

Ответ: 480 способов.

Пример 4 (размещения). В соревновании участвуют 10 спортсменов. Сколькими способами могут распределиться золотая, серебряная и бронзовая медали?

Тест на порядок: «Пётр — золото, Иван — серебро» и «Иван — золото, Пётр — серебро» — разные результаты. Порядок важен, берём 3 из 10 — размещения:

\[ A_{10}^{3} = \frac{10!}{7!} = 10 \cdot 9 \cdot 8 = 720 \]

Ответ: 720 способов.

Пример 5 (сочетания). В классе 25 учеников. Сколькими способами можно выбрать 4 дежурных?

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

\[ C_{25}^{4} = \frac{25!}{4!\,21!} = \frac{25 \cdot 24 \cdot 23 \cdot 22}{1 \cdot 2 \cdot 3 \cdot 4} = \frac{303\,600}{24} = 12\,650 \]

Ответ: 12 650 способов.

Пример 6 (комбинированный выбор). В кружке 7 мальчиков и 5 девочек. Сколькими способами можно составить команду из 3 мальчиков и 2 девочек?

Внутри каждой группы порядок не важен, поэтому дважды считаем сочетания, а результаты перемножаем (нужно выбрать мальчиков и девочек):

\[ C_7^3 = \frac{7 \cdot 6 \cdot 5}{1 \cdot 2 \cdot 3} = 35, \qquad C_5^2 = \frac{5 \cdot 4}{1 \cdot 2} = 10 \] \[ N = C_7^3 \cdot C_5^2 = 35 \cdot 10 = 350 \]

Ответ: 350 способов.

Пример 7 (бином Ньютона). Найти коэффициент при \(x^5\) в разложении \((x+2)^8\).

В формуле бинома \(a = x\), \(b = 2\), \(n = 8\). Слагаемое с \(x^5\) соответствует \(a^5 b^3\), то есть \(k = 3\):

\[ C_8^3 \cdot x^5 \cdot 2^3 = \frac{8 \cdot 7 \cdot 6}{1 \cdot 2 \cdot 3} \cdot x^5 \cdot 8 = 56 \cdot 8 \cdot x^5 = 448 x^5 \]

Ответ: 448.

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

• Путают размещения и сочетания. Самая частая ошибка темы: берут \(A_n^k\) там, где нужны \(C_n^k\), и получают ответ, больший ровно в \(k!\) раз. Лечится тестом на порядок — двумя конкретными наборами, а не ощущением.
• Складывают вместо умножения (и наоборот). «Или» — сумма, «и» — произведение. Если этапы выполняются последовательно и оба обязательны, это всегда произведение.
• Применяют формулы там, где есть повторения. Если элемент можно взять дважды (цифры в PIN-коде, броски кубика), \(A_n^k\) и \(C_n^k\) не действуют — работает правило произведения \(n^k\).
• Считают, что \(0! = 0\). Это разрушает все формулы с \((n-k)!\) при \(k = n\): возникает деление на ноль. По определению \(0! = 1\).
• Сокращают факториалы «в лоб». Вычислять \(25!\) не нужно и невозможно в уме. Сокращайте сразу: \(\dfrac{25!}{21!} = 25 \cdot 24 \cdot 23 \cdot 22\).
• Забывают об ограничениях в условии. «Не рядом», «обязательно включить X», «первая цифра не ноль» — такие условия считают либо через дополнение (всё минус плохие), либо фиксируя нужные элементы. Игнорирование ограничения даёт завышенный ответ.
• Умножают всё подряд в комбинированных задачах. В примере 6 группы мальчиков и девочек независимы, поэтому произведение верно. Но если группы пересекаются или условие «ровно 3» заменено на «не менее 3», задачу нужно разбить на случаи и сложить результаты.

Вывод

Комбинаторика держится на двух правилах (сумма и произведение) и трёх формулах (\(P_n\), \(A_n^k\), \(C_n^k\)). Формулы выводятся из правил, а не запоминаются по отдельности. Главный навык темы — не считать факториалы, а правильно задавать два вопроса: все ли элементы берём и важен ли порядок. Кто отвечает на них уверенно, тот решает комбинаторные задачи НМТ быстрее, чем читает условие. Дальше эти же числа понадобятся в темах о вероятности и биноме Ньютона, а привычка аккуратно сокращать дроби — везде, от НОД и НОК до алгебры старшей школы.

Если после этой статьи вы всё ещё колеблетесь между \(A_n^k\) и \(C_n^k\) в конкретной задаче — это нормально, критерий отрабатывается на задачах, а не на теории. Запишитесь на пробное занятие в Tutor-Math: разберём ваш тип задач и доведём выбор формулы до автоматизма.

Чем размещения отличаются от сочетаний?

Только учётом порядка. Размещения \(A_n^k\) считают наборы с разным порядком разными результатами, сочетания \(C_n^k\) — одинаковыми. Поэтому \(A_n^k = C_n^k \cdot k!\): каждое сочетание можно упорядочить \(k!\) способами. Например, выбрать 3 призёров из 10 — это \(A_{10}^{3} = 720\), а выбрать 3 участников в команду из 10 — это \(C_{10}^{3} = 120\), ровно в \(3! = 6\) раз меньше.

Почему \(0! = 1\), а не 0?

Из-за рекуррентного свойства \(n! = n \cdot (n-1)!\). При \(n = 1\) оно даёт \(1! = 1 \cdot 0!\), то есть \(0! = 1\). Содержательно: \(n!\) — количество способов упорядочить \(n\) предметов, а пустой набор упорядочивается ровно одним способом. Если бы \(0!\) равнялся нулю, формулы \(A_n^n = \frac{n!}{0!}\) и \(C_n^0 = \frac{n!}{0!\,n!}\) давали бы деление на ноль.

Как быстро понять, важен ли порядок в задаче?

Возьмите два конкретных набора из одних и тех же элементов в разном порядке и спросите: это разные результаты или один и тот же? «Староста Аня, заместитель Богдан» и «староста Богдан, заместитель Аня» — разные, значит, размещения. «Дежурные Аня и Богдан» и «дежурные Богдан и Аня» — одно и то же, значит, сочетания. Слова «место», «должность», «шифр» обычно означают порядок; «команда», «группа», «набор» — его отсутствие.

Что делать, если элементы могут повторяться?

Формулы \(P_n\), \(A_n^k\), \(C_n^k\) рассчитаны на различные элементы и не работают. Для наборов с повторениями применяют непосредственно правило произведения: если на каждой из \(k\) позиций есть \(n\) вариантов, количество наборов равно \(n^k\). Например, четырёхзначных PIN-кодов из цифр 0–9 существует \(10^4 = 10\,000\).