Комбинаторика — это раздел математики, который отвечает на вопрос «сколькими способами?». Сколько обедов можно собрать из меню, сколько паролей из четырёх цифр, сколькими способами рассадить гостей. Простыми словами, комбинаторика учит считать варианты, не выписывая их все подряд. В школе её начинают в 5–6 классе, продолжают в 9 классе и используют в 10–11 классе в теории вероятностей. На ЕГЭ комбинаторика нужна в задачах на вероятность по профильной математике и в задании 8 по информатике. Почти вся школьная комбинаторика держится на двух правилах — суммы и произведения.
Правило суммы
Если выбрать можно одно из двух: либо из первой группы ($m$ вариантов), либо из второй ($n$ вариантов), и группы не пересекаются, то всего вариантов $m + n$.
Пример. В столовой 3 супа и 4 салата. Вы берёте одно блюдо — суп или салат. Сколько вариантов? $3 + 4 = 7$.
Ключевое слово правила суммы — «или»: выбираем что-то одно из нескольких непересекающихся групп.
Правило произведения
Если выбор делается в два шага, на первом шаге есть $m$ вариантов, а на втором — $n$ вариантов при любом выборе на первом, то всего способов $m \cdot n$.
Пример. В той же столовой обед состоит из супа и салата. Суп можно выбрать тремя способами, к каждому супу — салат четырьмя способами. Обедов: $3 \cdot 4 = 12$.
Ключевое слово правила произведения — «и»: делаем выбор по шагам, один за другим. Для трёх, четырёх и более шагов правило работает так же: числа вариантов на каждом шаге перемножаются.
Дерево вариантов
Понять, почему варианты перемножаются, помогает дерево. Из начальной точки выходят ветки первого шага, из конца каждой ветки — ветки второго шага. Число концов дерева и есть число вариантов.
Для двух супов и трёх салатов получается $2 \cdot 3 = 6$ концов. Рисовать дерево целиком нужно редко, но в начале работы с темой оно помогает не перепутать правила.
Задачи на правило произведения
Задача 1. Числа с повторениями. Сколько трёхзначных чисел можно составить из цифр 1, 2, 3, 4, 5, если цифры могут повторяться?
На каждое из трёх мест подходит любая из 5 цифр: $5 \cdot 5 \cdot 5 = 125$.
Задача 2. Без повторений. А если цифры не повторяются?
На первое место — 5 вариантов, на второе — уже 4 (одна цифра занята), на третье — 3: $5 \cdot 4 \cdot 3 = 60$.
Задача 3. Ограничение на первую цифру. Сколько существует четырёхзначных чисел, все цифры которых чётные?
Чётных цифр пять: 0, 2, 4, 6, 8. Но первой цифрой не может быть 0, поэтому на первое место — 4 варианта, на остальные — по 5: $4 \cdot 5 \cdot 5 \cdot 5 = 500$.
Задача 4. Удобная хитрость. Сколько натуральных чисел от 1 до 999 не содержат цифру 5?
Допишем к коротким числам ведущие нули: 7 станет 007, 42 — 042. Тогда каждое число — это три места, и на каждое подходит одна из 9 цифр (все, кроме 5): $9^3 = 729$. Среди них есть запись 000, которая не является натуральным числом, поэтому ответ $729 - 1 = 728$.
Когда нужны оба правила
Задача 5. Сколько слов длиной не больше двух букв можно составить из букв А, Б, В? Словом считается любая последовательность букв.
Слово либо из одной буквы, либо из двух — это «или», правило суммы. Однобуквенных слов 3. Двухбуквенных по правилу произведения $3 \cdot 3 = 9$. Всего: $3 + 9 = 12$.
Так же устроено задание 8 ЕГЭ по информатике: слова из заданных букв с условиями. Только там вариантов тысячи, и считать удобнее программой. Где писать такой код, мы разобрали в статье про среду разработки Python для ЕГЭ.
Что дальше: перестановки, размещения, сочетания
Из правила произведения выводятся три формулы, которые проходят в 9–11 классе:
| Понятие | Что считаем | Формула |
|---|---|---|
| перестановки | сколькими способами упорядочить $n$ разных предметов | $P_n = n!$ |
| размещения | сколько упорядоченных наборов по $k$ из $n$ | $A_n^k = \dfrac{n!}{(n-k)!}$ |
| сочетания | сколько наборов по $k$ из $n$ без учёта порядка | $C_n^k = \dfrac{n!}{k!\,(n-k)!}$ |
Задача 2 выше — это размещения: $A_5^3 = 5 \cdot 4 \cdot 3 = 60$. Формулы удобны, но если понимать правило произведения, их легко восстановить самостоятельно.
Где ошибаются
где теряют баллы
Складывают там, где нужно умножать. Проверьте себя вопросом: выбор делается «или» (одно из) — сумма, «и» (по шагам) — произведение.
Где теряют баллы. Забывают, что число не начинается с нуля, и считают 0 возможной первой цифрой.
Где теряют баллы. Не учитывают, что без повторений число вариантов на каждом следующем шаге уменьшается.
Задачи для самопроверки
Задача 1. Флаг состоит из трёх горизонтальных полос разных цветов. Сколько разных флагов можно сшить, если есть ткань пяти цветов?
Задача 2. Сколько существует пятизначных чисел, оканчивающихся на 0?
Задача 3. Сколько слов длиной 4 можно составить из букв К, О, Т (буквы могут повторяться)? Сколько из них начинаются с буквы К?
Ответы
Задача 1. $5 \cdot 4 \cdot 3 = 60$.
Задача 2. Первая цифра — 9 вариантов (1–9), вторая, третья и четвёртая — по 10, пятая — только 0: $9 \cdot 10 \cdot 10 \cdot 10 = 9000$.
Задача 3. $3^4 = 81$ слово; если первая буква К фиксирована, остаётся $3^3 = 27$.
Коротко о главном
Комбинаторика в математике — это подсчёт вариантов. Если выбираем одно «или» другое из непересекающихся групп, варианты складываются. Если выбираем по шагам — первое «и» второе, варианты перемножаются. Дерево вариантов показывает, почему это так. Перестановки, размещения и сочетания — частные случаи правила произведения.
Если комбинаторика и вероятность пока не складываются в систему, их удобно разобрать на занятиях: на курсе математики по школьной программе каждую неделю — занятие по теме и ежедневная практика. Для подготовки к экзамену — курс ЕГЭ по профильной математике.
Материал подготовил Максим Муратов, преподаватель математики, физики и информатики с 2009 года. Об авторе
