число способов составить 600 рублей купюрами по 10, 50 и 100

[Димитрий]

Покупателю в магазине нужно оплатить покупку.
У него имеются купюры по 10, 50, 100 рублей.
Сколькими способами можно заплатить за покупку,
если её стоимость 600 рублей?

Методом перебора нашёл, что количество возможных
вариантов равно 49:

1.) 60*10
2.) 55*10+50
3.) 50*10+100
4.) 50*10+2*50
5.) 45*10+50+100
6.) 45*10+3*50
7.) 40*10+2*100
8.) 40*10+2*50 +100
9.) 40*10+4*50
10.) 35*10+50+2*100
11.) 35*10+3*50+100
12.) 35*10+5*50
13.) 30*10+3*100
14.) 30*10+2*50+2*100
15.) 30*10+4*50+100
16.) 30*10+6*50
17.) 25*10+50+3*100
18.) 25*10+3*50+2*100
19.) 25*10+5*50+100
20.) 25*10+7*50
21.) 20*10+4*100
22.) 20*10+2*50+3*100
23.) 20*10+4*50+2*100
24.) 20*10+6*50+100
25.) 20*10+8*50
26.) 15*10+50+4*100
27.) 15*10+3*50+3*100
28.) 15*10+5*50+2*100
29.) 15*10+7*50+100
30.) 15*10+9*50
31.) 10*10+5*100
32.) 10*10+2*50+4*100
33.) 10*10+4*50+3*100
34.) 10*10+6*50+2*100
35.) 10*10+8*50+100
36.) 10*10+10*50
37.) 5*10+50+5*100
38.) 5*10+3*50+4*100
39.) 5*10+5*50+3*100
40.) 5*10+7*50+2*100
41.) 5*10+9*50+100
42.) 5*10+11*50
43.) 2*50+5*100
44.) 4*50+4*100
45.) 6*50+3*100
46.) 8*50+2*100
47.) 10*50+100
48.) 12*50
49.) 6*100

Но как получить это число с помощью формулы никак не могу сообразить…

[Бодигрим]

В общем случае я бы решал это через производящие функции разбиений. Например, можно почитать Ландо С.К. — Лекции о производящих функциях (гл. 6, Разбиения и разложения). Или Гульден Я., Джексон Д. — Перечислительная комбинаторика (гл. 2.5, Разбиения целых чисел).

[ИСН]

Короче: красивой замкнутой формулы нет, ответ выглядит примерно как "коэффициент при $x^{600}$ в степенном разложении для $1\over(1-x^{10})(1-x^{50})(1-x^{100})$"

[PAV]

Через рекуррентные соотношения можно в принципе сделать. Все равно считать придется, но, возможно, чуть меньше. А, главное, можно быть более уверенным, что ни один вариант не пропущен.

[Бодигрим]

Но вообще вы перебрали верно - там действительно 49 вариантов.

[ИСН]

А нет, я трындел. Замкнутая формула таки есть (я это понял, глядя на ряд результатов), она всего лишь квадратичная от n, но уродливая и корявая, не однажды включает фрагменты вида "целая часть от n делить на что-то-там", и легче от неё никому не станет, потому выписывать её не буду.

[Димитрий]

Спасибо!

[bot]

Я бы по простому пошёл (годится и для 6000 вместо 600):

$x+5y+10z=60, \ \ x=5t \Rightarrow \ \ t + y = 2 (6-z) = 2v$

При $v=0,1,..,6$ имеется $2v+1$ решений.

Итого 1+3+...+13=49