bulgakov

08. Правила суммы и произведения: как считать, не перечисляя

Комбинаторика отвечает на вопрос «сколькими способами?» и считает способы, не выписывая их по одному. Почти всё держится на двух правилах: «и затем» — числа вариантов умножаем, «или» — складываем.

Что пригодится из прошлого: двоичные коды — там число вариантов уже удваивалось с каждым новым местом; число элементов объединения — там количества элементов складывали и вычитали лишнее. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

О чём эта наука

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

Вопрос почти всегда один: «Сколько существует способов…?» Нужно найти число, а не выписать все варианты. Вот почему списка недостаточно:

  • код замка из 4 цифр — 10 000 вариантов;
  • рассадка 10 человек в ряд — 3 628 800 вариантов;
  • все подмножества множества из 30 элементов — 1 073 741 824 вариантов.

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

Правило произведения: «и затем»

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

Соберём наряд в два шага: сначала выбираем футболку, затем брюки. Нарисуем все возможности деревом:

Схема
старт
├── красная футболка
│   ├── чёрные брюки   → наряд 1
│   ├── серые брюки    → наряд 2
│   └── бежевые брюки  → наряд 3
└── синяя футболка
    ├── чёрные брюки   → наряд 4
    ├── серые брюки    → наряд 5
    └── бежевые брюки  → наряд 6

У дерева две большие ветки — по числу футболок. На каждой ветке растут одни и те же три продолжения — по числу брюк. Поэтому всего

3+3=6 нарядов.3+3=6\text{ нарядов}.

Вот почему умножаем. Две ветки по три листа — это «два раза по три». Умножение и есть короткая запись такого повторяющегося сложения: 3+3=2⋅33+3=2\cdot3.

Правило произведения. Пусть действие состоит из шагов, которые выполняют один за другим. Если первый шаг можно сделать m1m_1 способами, второй — m2m_2 способами, третий — m3m_3 способами и так далее до rr-го шага, причём число способов каждого шага не зависит от того, как выполнены предыдущие, то всё действие можно выполнить

m1⋅m2⋅m3⋯mr\boxed{m_1\cdot m_2\cdot m_3\cdots m_r}

способами.

Для двоичных кодов из первой главы так и получалось: на каждом из nn мест два варианта, поэтому 2⋅2⋯2=2n2\cdot2\cdots2=2^n.

Метод ячеек

Чтобы не запутаться, нарисуйте столько ячеек, сколько шагов, и под каждой запишите, сколько у шага вариантов. Затем перемножьте числа под ячейками.

Задача. Сколько существует чётных трёхзначных чисел, то есть чисел от 100100 до 998998 с чётной последней цифрой?

  сотни     десятки    единицы
┌───────┐  ┌───────┐  ┌───────┐
│       │  │       │  │       │
└───────┘  └───────┘  └───────┘
 1,2,…,9    0,1,…,9   0,2,4,6,8
    9          10         5

Первая цифра не может быть нулём: 99 вариантов. На вторую ограничений нет: 1010 вариантов. Последняя — одна из пяти чётных цифр. Ответ:

9⋅10⋅5=450.9\cdot10\cdot5=450.

Что значит «число способов не зависит от предыдущих шагов»

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

  сотни     десятки    единицы
┌───────┐  ┌───────┐  ┌───────┐
│       │  │       │  │       │
└───────┘  └───────┘  └───────┘
цифры 1–9   0–9 без    0–9 без
             цифры     двух уже
             сотен     стоящих
    9          9          8

Какие именно цифры доступны на втором шаге, зависит от первого: нельзя повторить уже выбранную. Но сколько их — всегда 99: десять цифр без одной. Если сотни — цифра 55, для десятков остаются 0,1,2,3,4,6,7,8,90,1,2,3,4,6,7,8,9; если цифра 11, остаются 0,2,3,…,90,2,3,\dots,9; в обоих случаях девять вариантов. Именно постоянство числа вариантов разрешает умножать:

9⋅9⋅8=648.9\cdot9\cdot8=648.

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

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

Мы выбираем один вариант из двух групп, у которых нет общих вариантов:

┌─ автобус ─┐  ┌─ поезд ──┐
│ рейс 1    │  │ поезд 1  │
│ рейс 2    │  │ поезд 2  │
│ рейс 3    │  │          │
└───────────┘  └──────────┘
 3 способа   +  2 способа
       = 5 способов

Правило суммы. Если все объекты разбиты на группы и никакой объект не входит в две группы сразу, то число всех объектов равно сумме чисел объектов в группах:

N=N1+N2+⋯+Nk.\boxed{N=N_1+N_2+\cdots+N_k}.

Условие «нет общих объектов» существенно. Это та же формула ∣A∪B∣=∣A∣+∣B∣|A\cup B|=|A|+|B| из главы про число элементов объединения, только для множеств без общих элементов, когда ∣A∩B∣=0|A\cap B|=0.

Что будет, если общие объекты есть. Посчитаем числа от 11 до 1010, которые кратны 22 или 33:

Схема
кратны 2:  2  4  [6]  8  10  → 5
кратны 3:  3  [6]  9  → 3
число 6 стоит в обоих списках

Просто сложить 5+3=85+3=8 нельзя: число 66 посчитано дважды. Вычитаем общее: 5+3−1=75+3-1=7, и действительно подходят числа 2,3,4,6,8,9,102,3,4,6,8,9,10. Для таких задач нужен отдельный приём — включения и исключения. Пока запомним: правило суммы работает только для непересекающихся групп.

