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

UptoLike

ВУЗ: 

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

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

Рубрика: 

73
12
1
(1)!
,–1 .
!( 1)!
k
nk
kn
Pkn C
kn
34
55
4
(4.8)
Упражнения.
1. Входной алфавит абстрактного конечного автомата содержит
5 символов, например a, b, c, d, e. Входные слова имеют длину в
11 символов. Сколько разных слов может быть подано на вход конеч
ного автомата, если слова, имеющие одинаковый состав букв и разли
чающиеся только порядком, считать одинаковыми? Например, слова
baabce и eabcba считаются одинаковыми. При решении задачи нужно
учесть, что формула (4.8) определяет только количество вариантов вы
бора букв, но не их порядок в слове.
2. Графсхема алгоритма микропрограммного автомата содержит
операторные и условные вершины. Операторные вершины «начало» и
«конец» являются обязательными. Сколько существует различных
графсхем алгоритмов, содержащих 6 вершин, если нас интересует
только количественный состав, а не связи между вершинами?
3. У человека, спустившегося с гор, есть 5 баранов, которых он хо
чет раздать своим 8 сыновьям. Ему нужно найти число способов раз
дачи целых баранов, если:
a) каждый сын может получить либо одного барана, либо ничего;
b) число баранов, которые получают сыновья, неограничено (но, ес
тественно, не превышает 5).
4. Некоторый банк имеет 3 «свободных» миллиона и готов раздать
их 5 клиентам. Правление банка принимает решение о выдаче ссуды,
кратной 0,25 миллиона. Сколько существует способов выдачи ссуд?
4.1.9. Свойства чисел сочетаний
Приведем некоторые свойства чисел сочетаний, которые часто ис
пользуются при преобразованиях формул комбинаторики.
1.
.
knk
nn
СC1
2.
1
11
.
kk k
nn n
СC C1 2
3.
012
... 2 .
nn
nnn n
CCC C1111 2
Первое свойство совершенно очевидно. Второе легко доказывается,
если оба члена правой части представить по формуле (4.7). Третье свой
ство можно доказать методом математической индукции. Для приме
ра, при n = 2 получаем
012 2
222
1212.ССС11 2 112
При n = 3 получаем
0123 3
3333
13312.СССС111 2 1112

Страницы