Почему число вариантов равно N в степени k
Первое извлечение можно сделать N способами. Так как объект вернулся, второе извлечение тоже выбирает из всех N объектов, и независимо от первого результата вариантов снова N. По правилу произведения общее число последовательностей равно N · N · … · N, где множитель повторён k раз.
В комбинаторике такие последовательности называют размещениями с повторениями. Их порядок важен: последовательность (А, Б, А) отличается от (А, А, Б), хотя состав объектов у них одинаковый.
Разбор примера: выбор учеников и бросок кубика
В классе 30 учеников, и четыре раза подряд наугад называют фамилию, возвращая назвавшегося обратно. Получаем 30⁴ = 810000 различных упорядоченных результатов. Один и тот же ученик может быть назван несколько раз — это допустимо, раз он возвращается.
Другой пример — пять бросков игрального кубика. Каждый бросок даёт 6 исходов, поэтому записей результатов 6⁵ = 7776. Если спросить, какова вероятность конкретной последовательности, достаточно разделить единицу на это число, поскольку все последовательности равновероятны.
Сравнение с выборкой без возвращения
Без возвращения число вариантов на шагах уменьшается: N · (N − 1) · … · (N − k + 1). Для тех же 30 учеников и четырёх извлечений это 657720 последовательностей, на 18,8% меньше, чем 810000. Разница мала при малых k и большом N, но быстро растёт, когда k приближается к N.
Поэтому в практике допущение «с возвращением» часто используют как приближение, если выборка составляет малую долю совокупности: вероятность дважды выбрать один и тот же объект тогда мала. Для крупных долей выборки такое упрощение даёт заметную погрешность.
Где применяется число выборок с возвращением
Оно нужно в бутстрепе: из исходной выборки размера n многократно формируют новые выборки такого же размера с возвращением, и всего возможных вариантов n^n. На практике перебирают лишь случайную часть, но знание размера пространства показывает, что вариантов более чем достаточно.
Формула N^k встречается и в простых задачах кодов и паролей, где символы могут повторяться: например, трёхзначный код из десяти цифр даёт 10³ = 1000 комбинаций. Но для безопасных паролей важна не только комбинаторика, но и предсказуемость выбора.
Наконец, N^k помогает прикинуть вычислительную нагрузку: полный перебор всех упорядоченных выборок из 20 объектов по 8 извлечений потребовал бы рассмотреть 25,6 млрд вариантов. Такая оценка заранее показывает, когда перебор нереален и лучше использовать случайную часть вариантов.
Типичные ошибки при подсчёте выборок
Первая ошибка — применять формулу, когда порядок не важен: тогда нужно считать сочетания с повторениями, и число вариантов будет меньше. Вторая — забывать, что выборка без возвращения даёт другое число, и подставлять N^k там, где объекты не возвращаются.
Третья ошибка — путать число выборок с вероятностью. Число N^k — это количество равновероятных последовательностей лишь при случайном выборе с равными шансами; если шансы объектов разные, вероятности придётся считать отдельно для каждой последовательности.
Формула расчёта
M = N · N · … · N = N^k
Проверенные примеры
Из 30 учеников 4 раза выбирают случайного, возвращая выбранного обратно. Сколько упорядоченных выборок возможно?
Каждое из 4 извлечений даёт 30 вариантов, всего 30⁴ = 810000 упорядоченных выборок.
Кубик бросают 5 раз и записывают последовательность результатов. Сколько разных последовательностей возможно?
Здесь N = 6 граней, k = 5 бросков, 6⁵ = 7776 последовательностей.
Как пользоваться онлайн-калькулятором
- Введите N — сколько различимых объектов в совокупности.
- Введите k — сколько раз объект извлекается с возвращением.
- Нажмите «Вычислить» и сравните результат с числом выборок без возвращения, если оно вам нужно.