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

Размещения с повторениями

Считаем упорядоченные последовательности, в которых элемент может использоваться снова.

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

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

Модель считает PIN-коды, слова фиксированной длины и последовательности ответов «да/нет». Она также помогает через дополнение находить число записей, где выделенный символ встретился хотя бы один раз.

Главная идея. Размещение с повторениями — это упорядоченная последовательность из k мест, где на каждом месте снова доступны все n символов. Поэтому одинаковый выбор можно повторять, а перестановка символов обычно создаёт новый результат.

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

Проверьте, что позиции различимы, длина k фиксирована и использование символа не запрещает выбрать его на следующей позиции.
Для каждой из k позиций запишите одинаковое число доступных вариантов n, включая ведущий ноль, если условие его разрешает.
Примените правило произведения и получите n в степени k; не делите результат на факториалы повторяющихся символов.
При условии «хотя бы один выделенный символ» вычтите из nᵏ последовательности, составленные только из остальных n − 1 символов.

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

Как проверить себя. Считайте независимый выбор на каждой позиции: АА и АБ — два обычных допустимых слова, а все n вариантов снова доступны на каждом из k шагов.

Схема к теме

Наглядная модель: Размещения с повторениями

Считаем упорядоченные последовательности, в которых элемент может использоваться снова.

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

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

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

Объясните, почему трёхбуквенных слов из А, Б, В с хотя бы одной буквой А ровно 3³ − 2³ = 19, не перечисляя все слова вручную.

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

Общее число 27 получено как три выбора на каждой из трёх различимых позиций.
Вычтены восемь слов только из Б и В, то есть в дополнении нет ни одной буквы А.

Каждый выбор снова доступен

Размещение с повторениями — последовательность длины $k$ , каждая позиция которой выбирается из одного набора из $n$ элементов. Порядок важен, использование элемента не запрещает его повтор на следующих местах.

Для кодов из трёх букв А, Б, В длины два получаются АА, АБ, АВ, БА, ББ, БВ, ВА, ВБ, ВВ. Каждый первый символ имеет три продолжения, поэтому всего $3^2=9$ .

Почему появляется степень

Правило произведения перемножает $k$ одинаковых количеств $n$ . Получается $n^k$ . Это подсчёт без вероятностных предположений. Чтобы каждая последовательность имела вероятность $1/n^k$ , дополнительно нужны независимые равномерные выборы на позициях.

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

Не смешивайте виды повторений

В перестановках с повторяющимися элементами количества каждого символа заранее фиксированы. Здесь они свободны: слово АА допустимо наряду с АБ. Поэтому деление на факториалы повторений не применяется.

Условие «хотя бы один символ» удобно считать дополнением. Если один выделенный символ запрещён на всех позициях, остаётся $(n-1)^k$ слов; вычитание из $n^k$ даёт число слов с хотя бы одним его появлением.

Три примера

Десятичный четырёхзначный PIN допускает ведущие нули: вариантов $10^4=10000$ .
Пять независимых записей «да/нет» дают $2^5=32$ двоичных последовательности.
Трёхбуквенные слова из А, Б, В с хотя бы одной А: $3^3-2^3=27-8=19$ . Здесь не фиксировано точное число букв А.

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

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

\overline A_n^k=n^k

Формула словами: При n доступных символах на каждом из k различимых мест получается nᵏ последовательностей.

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

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

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

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

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

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

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

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

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

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