Слова-подсказки

  • слова «и», «затем», «после этого», «сначала … потом …» — числа вариантов умножают;
  • слова «или», «либо», «в одном из случаев» — числа вариантов складывают.

Слова — только подсказка: всегда проверяйте, что на самом деле происходит. Выбор «автобус или поезд» — это один выбор из двух групп, поэтому 3+23+2. А поездка «туда на автобусе и обратно на поезде» — два шага подряд, поэтому 3⋅2=63\cdot2=6.

Оба правила вместе

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

Сразу перемножить числа «сотни, десятки, единицы» не получится: если последняя цифра — нуль, то на сотни остаётся 99 вариантов, а если не нуль — только 88. Разобьём все числа на два непересекающихся случая по последней цифре и в каждом применим правило произведения:

чётные трёхзначные числа
с разными цифрами
│
├─ случай 1: последняя цифра 0
│    последняя  — 1 способ
│    сотни      — 9 способов
│    десятки    — 8 способов
│    1 · 9 · 8 = 72
│
└─ случай 2: последняя 2, 4, 6, 8
     последняя  — 4 способа
     сотни      — 8 способов
     десятки    — 8 способов
     4 · 8 · 8 = 256

В случае 2 сотни не могут быть нулём и не могут повторять последнюю цифру: из девяти цифр 1,…,91,\dots,9 убираем одну, остаётся 88. Десятки — любая из десяти цифр, кроме двух уже стоящих: тоже 88. Здесь удобно начать с последней цифры: от неё зависит, сколько вариантов останется для остальных. Вообще, начинайте с того шага, у которого больше всего ограничений. Случаи не пересекаются (последняя цифра разная), поэтому складываем:

72+256=328.72+256=328.

Главный приём курса: превращаем объекты в коды

В первой главе мы не выписывали все подмножества: каждому подмножеству мы сопоставили код из нулей и единиц, а затем посчитали коды. Два набора содержат поровну объектов, если их можно поставить в пары «один к одному» — без остатков и повторов. Это приём почти всего курса:

  • подмножества множества — двоичные коды (глава 1);
  • выборки из набора элементов — слова из букв (глава 10);
  • сочетания с повторениями — слова из единиц и звёздочек (глава 16);
  • пути по клетчатой решётке — слова из нулей и единиц (глава 19).

Когда задача кажется сложной, спросите себя: как записать один объект короткой «анкетой» и сколько существует разных анкет?

Частые ошибки

  • Сложить вместо умножения. Если шаги выполняются друг за другом, варианты не «добавляются», а повторяются на каждой ветке. Два цвета футболки и три вида брюк дают 2⋅32\cdot3, а не 2+32+3.
  • Умножить вместо сложения. Если выбирают одно из нескольких направлений («автобус или поезд»), ветки не растут одна из другой.
  • Посчитать один объект дважды. Если группы пересекаются, общие объекты нужно учесть один раз.
  • Забыть, что число вариантов может сокращаться. «Все цифры различны» — на каждом шаге вариантов меньше, чем на предыдущем.

Проверь себя

1. В кафе четыре вида супа, пять вторых блюд и три напитка. Сколько существует разных обедов «суп, второе, напиток»?

Решение

Три шага подряд: 44 способа, затем 55, затем 33. По правилу произведения

4⋅5⋅3=60.4\cdot5\cdot3=60.

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

Решение

Нечётных цифр пять: 1,3,5,7,91,3,5,7,9. Нуль не мешает, поэтому для каждой из трёх позиций ровно 55 вариантов:

5⋅5⋅5=125.5\cdot5\cdot5=125.

3. Пароль состоит либо из одной заглавной латинской буквы и двух цифр (в таком порядке), либо из трёх цифр. Сколько существует паролей? В латинском алфавите 2626 букв.

Решение

Паролей двух видов, общих у них нет: у первых первый символ — буква, у вторых — цифра. Поэтому складываем. Первый вид: три шага, 26⋅10⋅10=260026\cdot10\cdot10=2600. Второй вид: 10⋅10⋅10=100010\cdot10\cdot10=1000. Всего

2600+1000=3600.2600+1000=3600.

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

Решение

Первая цифра — одна из 99 (нуль нельзя). Вторая — любая из десяти, кроме выбранной: 99. Третья — 88, четвёртая — 77:

9⋅9⋅8⋅7=4536.9\cdot9\cdot8\cdot7=4536.

Итог

  • Шаги идут друг за другом → перемножаем числа вариантов; важно, что число вариантов каждого шага не зависит от предыдущих выборов.
  • Выбираем одно из нескольких непересекающихся направлений → складываем.
  • Сложная задача часто распадается на несколько случаев (сумма), а каждый случай — на шаги (произведение).
  • Почти любую задачу удобно превратить в подсчёт «кодов» — коротких записей, по которым объект восстанавливается однозначно.

Где читать дальше

  1. Р. Н. Тоноян, «Дискретная математика. Курс лекций» (на армянском языке: Ռ. Ն. Տոնոյան, «Դիսկրետ մաթեմատիկայի դասընթաց»), Ереван, ЕГУ, 1999.
  2. Н. Я. Виленкин, «Комбинаторика», М.: Наука, 1969.
  3. М. Холл, «Комбинаторика», М.: Мир, 1970.
  4. Ф. А. Новиков, «Дискретная математика для программистов», СПб.: Питер, 2008.
  5. Дж. А. Андерсон, «Дискретная математика и комбинаторика», М.: Вильямс, 2003.
ПрактикаЗагружаем тест…