Составители:
Рубрика:
25
Таким образом, количество комбинаций, при которых очередь за-
стрянет равно P(n – 1, k + 1), а общее число комбинаций равно P(n, k);
т. е., число благоприятных комбинаций, при которых очередь пройдет
без задержки, будет равно
P(n, k) – P(n – 1, k + 1).
Например, при n = 4 и k = 5 число благоприятных комбинаций равно
P(4, 5) – P(3, 4) = 9!/(4!5!) – 7!/(3!4!) = 126 – 35 = 91.
1.19. Рекуррентные соотношения в комбинаторике
1. Задача о наклейке марок.
Имеются марки достоинством в 4, 6, 10 копеек. На конверт нужно
наклеить марки так, чтобы сумма составляла 18 копеек. Будем счи-
тать, что порядок наклеиваемых марок важен, т. е. способы наклейки
марок достоинством в 4, 10, 4 копейки и 10, 4, 4 разные способы. Тогда
можно написать следующее рекуррентное соотношение:
F(N) = F(N – 4) + F(N – 6) + F(N – 10),
где под F(N) понимается количество вариантов наклейки марок общей
стоимостью N. Подсчитаем значения F(N) для некоторых начальных N.
F(N) = 0 при N<0. F(0) =1. F(1) = F(2) = F(3) = 0. F(4) = 1. F(5) = 0.
F(6) = 1. F(7) = 0. F(8) = 1. F(9) = 0. F(10) = 3. Тогда для N = 18 получаем:
F (18) = F(14) + F(12) + F(8) = F(10)+ F(8) + F(4) + F(8) +
+F(6) + F ( 2) + F(8) = 3 + 1 + 1 + 1 + 1 + 1 = 8.
2. Задача об уплате долга. В кошельке имеются монеты достоин-
ством в 1, 2, 3, 5, 10, 15, 20, 50 копеек (по одной штуке). Требуется упла-
тить долг в 73 копейки.
Запишем рекуррентное соотношение в общем случае, когда монеты имеют
достоинства в k
1
, k
2
, … и k
m
копеек и требуется набрать сумму в N копеек:
F(k
1
, k
2
, …, k
m
; N) = F(k
1
, k
2
, …, k
m–1
;N–k
m
) + F(k
1
, k
2
, …, k
m–1
; N).
Первый член правой части учитывает количество комбинаций, в ко-
торых монета старшего достоинства использована, второй член – в ко-
торых монета старшего достоинства не использована. Для рассматри-
ваемого примера
F(1, 2, 3, 5, 10, 15, 20, 50; 73) = F(1, 2, 3, 5, 10, 15, 20; 73) +
+F(1, 2, 3, 5, 10, 15, 20; 23).
Страницы
- « первая
- ‹ предыдущая
- …
- 23
- 24
- 25
- 26
- 27
- …
- следующая ›
- последняя »
