§ 1. Комбинаторное правило умножения

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

Начнём с задачи, которую ещё можно проверить глазами. В школьном буфете есть два сорта хлеба, белый и чёрный, а сверху кладут что-то одно: сыр, ветчину или повидло. Сколько разных бутербродов удастся собрать? Разложим их по клеткам таблицы: строки — сорт хлеба, столбцы — начинка (рис. 1). Каждая клетка — ровно один бутерброд, и ни один не повторяется дважды. Строк две, в строке три клетки, значит, бутербродов 2 · 3 = 6.

Тот же перебор удобно рисовать деревом (рис. 2). Из корня выходят две ветви — это выбор хлеба. Из каждой ветви растут ещё три — это выбор начинки. На нижнем ярусе получается шесть концов, по одному на бутерброд. Дерево показывает то, чего не видно в готовом ответе «шесть»: к любому первому выбору пристраивается одинаковый набор продолжений, поэтому число концов и находится умножением.

Комбинаторное правило умножения. Пусть первый предмет можно выбрать n способами, а второй — k способами. Тогда набор из двух предметов, где на первом месте стоит первый, а на втором — второй, составляется nk способами.