Принципы счёта: «и затем» перемножается, «или» складывается

У вас 4 рубашки и 3 пары брюк. Сколько нарядов? Представьте дерево выборов: из корня растут 4 ветви — по одной на рубашку; из каждой из них растут 3 ветви — по одной на пару брюк. Посчитайте листья: 4 группы по 3, итого 12. Это правило произведения: когда задача распадается на последовательные этапы — сделай этот выбор, а затем тот — и число вариантов на каждом этапе не зависит от сделанного ранее, итог равен произведению количеств по этапам.

Когда вы видите вложенный цикл, спросите себя: каждый уровень — независимое «а затем»? Если да, вы можете перемножить количества на каждом уровне — и не запускать код. Код говорит на этом правиле свободно — каждый вложенный цикл и есть умножение:

const browsers = ["chrome", "firefox", "safari"];        // 3 варианта
const oses = ["ubuntu", "macos", "windows", "alpine"];   // 4 варианта
const locales = ["en", "ru"];                            // 2 варианта

let jobs = 0;
for (const b of browsers)      // выбрать браузер, А ЗАТЕМ…
  for (const o of oses)        //   …выбрать ОС, А ЗАТЕМ…
    for (const l of locales)   //     …выбрать локаль
      jobs++;

console.log(jobs);             // 3 · 4 · 2 = 24 — по джобу на каждый лист дерева

Правило произведения оценивает пространство паролей. Пароль из 8 строчных букв — это 8 последовательных выборов из 26 букв: 26^8, около 2,1 × 10¹¹ строк. Расширьте алфавит до 62 символов (верхний и нижний регистр, цифры) и удлините до 12 знаков: 62^12, около 3,2 × 10²¹ — в десять миллиардов раз больше. Каждая добавленная позиция снова умножает всё пространство на размер алфавита — вот почему длина пароля бьёт хитрые замены символов: длина добавляет множители, а замены лишь слегка утолщают один из них.

Мелкий шрифт правила произведения: сами варианты могут меняться от ранних выборов — неизменным обязано быть только их число. Выбор 2 различных букв для кода: 26 вариантов на первую, затем 25 на вторую — 26 · 25 = 650 упорядоченных пар. Правило работает, потому что каждая ветвь дерева разветвляется на одинаковое число подветвей.

Ужин — одно блюдо. В меню 3 пасты и 4 пиццы. Вы не выбираете пасту, а затем пиццу — вы выбираете одно блюдо из двух непересекающихся случаев (ни одно блюдо не является пастой и пиццей одновременно), поэтому количества складываются: 3 + 4 = 7 возможных ужинов. Это правило суммы: когда исходы распадаются на случаи без общих элементов, итог равен сумме количеств по случаям.

Несущее слово — непересекающиеся. Посчитайте файлы, которые велики или недавно изменены: 80 больших плюс 50 свежих — это не 130, если 20 файлов и то и другое: их посчитали дважды. Вычтите двойной счёт один раз: 80 + 50 − 20 = 110. Правило суммы — счастливый частный случай, когда пересечение пусто.

Сколькими способами n различных предметов могут встать в ряд? Примените правило произведения n раз: n вариантов на первое место, а затем n − 1 на второе (один предмет занят), а затем n − 2, и так до 1. Произведение n · (n−1) · … · 1 записывается n! и читается «эн факториал». Пять сервисов, которые надо задеплоить по очереди: 5! = 120 возможных порядков.

Оборвите произведение раньше — получите упорядоченные выборки: пьедестал (золото, серебро, бронза) из 10 бегунов — это 10 · 9 · 8 = 720: три этапа, и стоп. k этапов = число размещений k из n, и порядок здесь действительно важен: «золото — Аня, серебро — Боря» — другой пьедестал, чем «золото — Боря, серебро — Аня».

Единственный по-настоящему новый ход. Выберем неупорядоченную команду из 3 человек из 10. Те 720 упорядоченных выборок её пересчитывают: команда из Ани, Бори и Светы появляется по разу на каждый способ упорядочить этих троих — а упорядочений 3 предметов ровно 3! = 6. Каждая команда посчитана ровно 6 раз, без исключений, поэтому команд 720 / 6 = 120.

Этот аргумент деления — сгруппировать упорядоченные выборки по тому, какое множество они образуют, заметить, что в каждой группе ровно k! членов, и поделить — вся теория сочетаний целиком. C(n, k) — не формула для зубрёжки, а «посчитай упорядоченно правилом произведения, затем подели на упорядочения, которые тебя не интересовали». Вопрос: считаются ли здесь две выборки, отличающиеся лишь порядком, одним и тем же исходом? Пьедестал: нет — оставьте произведение. Дежурная команда, рука карт: да — поделите на k!.