Банкноты Страны Странностей

[Ktina]

В Стране Странностей имеют хождение банкноты достоинством 1, 2, 3, 4, 5, 6, 7, 8, 9 и 10 бурлей.
Найти количество способов размена 10-бурлёвой купюры на купюры меньшего достоинства.

[mihaild]

1) способы с учетом порядка?
2) предлагается считать вручную как-то хитро, или написать тривиальную динамику?

[worm2]

Наверное, достаточно написать рекурсивную формулу, т.е. динамику, но пока, с кавалерийского наскоку, она мне не кажется тривиальною.

[12d3]

worm2 в сообщении #1144682 писал(а):

Наверное, достаточно написать рекурсивную формулу, т.е. динамику, но пока, с кавалерийского наскоку, она мне не кажется тривиальною.

Количество способов разменять сумму $n$ купюрами максимального номинала $m$: $\displaystyle{P(n,m) = \sum_{k=0}^{\left[\frac{n}{m}\right]}P(n-km,m-1)}$. Вот и вся динамика.

[Ktina]

mihaild в сообщении #1144649 писал(а):

1) способы с учетом порядка?

Без.

[Yadryara]

Таким образом, для 10-бурлёвой — 41 способ.

[worm2]

12d3 в сообщении #1144687 писал(а):

Вот и вся динамика.

Вроде, всё правильно.
Можно то же самое проще записать: $P(n,m)=P(n,m-1)+P(n-m,m)$. Ну и положить $P(0,m)=1$, $P(<0,m)=0$, $P(>0,1)=1$.

-- Ср авг 17, 2016 14:18:40 --

Yadryara в сообщении #1144697 писал(а):

Таким образом, для 10-бурлёвой — 40 способов.

У меня получилось 41.

[Yadryara]

worm2
Обратите внимание, я раньше Вас исправил

[RIP]

Предлагается посчитать $p(10)-1$ (A000041). В чём тут олимпиадность?

[worm2]

Вот это да!
Смотрел ведь на эту последовательность, пока думал над задачей. В упор смотрел. И не видел, что это она.

[Yadryara]

Так уже давным-давно есть A000065.