Размещения с повторениями
Рассмотрим задачу: сколько разных 5-разрядных чисел можно составить из 10 цифр?
Перенумеруем разряды:
В первый разряд можно поставить одну из 10 цифр. Независимо от того, какая цифра поставлена, во второй разряд можно также поставить одну из 10 цифр и т. д. Всего получается различных чисел.
Для двоичной системы счисления (используются только две цифры: 0 или 1) получаем различных чисел. Для системы с основанием k и числом разрядов n соответственно получаем:
(1)
n-число позиций (разрядов); k: -число элементов в каждой позиции (цифр).
В общем виде задача ставится следующим образом: имеется k типов предметов (количество предметов каждого типа иеограничено) и n позиций (ящиков, кучек, разрядов). Требуется определить, сколько разных комбинаций можно составить, если в позициях предметы могут повторяться? Ответ дается формулой (1).
Пример. Сколько разных чисел может содержать 10-разрядное слово в троичной системе счисления? В первый разряд можно поставить один из трех символов (0, 1 или 2), во второй разряд - также один из трех символов и т. д. Всего получаем чисел.
Упражнения
1. Кодовый замок имеет 5 одинаковых ячеек, каждая ячейка может быть установлена в одно из 6 устойчивых положений. Сколько различных комбинаций нужно перебрать (максимальное количество), чтобы не зная кода, открыть кодовый замок?
2. Пятеро студентов сдают экзамен. Каким количеством способов могут быть выставлены оценки, если известно, что никто из студентов не получил неудовлетворительной оценки?
3. На почте имеется 5 типов марок одинакового достоинства. На конверт нужно наклеить 3 марки. Сколько существует различных комбинаций наклейки марок на конверт, если порядок наклейки марок имеет значение?
4. Частично определенная булева функция в таблице истинности (диаграмме Вейча) кроме 1 и 0 содержит 30 прочерков. На месте каждого прочерка при доопределении может быть поставлена 1 или 0. Сколько существует разных способов доопределения этой булевой функции? Оцените число способов доопределения в десятичной системе, используя очевидное неравенство:
В некоторых случаях имеются ограничения на количество разных предметов, которые можно помещать на позиции. Пусть, например, имеется n позиций и на каждую i-ю позицию можно поставить ki предметов. Сколько в этом случае существует разных расстановок предметов по позициям?
Легко обосновывается формула:
(2)
IIример. В эстафете 100+200+400+800 метров на первую позицию тренер может выставить одного из 3 бегунов, на вторую - одного из 5, на третью - одного из 6, па четвертую - единственного бегуна (на каждую позицию выставляются разные бегуны). Сколько вариантов расстановки участников эстафетного забега может составить тренер?
В соответствии с формулой (2) получаем, что число вариантов равно: 3 · 5 · 6 · 1 = 90.
Упражнения
1. Сколько существует автомобильных номеров, содержащих три буквы и 5 цифр, если используется 20 букв русского алфавита и все 10 цифр?
2. Сколько существует 7 разрядных чисел в первых трех разрядах которых нет цифр 0, 8, 9?
3. Время работы агрегата в сутки задается часами, минутами и секундами. Сколько разных временных интервалов может быть задано для работы агрегата? (86400)
