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

UptoLike

ВУЗ: 

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

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

Рубрика: 

83
2. Определите, во сколько раз увеличится количество сигналов, если
учесть способы развешивания не всех флагов.
4.3.5. «Покупка билетов»
Перед кассой кинотеатра стоит очередь из n владельцев рублей и k
владельцев полтинников. Билет в кинотеатр стоит полтинник (было
же такое время!). В каком количестве комбинаций очередь пройдет без
задержки?
Для решения задачи уточним условия. Если к кассе подходит чело
век с полтинником, он отдает его и получает билет. Если подходит че
ловек с рублем, он отдает рубль, получает на сдачу полтинник и би
лет. У кассирши нет запаса полтинников, т. е. вообще говоря, она не
готова к работе, но в России этим никого не удивишь. Ясно, что зада
ча имеет смысл, если число рублей меньше или равно числу полтинни
ков, т. е. n £ k.
Возьмем комбинацию, при которой очередь застрянет, и запишем
ее следующим образом: (s рублей + s полтинников) P… Очередь, ко
нечно, застрянет на рубле, перед которым было одинаковое число
рублей и полтинников. Добавим впереди полтинник (их тогда ста
нет k+1, и теперь уже число рублей будет строго меньше числа пол
тинников), а затем проинвертируем всю комбинацию до рубля вклю
чительно, на котором очередь застрянет (заменим полтинники на
рубли и рубли на полтинники). Мы придем к комбинации из n руб
лей и k+1 полтинника, которая начинается с рубля: P (s рублей + s
полтинников) П… Если теперь взять n рублей и k+1 полтинник и
начать комбинацию с рубля, то обратным преобразованием мы при
дем к комбинации, при которой очередь застрянет. Таким образом,
число комбинаций из n рублей и k полтинников, при которой оче
редь в кассу застрянет, равно P(n–1, k+1). Число же благоприят
ных комбинаций, при которых очередь пройдет без задержки, будет
равно Р(n, k) – P(n–1, k+1). Например, при n = 4, k = 5 число благо
приятных комбинаций равно P(4, 5)–P(3, 6) = 126–84 = 42.
4.4. Рекуррентные соотношения в комбинаторике
В ряде случаев комбинаторная задача не может быть решена с ис
пользованием описанных методов и приемов, но легко решается с по
мощью упорядоченного перебора вариантов. Часто это решение может
быть получено с использованием так называемых рекуррентных соот
ношений. Рассмотрим несколько примеров.

Страницы