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

UptoLike

ВУЗ: 

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

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

Рубрика: 

75
Формула сочетаний используется тогда, когда порядок выбора k
предметов из n не учитывается.
Примеры:
– выбор нескольких человек из группы для выполнения какихлибо
работ;
– выбор нескольких букв алфавита для использования в автомо
бильных номерах.
6. Сочетания с повторениями:
1 2
1
(1)!
,1 .
!( 1)!
k
nk
kn
Pkn C
kn
3 4
45 5
4
Формула используется тогда, когда требуется набрать k предметов
n типов.
Примеры:
– выдача n клиентам банка ссуды с использованием k квот;
– покупка k пирожных n типов.
4.2. Комбинаторные задачи с ограничениями
Рассмотрим несколько классов задач, в которых на комбинации на
кладываются определенные ограничения. Следует заметить, что таких
классов задач встречается очень много.
4.2.1. Простые задачи с ограничениями
a) «Задача о львах и тиграх». Имеется 5 львов и 4 тигра. Необхо
димо их расставить в ряд, но при этом дрессировщик знает, что тигр
не может спокойно идти за тигром.
Для решения задачи сначала расставим львов с промежутками (по
лучим 6 промежутков), выберем из них 4 и на них поставим тигров,
а лишние промежутки уберем. В этом случае ни один тигр не будет
идти за тигром. Таким образом, если львы и тигры обезличенные, то
4
6
15.С 1
В общем случае при n львах и k тиграх получаем:
1
.
k
n
С
b) «Задача о книжной полке». Из n книг, стоящих на полке, нуж
но выбрать k таких, которые не стояли рядом на книжной полке.
Отберем сразу k книг, останется n–k книг. Расставим их с проме
жутками, получим n–k+1 промежуток. Выберем из этих промежутков
k и на них вернем выбранные книги. Остальные промежутки уберем.
Решение:
1
.
k
nk
С
(4.9)
c) «Рыцари короля Артура». 12 рыцарей сидят за круглым сто
лом, едят, пьют вино и, естественно, ссорятся. Причем ссорятся си
дящие рядом. Неожиданно приходит известие о том, что любимая
дочь короля украдена. Нужно послать команду для спасения доче

Страницы