Комбинаторика: формулы перестановок и сочетаний

Q: Чему равен 0!?

По определению 0! = 1. Это соглашение нужно, чтобы формулы работали при k = n: например, C_5^5 = \frac{5!}{5! \cdot 0!} = 1 — выбрать все 5 элементов можно одним способом.

Q: Что такое треугольник Паскаля?

Это таблица чисел сочетаний: в строке n стоят C_n^0, C_n^1, \ldots, C_n^n, а каждое число равно сумме двух над ним. Например, строка 4 — это 1, 4, 6, 4, 1.

Зачем комбинаторика на экзамене

Комбинаторика — это раздел математики о подсчёте числа вариантов: сколькими способами можно выбрать, расставить или составить объекты. На экзамене она нужна прежде всего для задач на вероятность.

Комбинаторика и формулы подсчёта не выделены в отдельный номер ни в ОГЭ, ни в ЕГЭ, но её приёмы встречаются в задании 10 ОГЭ и в заданиях 4–5 профильного ЕГЭ, где нужно посчитать число исходов. По ФОП основного общего образования^[1] элементы комбинаторики входят в курс вероятности и статистики, а учебник Высоцкого и Ященко^[2] вводит правило умножения раньше классической вероятности — без него многие задачи не решить. В кодификаторе ФИПИ этот материал относится к блоку вероятности и статистики. Если исходов мало, их выписывают списком, а когда вариантов сотни, без формул не обойтись.

Комбинаторика без формулы: правило умножения

Правило умножения гласит: если первый выбор можно сделать $m$ способами, а второй после него — $n$ способами, то пару выборов можно сделать $m \cdot n$ способами. Из этого правила выводятся все остальные формулы.

У ученика 4 рубашки и 3 пары брюк — комплектов $4 \cdot 3 = 12$ . Кодовый замок с тремя дисками по 10 цифр даёт $10^3 = 1000$ комбинаций. Трёхзначных чисел с различными цифрами $9 \cdot 9 \cdot 8 = 648$ : на первое место нельзя ставить ноль (9 вариантов), на второе — любая цифра, кроме первой (9 вариантов), на третье — любая из оставшихся восьми.

Правило сложения работает, когда выбирают один вариант из нескольких непересекающихся групп. Если из города в посёлок ходят 5 автобусных маршрутов и 3 электрички, способов доехать $5 + 3 = 8$ . Короткая подсказка: «и то, и другое» — умножаем, «либо то, либо другое» — складываем.

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

Перестановка — это способ расставить по порядку все $n$ различных элементов. Число перестановок равно $P_n = n! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n$ , а по соглашению $0! = 1$ .

Одна перестановка — это один конкретный порядок, например «Атанасян, Макарычев, Мордкович, Колмогоров, Пойа» для 5 книг. Все 5 книг на полке можно расставить $5! = 120$ способами: на первое место — любая из 5, на второе — из 4 оставшихся, и так далее. Очередь из 6 человек выстраивается $6! = 720$ способами. Факториал растёт очень быстро: $10! = 3\,628\,800$ , поэтому в экзаменационных задачах $n$ обычно не больше 7.

Перестановки с повторениями

Если среди элементов есть одинаковые, перестановки, отличающиеся только их обменом, совпадают. Из букв слова «МАМА» получится не $4! = 24$ , а $\frac{4!}{2! \cdot 2!} = 6$ различных буквосочетаний: МАМА, МААМ, ММАА, АМАМ, АММА, ААММ. Делим на перестановки одинаковых букв внутри каждой группы. Каждая отдельная перестановка букв А между собой не даёт нового слова, и каждая перестановка букв М — тоже.

Размещения: когда порядок важен

Размещение — это упорядоченный выбор $k$ элементов из $n$ . Число размещений $A_n^k = \frac{n!}{(n - k)!} = n(n - 1) \ldots (n - k + 1)$ — произведение $k$ убывающих множителей.

В клубе 10 человек. Нужно выбрать председателя, заместителя и секретаря. Сколькими способами это можно сделать?

Должности разные, поэтому порядок важен: Иванов-председатель и Петров-заместитель — не то же самое, что наоборот. $A_{10}^3 = 10 \cdot 9 \cdot 8 = 720$ . Ответ: 720. Обратите внимание: это то же правило умножения, просто записанное формулой.

Сочетания: когда порядок не важен

Сочетание — это неупорядоченный выбор $k$ элементов из $n$ . Число сочетаний $C_n^k = \frac{n!}{k!\,(n - k)!}$ : размещения делят на $k!$ , потому что внутри выбранной группы порядок не различается.

Из 10 учеников нужно выбрать троих для дежурства. Сколькими способами это можно сделать?

Обязанности одинаковые, значит, тройка {Аня, Боря, Вика} — один вариант, в каком бы порядке их ни назвали. $C_{10}^3 = \frac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = 120$ . Ответ: 120 — ровно в $3! = 6$ раз меньше, чем размещений из предыдущей задачи.

Классический сюжет — рукопожатия: 8 человек, каждый жмёт руку каждому, рукопожатий $C_8^2 = 28$ . Полезное свойство симметрии: $C_n^k = C_n^{n - k}$ , например выбрать 7 из 9 — то же, что выбрать 2, которые останутся: $C_9^7 = C_9^2 = 36$ .

Миф: «сочетания и размещения — это одно и то же, просто в разных учебниках по-разному называют». Неверно: размещения учитывают порядок, сочетания — нет, и при $k \ge 2$ числа различаются в $k!$ раз. В задаче про дежурных ответ 120, а не 720.

Комбинаторика: формулы в одной таблице

