Размен монетами, найти количество способов

[eugrita]

Выскажу и свое мнение. Соглашаясь с подходом вычисления коэфф при производящей функции, тем не менее как программист предпочитаю любой программный алгоритм. Даже грубой силы , т.е. перебором по всем векторам $P$
$p_i \le n_i$ $1 \le i \le k$
$k$ кол-ва номиналов $n_i$ -вектор номиналов монет
Находит не только количество вариантов но и сами варианты. Если наложить доп. ограничения по количеству монет номиналов типа $p_i \le kol_i$
-тоже нет проблем. Программа легко и к этому адаптируется.
Именно такая практическая задача востребована в жизни и у любого кассира и у разменного автомата.
Пример результата расчета (разделитель меж тройками -запятая)
$k=3 N=81 n=3, 5,7 $
$ X=0 5 8 , 0; 12; 3 , 1 3 9, 1 ;10; 4, 2 1;10, 2 8 5 , 2 ;15; 0, 3 6 6 ,3 ;13 ;1,4 4 7, 4 ;11; 2, 5 2 8, 5 9 3 ,6 0 9,6 7 4 ,7 5 5 ,7 ;12; 0, 8$
3 6,8 10 1,9 1 7 ,9 8 2 ,10; 6 3 ,11; 4 4, 12;2 5, 12; 9 0, 13; 0 6, 13; 7 1 ,14; 5 2, 15; 3 3 ,16; 1 4 ,17; 6 0,18; 4 1, 19; 2 2, 20; 0 3 , 22; 3 0 , 23; 1 1 $

А если наложить дополнительно ограничения по количествам номиналов
$(20,10,3)$ то количество решений резко снизится - cтанет 6

[eugrita]

$12 ;9 0 ,13; 7 1 ,14; 5 2 ,17; 6 0 ,18; 4 1 ,19; 2 2$