Вероятность и статистика · Подсчёт вариантов

Комбинаторное правило произведения

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

6 минут на чтениеЗаданий для самопроверки: 3

Чему научимся

Правило лежит в основе подсчёта кодов, комплектов, назначений и формул размещений. Оно заставляет заранее учитывать порядок, повторения и специальные ограничения вроде запрета ведущего нуля.

Главная идея. Комбинаторное правило произведения считает полный вариант как цепочку последовательных решений. Если после каждой истории предыдущих шагов на очередном шаге есть одинаковое число продолжений, количества перемножаются.

План рассуждения и проверка понимания

Разделите построение результата на последовательные шаги и определите, какие частичные истории считаются различными.
Для каждого шага найдите число допустимых продолжений после любой истории предыдущих шагов, уже учитывая запреты.
Если число продолжений на уровне постоянно, перемножьте n₁n₂…nᵣ; если меняется по ветвям, разбейте задачу на случаи.
Сверьте результат маленьким деревом и убедитесь, что каждый допустимый конечный объект получен ровно один раз.

Частая ошибка. Посчитать двузначные числа из 0, 1, 2 без повторов как 3 · 2, разрешив ноль на первой позиции и включив записи 01 и 02.

Как проверить себя. На первом шаге доступны только 1 и 2, а после каждого выбора остаются две цифры для единиц; поэтому допустимых чисел 2 · 2 = 4.

Схема к теме

Наглядная модель: Комбинаторное правило произведения

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

1. Условия — что известно и что требуется
2. Модель — порядок, повторения и допустимые исходы
3. Подсчёт — каждый вариант учитывается один раз
4. Проверка — малый случай можно выписать вручную

Последовательность отделяет выбор модели от вычисления и не даёт потерять или повторно учесть варианты. Вывод: Сначала ответьте на вопросы о порядке и повторениях, только потом выбирайте формулу.

Проверка пониманияОбъясните тему своими словами

Объясните, почему назначение капитана и помощника из пяти человек даёт 5 · 4 = 20 вариантов, хотя второй набор кандидатов зависит от первого имени.

В хорошем объяснении есть:

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

Несколько решений подряд

Правило произведения считает варианты, состоящие из последовательных выборов. Если первый шаг возможен $a$ способами, а после каждого первого шага второй доступен $b$ способами, число пар равно $ab$ .

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

Какие ограничения уже учтены

Сначала определяют, важен ли порядок, допускается ли повтор и есть ли ограничения на первую позицию. Код с ведущим нулём и натуральное число одинаковой длины — разные объекты. У трёхзначного числа первая цифра не ноль, поэтому число свободных десятичных записей $1000$ нужно заменить $9\cdot10\cdot10=900$ .

Если число продолжений меняется в зависимости от первой ветви, универсальное произведение может быть неверным. Тогда считают произведения внутри однородных случаев и складывают их.

Не нужно делить на факториал «на всякий случай». Деление на число порядков допустимо, только когда каждый конечный объект одинаковое число раз представлен перечисленными последовательностями.

Три примера

Три вида билета сочетаются с четырьмя сеансами: при доступности всех сочетаний получается $12$ вариантов.
Капитана и помощника выбирают из пяти людей без совмещения ролей. Первых выборов $5$ , вторых $4$ , всего $20$ назначений.
Двузначные числа из цифр $0,1,2$ без повторов: первая цифра имеет два варианта, после неё вторая — два. Итог $4$ , а не $3\cdot3=9$ .

Правильный подсчёт удобно сверять маленьким деревом: у каждой вершины посмотрите число детей и убедитесь, что произведение действительно описывает все листья. Это особенно полезно перед применением готовых формул размещений.

Формула, смысл и ограничения

Главные формулы с расшифровкой

N=n_1n_2\cdots n_r

Формула словами: Если после каждой истории шага j−1 есть ровно nⱼ допустимых продолжений, число полных вариантов — произведение.

От формулы к наблюдению

Попробуйте самостоятельно

Измените параметры и сопоставьте расчёт с результатами случайного эксперимента.

Комбинаторика

От простого к сложному

Проверьте себя

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

Открываем задание…

Источники и соглашения

Объяснения и задачи — авторские. Источники помогают проверить определения, условия и школьную привязку. Обозначения и параметризация указаны в статье.