Вероятность и статистика · Математическая основа

Систематический перебор

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

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

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

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

Главная идея. Систематический перебор — это перечисление по заранее выбранному правилу, при котором каждый допустимый вариант появляется ровно один раз. Таблица или дерево делают полноту списка проверяемой.

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

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

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

Как проверить себя. Используйте стабильный порядок по первому элементу и заранее решите, является ли АБ тем же результатом, что БА; тогда дубликаты видны сразу.

Схема к теме

Наглядная модель: Систематический перебор

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

Систематический перебор → перебор
Систематический перебор → варианты
Систематический перебор → порядок
Систематический перебор → таблица вариантов
Систематический перебор → дерево

Схема связывает понятие «Систематический перебор» с его ключевыми признаками. Вывод: Свяжите определение, условия и обозначения: тогда формула станет краткой записью уже понятной идеи.

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

Перечислите двузначные числа из 0, 1, 2 без повторений и объясните, почему список 10, 12, 20, 21 полон и не содержит лишних записей.

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

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

Перебор — это правило записи

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

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

Различаем похожие задачи

Для двух мест и букв А, Б, В с повторениями список начинается АА, АБ, АВ, затем БА, ББ, БВ, затем ВА, ВБ, ВВ. Получаем $3\cdot3=9$ последовательностей. Если повторять буквы нельзя, остаётся шесть.

Если из трёх человек выбирают капитана и помощника, роли различаются: АБ и БА — разные назначения. Если выбирают пару дежурных с одинаковыми ролями, это одна и та же пара. В первом случае вариантов шесть, во втором — три.

Правило умножения работает, когда число продолжений одинаково для каждого первого выбора. Если из одной вершины дерева выходят две ветви, а из другой три, общее число конечных путей $2+3=5$ . Нельзя заменить это дерево произведением $2\cdot3$ .

Как проверять полноту

Группы вариантов должны не пересекаться и вместе покрывать все допустимые случаи. Например, двузначные числа группируем по десяткам: число не попадёт сразу в две группы. Внутри группы упорядочиваем единицы. В конце проверяем ограничения: может ли первая цифра быть нулём, можно ли повторять элементы, важен ли порядок.

В вероятности полный список особенно полезен для маленьких моделей. Но количество вариантов ещё не доказывает равенства их вероятностей: это отдельное условие случайного эксперимента.

Три примера

Есть две футболки и три пары брюк; любая футболка подходит к любой паре. Комплектов $2\cdot3=6$ .
Из цифр $0$ , $1$ , $2$ составляют двузначные числа без повторений. Десяток не может быть нулём. Список: $10$ , $12$ , $20$ , $21$ — четыре числа.
Из А, Б, В выбирают пару без ролей. Упорядоченных записей шесть: АБ, АВ, БА, БВ, ВА, ВБ. Каждая пара записана дважды, поэтому различных пар $6/2=3$ .

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

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

N=a\cdot b

Формула словами: Если после каждого из a первых вариантов доступны ровно b вторых, последовательностей a·b.

N=n(n-1)

Формула словами: Число упорядоченных пар разных элементов из набора из n элементов, n ≥ 2.

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

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

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

Лаборатория: Карточная колода Лаборатория: Дерево вероятностей Комбинаторика

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

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

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

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

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

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