задача о размене достаточно важная в комбинаторике может решаться 2 основными способами 1)Методом производящих функций с перемножением соответствующих многочленов 2)рекурсивным методом (cм ЕГ информатика, рекурсивные вычисления).
Правда во 2 сл учитывается последовательность монет, т.е. для нахождения количества действительно разных способов надо делить на число сочетаний, например при
рекурсией получим 5 а с учетом отсутствия перестановок надо поделить на 5 и будет 1
Не знаю, может возможно решение через формулу Пика.
Задача сводится к количеству целочисленных точек
на наклонном отрезке решетки
Для
и прямоугольного треугольника ограниченного осями и линией
она имеет вид
площадь
найти легко.
Т.е. задача размена сводится к оценке количества целочисленных точек
прямоугольного треугольника (неизвестно что легче)
Во 2 разновидности постановки задачи с учетом ограничений по количеству купюр каждого номинала видимо минимально гарантированной разменной суммы может и не существовать