Дискретная математика. Ерош И.Л - 64 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

64
Для двоичной системы счисления (в которой используются только
две цифры: 0 или 1) получаем 2
5
различных чисел. Для системы с ос
нованием k и числом разрядов n соответственно получаем
.
n
Ak1
(4.1)
Формула (4.1) определяет количество конфигураций
A
– размеще
ний с повторениями.
В общем виде задача размещений с повторениями ставится следую
щим образом. Имеется k типов предметов (количество предметов каж
дого типа неограничено) и n позиций (ящиков, сумок, кучек, разря
дов). Требуется определить, сколько разных комбинаций можно соста
вить, если в позициях предметы могут повторяться? Ответ дается фор
мулой (4.1).
Сколько разных десятиразрядных чисел можно записать в троич
ной системе счисления? Получаем 3
10
.
Упражнения.
1. Кодовый замок имеет 5 одинаковых ячеек, каждая ячейка мо
жет быть установлена в одно из 6 устойчивых положений. Какое мак
симальное число комбинаций нужно перебрать, чтобы открыть кодо
вый замок?
2. Пятеро студентов сдают экзамен. Каким количеством способов
могут быть поставлены им оценки, если известно, что никто из сту
дентов не получил неудовлетворительной оценки?
3. Частично определенная булева функция в таблице истинности
(диаграмме Вейча) кроме 1 и 0 содержит 30 прочерков. На месте каж
дого прочерка при доопределении может быть поставлена либо 1, либо
0. Сколько существует разных способов доопределения этой булевой
функции? Оцените число способов доопределения в десятичной систе
ме, используя очевидное неравенство: 2
10
> 10
3
.
В некоторых случаях кроме числа позиций дополнительно указы
вается ограничение на количество предметов, которые могут быть по
мещены на каждую позицию. Пусть, например, имеется n позиций и
на каждую iю можно поставить n
i
предметов. Сколько существует раз
ных расстановок предметов по позициям?
Легко обосновывается формула
123
1
... .
i
n
n
i
Akkk k k11
2
(4.2)
Пример. В эстафете 100 + 200 + 400 + 800 метров на первую позицию
тренер может поставить одного из 3х бегунов, на вторую – одного из 5,

Страницы