Чтобы выбрать формулу, ответьте на 2 вопроса: все ли элементы участвуют и важен ли порядок. Таблица ниже сводит ответы к четырём случаям.

Что делаем	Порядок	Формула	Пример
Последовательные выборы	—	$m \cdot n \cdot \ldots$	12 комплектов из 4 рубашек и 3 брюк
Расставляем все $n$ элементов	важен	$P_n = n!$	5 книг на полке — 120
Выбираем $k$ из $n$ с ролями	важен	$A_n^k = \frac{n!}{(n - k)!}$	председатель, зам, секретарь из 10 — 720
Выбираем группу $k$ из $n$	не важен	$C_n^k = \frac{n!}{k!\,(n - k)!}$	3 дежурных из 10 — 120
Выбор с повторениями	важен	$n^k$	код из 3 цифр — 1000

Одна задача — три разных ответа

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

Вариант 1. «Сколькими способами можно выбрать троих на олимпиаду?» Состав важен, порядок нет: $C_5^3 = 10$ .
Вариант 2. «Сколькими способами можно распределить золото, серебро и бронзу?» Порядок важен: $A_5^3 = 60$ .
Вариант 3. «Сколькими способами можно раздать три разные книги, если один ученик может получить несколько?» Каждая книга выбирает владельца независимо: $5^3 = 125$ .

Комбинаторика: формулы здесь одни и те же для всех трёх вопросов, отличается только модель. Полезно проверять себя сравнением: размещений всегда в $k!$ раз больше сочетаний ( $60 = 10 \cdot 6$ ), а выбор с повторениями даёт больше всего вариантов. Если перестановка внутри тройки меняет смысл ответа, это размещение; если не меняет — сочетание.

Комбинаторика в задачах на вероятность

Если в классической вероятности исходов слишком много для перебора, числа $n$ и $m$ считают формулами комбинаторики. Это главное применение темы на экзамене.

Монету бросают 5 раз. Всех исходов $2^5 = 32$ , а исходов с ровно двумя орлами $C_5^2 = 10$ — выбираем, на какие два броска пришлись орлы. Вероятность $\frac{10}{32} = 0{,}3125$ . Другой пример: в группе 16 учеников, из них 4 девушки; случайно выбирают двоих. Вероятность, что обе — девушки, равна $\frac{C_4^2}{C_{16}^2} = \frac{6}{120} = 0{,}05$ . Подробнее о самих вероятностях — в статьях классическое определение вероятности и теоремы сложения и умножения; разбор номера с такими задачами — на странице задание 5 профильного ЕГЭ.

Задачи с проверкой

Блок «Задачи с проверкой» вверху страницы содержит 9 задач на все формулы из таблицы: 8 с числовым ответом и одну с выбором варианта. Решайте на черновике, потом вводите ответ и нажимайте «Проверить».

Перед каждым ответом проговорите вслух, важен ли порядок, — это и есть главный навык темы. Кнопка «Решение» покажет, какой формулой пользовались. Возвращайтесь к блоку через несколько дней: исследование Cepeda и соавторов^[3] показывает, что распределённое повторение с интервалами эффективнее занятий подряд.

Когда готовая формула не подходит

Формулы удобны, но в 3 ситуациях они только мешают и приводят к ошибкам.

Если вариантов меньше 10, быстрее и надёжнее выписать их все списком или таблицей.
Если на элементы наложены условия (2 соседа не должны сидеть рядом, цифры идут по возрастанию), готовая формула не подходит — сначала разбейте задачу на случаи.
Если до ОГЭ меньше 3 недель, учить размещения и сочетания не обязательно: в задании 10 хватает перебора и правила умножения.

Чего делать нельзя

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

Нельзя ставить ноль на первое место при подсчёте многозначных чисел.
Нельзя считать сочетаниями выбор людей на разные должности.
Не следует вычислять большие факториалы целиком: сокращайте дробь до умножения.
Не следует забывать делить на перестановки одинаковых элементов.
Не стоит применять правило умножения, если число вариантов второго шага зависит от первого по-разному.

Источники

[1] Федеральная образовательная программа основного общего образования (утв. приказом Минпросвещения России от 18.05.2023 № 370).

[2] Высоцкий И. Р., Ященко И. В. Математика. Вероятность и статистика. 7–9 классы. — М.: Просвещение.

[3] Cepeda N. J., Pashler H., Vul E., Wixted J. T., Rohrer D. Distributed practice in verbal recall tasks: a review and quantitative synthesis // Psychological Bulletin. 2006. Vol. 132, No. 3. P. 354–380.

Вопросы и ответы

Как запомнить, когда сочетания, а когда размещения?

Представьте, что выбранных людей фотографируют. Если на фото важно, кто где стоит (должности, места, призовые места), — размещения. Если важен только состав группы — сочетания.

Чему равен 0!?

По определению $0! = 1$ . Это соглашение нужно, чтобы формулы работали при $k = n$ : например, $C_5^5 = \frac{5!}{5! \cdot 0!} = 1$ — выбрать все 5 элементов можно одним способом.

Дают ли формулы на экзамене?

Рассчитывать на подсказку не стоит: формулы проще помнить или выводить из правила умножения — это занимает несколько секунд.

Нужна ли комбинаторика для базового ЕГЭ?

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

Что такое треугольник Паскаля?

Это таблица чисел сочетаний: в строке $n$ стоят $C_n^0, C_n^1, \ldots, C_n^n$ , а каждое число равно сумме двух над ним. Например, строка 4 — это 1, 4, 6, 4, 1.

Как проверить ответ в задаче на подсчёт вариантов?

Решите упрощённую версию с маленькими числами и выпишите варианты руками. Если формула дала то же число, что и перебор, ей можно доверять и для больших чисел.