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

UptoLike

ВУЗ: 

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

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

Рубрика: 

23
бами. Каждой перестановке будет соответствовать некоторый способ
раздела 40 яблок на 3 кучки. Каждому способу раздела будет соответ-
ствовать некоторый код, содержащий 40 единиц и 2 нуля. Поэтому коли-
чество способов раздела:
P(40, 2) = 42!/(2!40!) = 861.
Если мы раскладываем n
1
предметов 1-го типа, n
2
предметов вто-
рого, …, n
k
предметов k-го типа на s кучек, тогда
P(n
1
, s – 1) P(n
2
, s – 1)…P(n
k
, s – 1) .
Рассмотренный способ раздела содержит комбинации, при которых
в какой-либо кучке вообще может не оказаться ни одного предмета,
поэтому его можно назвать несправедливым. Для обеспечения более
справедливого раздела можно заранее разложить часть предметов по
кучкам (ящикам, корзинам), а затем оставшиеся предметы расклады-
вать описанным несправедливым способом.
Упражнения
1. У человека, спустившегося с гор, есть 5 баранов, которых он хо-
чет раздать своим 8 сыновьям. Ему нужно найти число способов раз-
дачи целых баранов если:
а) каждый сын может получить либо одного барана, либо ничего,
б) число баранов, которые получают сыновья неограниченно (но не
более 5).
2. Обобщите решение предыдущей задачи в случаях a) и б) при n
баранах и k сыновьях.
3. Имеется два множества: A с элементами a
1
, a
2
, …, a
n
и B с эле-
ментами b
1
, b
2
, …, b
k
.
Требуется составить множество С из элементов множества A и B
так, чтобы в множестве С содержалось s элементов, при этом нужно,
чтобы в С было не менее p элементов множества A.
Для решения этой задачи предварительно решите следующую: Из
группы, состоящей из 7 мужчин и 4 женщин нужно отобрать 6 человек
так, чтобы в выбранное множество входило не менее 2 женщин.
1.17. Задача: Флаги на мачтах
Имеется n флагов и k мачт. Сколько разных сообщений можно пере-
дать, развешивая флаги на мачтах? В этой задаче важным является не

Страницы