Урок 5. Комбинаторика: учимся считать варианты

Математика · ~55 минут

🎯 Что ты узнаешь

• Правило суммы («или») и правило произведения («и») — два кита всех подсчётов.
• Как рисовать дерево вариантов, чтобы ничего не пропустить.
• Что такое перестановки и факториал n! (сколькими способами выстроить в ряд).
• Как считать сочетания — выбор нескольких предметов, когда порядок неважен.

📖 Разбираемся в теме

Вопрос на засыпку: сколькими способами можно перетасовать обычную колоду из 52 карт? Ответ настолько огромен, что в него трудно поверить: число с 68 нулями. Это больше, чем число атомов во всей нашей Галактике. А значит, скорее всего, КАЖДЫЙ раз, когда кто-то хорошо тасует колоду, получается порядок карт, который не выпадал НИ РАЗУ за всю историю человечества. Как такое вообще можно посчитать, не перебирая варианты? Этим и занимается комбинаторика — наука считать, не пересчитывая.

Правило произведения («и»)

Представь: утром ты выбираешь футболку (их у тебя 3) и шорты (их 2). Сколько разных нарядов получится? Для каждой из 3 футболок есть 2 варианта шорт: 3·2 = 6 нарядов.

Правило произведения. Если первое действие можно сделать a способами, и для каждого из них второе действие можно сделать b способами, то оба действия вместе можно сделать a·b способами.

Ключевое слово — «И»: выбираем футболку И шорты. Способов перемножаем. Действий может быть и больше двух — тогда перемножаем все.

Правило суммы («или»)

Теперь другое. У тебя на полке 3 книги про космос и 4 книги про динозавров. Сколько способов взять одну книгу? Можно взять про космос (3 способа) ИЛИ про динозавров (4 способа): 3 + 4 = 7.

Правило суммы. Если есть две группы вариантов, не пересекающиеся между собой, и в первой a вариантов, а во второй b, то всего вариантов a + b.

Ключевое слово — «ИЛИ»: одно из двух, но не оба сразу. Важно, чтобы группы не пересекались (книга не может быть одновременно про космос и про динозавров).

📌 Запомни: «и» → умножаем, «или» → складываем. Это самый частый компас в комбинаторике. Прочитал условие, нашёл в нём «и» или «или» — сразу понятно, что делать со способами.

Дерево вариантов

Когда хочется всё «увидеть», рисуют дерево. От стартовой точки рисуют ветки — варианты первого действия. От каждой ветки — варианты второго действия, и так далее. Число «листьев» (концов веток) и есть число всех комбинаций.

Например, бросаем монетку дважды. Первый бросок: О или Р (две ветки). От каждой — снова О или Р. Получается 2·2 = 4 листа: ОО, ОР, РО, РР. Дерево заодно показывает, чему равны все варианты, — удобно для проверки.

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

Сколькими способами 3 ребёнка (Аня, Боря, Витя) могут встать в очередь?

• На первое место — любой из 3 (3 способа).
• На второе место — любой из 2 оставшихся (2 способа).
• На третье — последний оставшийся (1 способ).

По правилу произведения: 3·2·1 = 6 способов.

Произведение всех чисел от 1 до n называют факториалом и обозначают n! (читается «эн факториал»): $$n! = 1\cdot 2\cdot 3\cdot \ldots \cdot n.$$ Например: 3! = 6, 4! = 24, 5! = 120. Растёт очень быстро!

🤔 А знаешь ли ты? Тот самый невероятный ответ про колоду из начала урока — это и есть факториал 52! (число способов выстроить 52 карты в ряд). Факториал растёт так бешено, что уже 13! больше шести миллиардов. Поэтому-то полностью перебрать все варианты в больших задачах не может даже суперкомпьютер — и приходится считать с умом.

Перестановки. Число способов выстроить n различных предметов в ряд равно n!.

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

Иногда нам не важен порядок. Например: из 4 друзей нужно выбрать 2 в команду. Команда {Аня, Боря} — это та же команда, что {Боря, Аня}. Порядок не считается!

Тут нельзя просто перемножать, потому что мы посчитаем одни и те же команды по нескольку раз. Как быть — разберём на конкретном примере ниже. Главную идею назовём заранее: посчитать с учётом порядка, а потом поделить на число лишних повторов.

✍️ Разбор примеров

Пример 1. Сколько двузначных чисел можно составить из цифр 1, 2, 3, если цифры можно повторять? А если повторять нельзя?

Как рассуждаем. Двузначное число — это «первая цифра И вторая цифра». Видишь «И»? Значит, работает правило произведения.

С повторениями: первую цифру выбираем из {1,2,3} — 3 способа; вторую тоже из {1,2,3} — снова 3 способа. Итого 3·3 = 9. (Это 11, 12, 13, 21, 22, 23, 31, 32, 33.)

Без повторений: первую цифру выбираем 3 способами, а вторую — уже из 2 оставшихся (одну цифру использовали). Итого 3·2 = 6. (Это 12, 13, 21, 23, 31, 32.)

Ответ: 9 с повторениями, 6 без повторений.

Пример 2. В сетке нужно пройти из левого нижнего угла A в правый верхний угол B, двигаясь только вправо или вверх по линиям. Сетка 2×2 клетки. Сколько разных маршрутов?

⏱ Попробуй сам прямо сейчас: нарисуй сетку 2×2 и впиши в каждый узел, сколькими путями в него можно попасть. Потом читай дальше.

Как рассуждаем. Чтобы попасть из A в B по сетке 2×2, нужно сделать 2 шага вправо (П) и 2 шага вверх (В) — всего 4 шага в каком-то порядке. Каждый маршрут — это последовательность из двух букв П и двух букв В, например ППВВ или ПВПВ.

