08. Правила суммы и произведения: как считать, не перечисляя
Комбинаторика отвечает на вопрос «сколькими способами?» и считает способы, не выписывая их по одному. Почти всё держится на двух правилах: «и затем» — числа вариантов умножаем, «или» — складываем.
Что пригодится из прошлого: двоичные коды — там число вариантов уже удваивалось с каждым новым местом; число элементов объединения — там количества элементов складывали и вычитали лишнее. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
О чём эта наука
Комбинаторика — раздел математики, который изучает задачи выбора и расположения элементов из заданного набора элементов при заданных ограничениях. Она тесно связана с теорией чисел, алгеброй, геометрией, теорией графов и теорией вероятностей: в каждой из них приходится считать, сколько существует объектов нужного вида.
Вопрос почти всегда один: «Сколько существует способов…?» Нужно найти число, а не выписать все варианты. Вот почему списка недостаточно:
- код замка из 4 цифр — 10 000 вариантов;
- рассадка 10 человек в ряд — 3 628 800 вариантов;
- все подмножества множества из 30 элементов — 1 073 741 824 вариантов.
Выписать такой список руками невозможно, а посчитать можно за несколько секунд. Этому и учит комбинаторика. Два самых простых правила подсчёта — прямо в этой главе, а факториал и степени двойки из этого списка появятся в следующих.
Правило произведения: «и затем»
У вас две футболки (красная и синяя) и три пары брюк (чёрные, серые, бежевые). Сколько разных нарядов можно собрать?
Соберём наряд в два шага: сначала выбираем футболку, затем брюки. Нарисуем все возможности деревом:
старт
├── красная футболка
│ ├── чёрные брюки → наряд 1
│ ├── серые брюки → наряд 2
│ └── бежевые брюки → наряд 3
└── синяя футболка
├── чёрные брюки → наряд 4
├── серые брюки → наряд 5
└── бежевые брюки → наряд 6
У дерева две большие ветки — по числу футболок. На каждой ветке растут одни и те же три продолжения — по числу брюк. Поэтому всего
Вот почему умножаем. Две ветки по три листа — это «два раза по три». Умножение и есть короткая запись такого повторяющегося сложения: .
Правило произведения. Пусть действие состоит из шагов, которые выполняют один за другим. Если первый шаг можно сделать способами, второй — способами, третий — способами и так далее до -го шага, причём число способов каждого шага не зависит от того, как выполнены предыдущие, то всё действие можно выполнить
способами.
Для двоичных кодов из первой главы так и получалось: на каждом из мест два варианта, поэтому .
Метод ячеек
Чтобы не запутаться, нарисуйте столько ячеек, сколько шагов, и под каждой запишите, сколько у шага вариантов. Затем перемножьте числа под ячейками.
Задача. Сколько существует чётных трёхзначных чисел, то есть чисел от до с чётной последней цифрой?
сотни десятки единицы
┌───────┐ ┌───────┐ ┌───────┐
│ │ │ │ │ │
└───────┘ └───────┘ └───────┘
1,2,…,9 0,1,…,9 0,2,4,6,8
9 10 5
Первая цифра не может быть нулём: вариантов. На вторую ограничений нет: вариантов. Последняя — одна из пяти чётных цифр. Ответ:
Что значит «число способов не зависит от предыдущих шагов»
Задача. Сколько существует трёхзначных чисел, у которых все цифры различны?
сотни десятки единицы
┌───────┐ ┌───────┐ ┌───────┐
│ │ │ │ │ │
└───────┘ └───────┘ └───────┘
цифры 1–9 0–9 без 0–9 без
цифры двух уже
сотен стоящих
9 9 8
Какие именно цифры доступны на втором шаге, зависит от первого: нельзя повторить уже выбранную. Но сколько их — всегда : десять цифр без одной. Если сотни — цифра , для десятков остаются ; если цифра , остаются ; в обоих случаях девять вариантов. Именно постоянство числа вариантов разрешает умножать:
Правило суммы: «или»
Теперь другая история. Из города A в город B можно добраться либо на автобусе (3 разных рейса), либо на поезде (2 разных поезда). Сколько способов выбрать поездку?
Мы выбираем один вариант из двух групп, у которых нет общих вариантов:
┌─ автобус ─┐ ┌─ поезд ──┐
│ рейс 1 │ │ поезд 1 │
│ рейс 2 │ │ поезд 2 │
│ рейс 3 │ │ │
└───────────┘ └──────────┘
3 способа + 2 способа
= 5 способов
Правило суммы. Если все объекты разбиты на группы и никакой объект не входит в две группы сразу, то число всех объектов равно сумме чисел объектов в группах:
Условие «нет общих объектов» существенно. Это та же формула из главы про число элементов объединения, только для множеств без общих элементов, когда .
Что будет, если общие объекты есть. Посчитаем числа от до , которые кратны или :
кратны 2: 2 4 [6] 8 10 → 5
кратны 3: 3 [6] 9 → 3
число 6 стоит в обоих списках
Просто сложить нельзя: число посчитано дважды. Вычитаем общее: , и действительно подходят числа . Для таких задач нужен отдельный приём — включения и исключения. Пока запомним: правило суммы работает только для непересекающихся групп.
Слова-подсказки
- слова «и», «затем», «после этого», «сначала … потом …» — числа вариантов умножают;
- слова «или», «либо», «в одном из случаев» — числа вариантов складывают.
Слова — только подсказка: всегда проверяйте, что на самом деле происходит. Выбор «автобус или поезд» — это один выбор из двух групп, поэтому . А поездка «туда на автобусе и обратно на поезде» — два шага подряд, поэтому .
Оба правила вместе
Задача. Сколько существует чётных трёхзначных чисел с различными цифрами?
Сразу перемножить числа «сотни, десятки, единицы» не получится: если последняя цифра — нуль, то на сотни остаётся вариантов, а если не нуль — только . Разобьём все числа на два непересекающихся случая по последней цифре и в каждом применим правило произведения:
чётные трёхзначные числа
с разными цифрами
│
├─ случай 1: последняя цифра 0
│ последняя — 1 способ
│ сотни — 9 способов
│ десятки — 8 способов
│ 1 · 9 · 8 = 72
│
└─ случай 2: последняя 2, 4, 6, 8
последняя — 4 способа
сотни — 8 способов
десятки — 8 способов
4 · 8 · 8 = 256
В случае 2 сотни не могут быть нулём и не могут повторять последнюю цифру: из девяти цифр убираем одну, остаётся . Десятки — любая из десяти цифр, кроме двух уже стоящих: тоже . Здесь удобно начать с последней цифры: от неё зависит, сколько вариантов останется для остальных. Вообще, начинайте с того шага, у которого больше всего ограничений. Случаи не пересекаются (последняя цифра разная), поэтому складываем:
Главный приём курса: превращаем объекты в коды
В первой главе мы не выписывали все подмножества: каждому подмножеству мы сопоставили код из нулей и единиц, а затем посчитали коды. Два набора содержат поровну объектов, если их можно поставить в пары «один к одному» — без остатков и повторов. Это приём почти всего курса:
- подмножества множества — двоичные коды (глава 1);
- выборки из набора элементов — слова из букв (глава 10);
- сочетания с повторениями — слова из единиц и звёздочек (глава 16);
- пути по клетчатой решётке — слова из нулей и единиц (глава 19).
Когда задача кажется сложной, спросите себя: как записать один объект короткой «анкетой» и сколько существует разных анкет?
Частые ошибки
- Сложить вместо умножения. Если шаги выполняются друг за другом, варианты не «добавляются», а повторяются на каждой ветке. Два цвета футболки и три вида брюк дают , а не .
- Умножить вместо сложения. Если выбирают одно из нескольких направлений («автобус или поезд»), ветки не растут одна из другой.
- Посчитать один объект дважды. Если группы пересекаются, общие объекты нужно учесть один раз.
- Забыть, что число вариантов может сокращаться. «Все цифры различны» — на каждом шаге вариантов меньше, чем на предыдущем.
Проверь себя
1. В кафе четыре вида супа, пять вторых блюд и три напитка. Сколько существует разных обедов «суп, второе, напиток»?
Решение
Три шага подряд: способа, затем , затем . По правилу произведения
2. Сколько существует трёхзначных чисел, у которых все цифры нечётные?
Решение
Нечётных цифр пять: . Нуль не мешает, поэтому для каждой из трёх позиций ровно вариантов:
3. Пароль состоит либо из одной заглавной латинской буквы и двух цифр (в таком порядке), либо из трёх цифр. Сколько существует паролей? В латинском алфавите букв.
Решение
Паролей двух видов, общих у них нет: у первых первый символ — буква, у вторых — цифра. Поэтому складываем. Первый вид: три шага, . Второй вид: . Всего
4. Сколько существует четырёхзначных чисел, у которых все цифры различны?
Решение
Первая цифра — одна из (нуль нельзя). Вторая — любая из десяти, кроме выбранной: . Третья — , четвёртая — :
Итог
- Шаги идут друг за другом → перемножаем числа вариантов; важно, что число вариантов каждого шага не зависит от предыдущих выборов.
- Выбираем одно из нескольких непересекающихся направлений → складываем.
- Сложная задача часто распадается на несколько случаев (сумма), а каждый случай — на шаги (произведение).
- Почти любую задачу удобно превратить в подсчёт «кодов» — коротких записей, по которым объект восстанавливается однозначно.
Где читать дальше
- Р. Н. Тоноян, «Дискретная математика. Курс лекций» (на армянском языке: Ռ. Ն. Տոնոյան, «Դիսկրետ մաթեմատիկայի դասընթաց»), Ереван, ЕГУ, 1999.
- Н. Я. Виленкин, «Комбинаторика», М.: Наука, 1969.
- М. Холл, «Комбинаторика», М.: Мир, 1970.
- Ф. А. Новиков, «Дискретная математика для программистов», СПб.: Питер, 2008.
- Дж. А. Андерсон, «Дискретная математика и комбинаторика», М.: Вильямс, 2003.
