Задача "Флаги на мачтах"
Имеется n флагов и k мачт. Сколько разных сообщений можно передать, развешивая флаги на мачтах? В этой задаче важным является не только количество флагов, вывешенных на каждой мачте, но и их порядок.
Сначала будем считать, что все флаги одинаковые. Тогда:
Р(n, к - 1) = (n + k- 1)!/(n!(k- 1)!).
Окончательное решение - полученный результат нужно умножить на n! так как после того, как флаги развешены каким-либо способом, можно еще их поменять n! способами, сохраняя количество флагов на каждой мачте.
Количество разных сигналов, получаемых путем развешивания флагов на мачтах, можно еще увеличить, если учитывать варианты, при которых вывешиваются не вес флаги, а, например, s флагов из имеющихся n. Тогда общее число расстановок будет
Задача "Покупка билетов"
Перед кассой по продаже билетов стоит очередь из n владельцев рублей и k владельцев полтинников. Билет стоит полтинник. В каком количестве комбинаций очередь пройдет без задержки, если владелец полтинника, подойдя к кассе, получает билет, а владелец рубля - билет и полтинник на сдачу. В кассе предварительно нет полтинников. Ясно, что задача имеет смысл, если n < k.
Возьмем комбинацию, при которой очередь застрянет и запишем ее следующим образом:
(s - рублей и s - полтинников)Р.........
Очередь застрянет на рубле, при этом до этого рубля в очереди должно быть одинаковое количество владельцев рублей и полтинников. Добавим спереди полтинник (их станет
k + 1) и проинвертируем всю комбинацию (заменим рубли на полтинники, а полтинники на рубли) до рубля, на котором очередь застряла (включая и его). Мы придем к комбинации, содержащей п рублей и k + 1 полтинник, начинающейся с рубля. Можно взять n рублей и
k + 1 полтинник (теперь всегда число полтинников строго больше числа рублей) и начать комбинацию с рубля. Обратным преобразованием придем к комбинации, при которой очередь обязательно застрянет.
Таким образом, количество комбинаций, при которых очередь застрянет равно Р(n - 1,
k + 1), а общее число комбинаций равно Р(n, k): т. е., число благоприятных комбинаций, при которых очередь пройдет без задержки, будет равно
Р(n,k)-Р(n- 1,k + 1).
Например, при n = 4 и k = 5 число благоприятных комбинаций равно
Р(4, 5) - Р(3, 4) = 9!/(4!5!) - 7!/(3!4!) = 126- 35 = 91.