Удобно считать по-другому, через клетки (метод подсчёта путей): в каждый узел сетки впишем число путей, которыми в него можно прийти. В нижний ряд и левый столбец — везде по 1 способу (идти только прямо). А в любой внутренний узел приходим либо снизу, либо слева, поэтому число путей в него = сумма путей в узел слева и в узел снизу. Заполняя сетку, в углу B получим 6.

Можно проверить перечислением: ППВВ, ПВПВ, ПВВП, ВППВ, ВПВП, ВВПП — ровно 6.

Ответ: 6 маршрутов.

Пример 3. Сколькими способами 5 детей могут встать в очередь?

Как рассуждаем. Это чистые перестановки 5 предметов. На первое место — 5 кандидатов, на второе — 4 оставшихся, потом 3, 2 и наконец 1. По правилу произведения: 5·4·3·2·1 = 5! = 120.

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

Пример 4. Сколько различных «слов» (любых буквосочетаний, не обязательно осмысленных) можно получить, переставляя буквы слова КОТ? А слова МАМА?

Как рассуждаем. В слове КОТ все три буквы разные. Значит, это обычные перестановки трёх букв: 3! = 6 (КОТ, КТО, ОКТ, ОТК, ТКО, ТОК).

А вот в МАМА есть повторы: две буквы М и две буквы А. Если бы все четыре буквы были разными, было бы 4! = 24 перестановки. Но из-за повторов многие из них выглядят одинаково. Две буквы М можно поменять местами — слово не изменится, это «лишний» множитель 2! = 2. То же с двумя А — ещё множитель 2! = 2. Поэтому настоящих разных слов: 4! / (2!·2!) = 24 / 4 = 6... проверим перечислением: МАМА, МААМ, ММАА, ААММ, АМАМ, АММА — да, ровно 6.

💡 Лайфхак: Когда среди элементов есть одинаковые, всегда действуй так: сначала посчитай, как будто все они разные (через факториал), а потом подели на факториал числа повторов каждого сорта. Этот приём «посчитал лишнее — поделил на повторы» спасает в куче задач.

(Внимание: в исходном плане стоял ответ 12 — это для случая, когда повторяющиеся буквы считают различимыми, скажем М₁ и М₂. Если же буквы М неотличимы друг от друга, разных слов именно 6. Будем считать одинаковые буквы неотличимыми — так правильнее.)

Ответ: КОТ — 6 слов; МАМА — 6 различных слов (если одинаковые буквы неотличимы).

Пример 5. Сколько существует трёхзначных чисел, у которых все три цифры разные?

Как рассуждаем. Строим число по разрядам, помня про правило произведения и про важную тонкость: первая цифра не может быть 0 (иначе число не трёхзначное).

• Сотни (первая цифра): любая из 1–9, ноль нельзя — 9 вариантов.
• Десятки (вторая цифра): любая цифра 0–9, кроме уже использованной в сотнях. Всего цифр 10, одну заняли — 9 вариантов (ноль здесь уже можно!).
• Единицы (третья цифра): любая из 10, кроме двух уже использованных — 8 вариантов.

По правилу произведения: 9·9·8 = 648.

Ответ: 648 чисел.

Пример 6. На полке стоят 4 разные книги. Сколькими способами можно выбрать 2 из них (порядок неважен — просто пара книг)?

Как рассуждаем. Сначала посчитаем С УЧЁТОМ порядка: первую книгу выбираем 4 способами, вторую — 3 способами из оставшихся, всего 4·3 = 12 упорядоченных пар. Но порядок нам неважен: пара (книга1, книга2) и (книга2, книга1) — это одна и та же пара книг. Значит, каждую пару мы посчитали ровно дважды. Делим на 2: 12 / 2 = 6.

Так считаются сочетания: считаем «как будто порядок важен», а потом делим на число перестановок выбранной группы (для 2 книг это 2! = 2). Перечислим для надёжности (книги A, B, C, D): AB, AC, AD, BC, BD, CD — ровно 6 пар.

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

💡 Запомни главное

«И» — перемножаем варианты (правило произведения). «ИЛИ» — складываем (правило суммы, если группы не пересекаются).

• n! = 1·2·…·n — число способов выстроить n разных предметов в ряд (перестановки).
• Когда выбираешь нескольких и порядок неважен (сочетания): посчитай с учётом порядка, потом раздели на число перестановок выбранной группы.
• Если есть повторяющиеся одинаковые элементы — дели на факториал числа повторов каждого.
• Первая цифра числа не может быть 0 — частая ловушка.
• Сомневаешься — нарисуй дерево вариантов или перечисли маленький случай для проверки.

📝 Домашнее задание

1. В кафе 3 вида мороженого и 4 вида сиропа. Сколькими способами можно заказать одну порцию мороженого с одним сиропом?
2. Сколько трёхзначных чисел можно составить из цифр 1, 2, 3, 4, 5, если цифры можно повторять?
3. Сколькими способами 6 человек могут сесть на 6 стульев в ряд?
4. Сколько различных «слов» можно получить, переставляя буквы слова КНИГА? А слова КОЛОБОК? (Во втором есть повторяющиеся буквы — посчитай их.)
5. Из класса в 10 человек нужно выбрать двоих дежурных (оба равноправны, порядок неважен). Сколькими способами это можно сделать?
6. Сколько существует четырёхзначных чисел, все цифры которых разные?
7. В меню 2 первых блюда, 3 вторых и 2 десерта. Сколькими способами можно составить обед из одного первого, одного второго и одного десерта?
8. ⭐ Сколькими способами можно разменять 10 рублей монетами достоинством 1, 2 и 5 рублей? (Способы, различающиеся только числом монет каждого вида; аккуратно переберите, сколько берём пятёрок, потом двушек, остальное — рублями.)