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

UptoLike

ВУЗ: 

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

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

Рубрика: 

24
только количество флагов, вывешенных на каждой мачте, но и их поря-
док.
Сначала будем считать, что все флаги одинаковые. Тогда:
P(n, k – 1) = (n + k – 1)!/(n!(k – 1)!).
Окончательное решение – полученный результат нужно умножить
на n! так как после того, как флаги развешены каким-либо способом,
можно еще их поменять n! способами, сохраняя количество флагов на
каждой мачте.
Количество разных сигналов, получаемых путем развешивания фла-
гов на мачтах, можно еще увеличить, если учитывать варианты, при
которых вывешиваются не все флаги, а, например, s флагов из имею-
щихся n. Тогда общее число расстановок будет
()
1
!,1.
n
i
sPsk
=
−
∑
1.18. Задача: Покупка билетов
Перед кассой по продаже билетов стоит очередь из n владельцев
рублей и k владельцев полтинников. Билет стоит полтинник. В каком
количестве комбинаций очередь пройдет без задержки, если владелец
полтинника, подойдя к кассе, получает билет, а владелец рубля – билет
и полтинник на сдачу. В кассе предварительно нет полтинников. Ясно,
что задача имеет смысл, если n ≤ k.
Возьмем комбинацию, при которой очередь застрянет и запишем ее
следующим образом:
(s – рублей и s – полтинников)Р………
Очередь застрянет на рубле, при этом до этого рубля в очереди дол-
жно быть одинаковое количество владельцев рублей и полтинников.
Добавим спереди полтинник (их станет k + 1) и проинвертируем всю
комбинацию (заменим рубли на полтинники, а полтинники на рубли) до
рубля, на котором очередь застряла (включая и его). Мы придем к ком-
бинации, содержащей n рублей и k + 1 полтинник, начинающейся с руб-
ля. Можно взять n рублей и k + 1 полтинник (теперь всегда число пол-
тинников строго больше числа рублей) и начать комбинацию с рубля.
Обратным преобразованием придем к комбинации, при которой очередь
обязательно застрянет.

Страницы