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

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

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

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

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

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

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

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

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

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

Три примера

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