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

UptoLike

ВУЗ: 

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

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

Рубрика: 

74
Упражнения.
1. Полный дешифратор имеет n входов и 2
n
выходов. Сколько вы
ходов будет иметь дешифратор на 5 входов, если исключить все выхо
ды, соответствующие равновесным входным наборам из 2х и 4х еди
ниц?
2. В некотором государстве не было двух жителей с одинаковым на
бором зубов. Сколько жителей могло быть в этом государстве, если во
рту человека не может быть больше 32х зубов? Для оценки исполь
зуйте очевидное неравенство: 2
10
> 10
3
.
4.1.10. Основные формулы классической комбинаторики
Нами рассмотрены следующие основные случаи, которые обычно
относят к классической комбинаторике.
1. Размещения с повторениями: .
kk
n
A
n1
Здесь n – число типов объектов, k – число позиций.
Примеры:
– количество kразрядных чисел в системе с основанием n;
– максимальное число попыток вскрытия замка, состоящего из
n ячеек с k – числом позиций (устойчивых положений) каждой ячей
ки.
2. Размещения без повторений:
!
.
()!
k
n
n
A
nk
1
2
Здесь n – число различных объектов, k – число позиций. Каждый
объект представлен в единственном экземпляре.
Примеры:
– выборы из n человек k человек с назначением их на должности;
– выборы из n предметов k предметов с присваиванием им номеров.
3. Перестановки без повторений: P
n
= n!.
Примеры:
– различные списки выступающих;
– перестановка букв в слове в случае, когда ни одна буква не повто
ряется.
4. Перестановки с повторениями: P(n
1
, n
2
, …, n
k
) = (n
1
+ n
2
+…
+ n
k
)!/ (n
1
!n
2
!…n
k
!).
Здесь n
1
, n
2
, …, n
k
– количество объектов каждого типа.
Примеры:
– количество различных слов, получаемых перестановкой букв в
словах, в которых одинаковые буквы могут повторяться несколько раз;
– равновесные коды.
5. Сочетания без повторений:
!
.
!( )!
k
n
n
С
kn k
1
2

Страницы