В предыдущем пункте элементы комбинаций не повторялись: в пароле стояли разные цифры, в очереди — разные люди. Теперь разрешим повторения: в коде цифра может встречаться несколько раз, в слове — одна и та же буква.
Пример 1. Сколько существует трёхзначных кодов замка, в которых не используются цифры 0, 5 и 7?
Разрешённых цифр семь: 1, 2, 3, 4, 6, 8, 9. Кодов из одной цифры — 7. Каждый код из двух цифр получается, если перед кодом из одной цифры написать любую из семи цифр: 11, 21, 31, …, 99 — их 7 · 7 = 7² = 49. Так же перед каждым из 49 двузначных кодов можно написать любую из семи цифр: трёхзначных кодов 7² · 7 = 7³ = 343.
Заметим: неважно, какие именно три цифры запрещены, — ответ зависит только от того, сколько цифр разрешено.
Способ подсчёта числа комбинаций с повторениями. Сначала считают комбинации из одного символа (длины 1). Потом, приписывая перед каждой из них по очереди каждый из возможных символов, считают комбинации длины 2, затем длины 3 и так далее, пока не дойдут до нужной длины. Если символов k, то на каждом шаге число комбинаций умножается на k, и комбинаций длины n получается kⁿ.
Пример 2. Сигнальщик передаёт буквы флажком: каждое движение — вверх, вниз или в сторону, а букве соответствует последовательность от одного до трёх движений. Хватит ли таких сигналов для всех 33 букв русского алфавита?
Сигналов из одного движения 3, из двух — 3² = 9, из трёх — 3³ = 27. Всего 3 + 9 + 27 = 39, а 39 ≥ 33, — значит, хватит, и шесть сигналов ещё останутся свободными. А вот если бы движений было только два, последовательностей длиной от одного до четырёх движений было бы 2 + 4 + 8 + 16 = 30 < 33 — не хватило бы.