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

[Padawan]

Сколькими способами можно разменять рубль на монеты достоинством в 1, 2, 5, 10, 20 и 50 копеек?

Это первая задача из задачника Полиа, Сеге "Задачи и теоремы из анализа". Я её решил, как мне кажется, дурацким способом, типа составления таблицы, и сведения задачи к аналогичным более простым. Кто знает способ проще?

[Legioner93]

4562?

[Padawan]

Да. Как сделали?

[Xaositect]

Можно ввести $q(n; k_1,\dots,k_m)$ - количество вариантов размена суммы в $n$ копеек монетами достоинств $k_1,\dots,k_m$ и считать с помощью рекуррентного уравнения

$$q(n;k_1,\dots,k_m) = q(n;k_2,\dots,k_m}) + q(n-k_1;k_1,\dots,k_m),\quad q(0;k_1,\dots,k_m) = 1, q(-n;k_1,\dots,k_m) = 0, q(0;) = 1, q(n;) = 0$$

Prelude> let q 0 _ = 1; q n _ | n < 0 = 0; q n [] = 0; q n ks = q n (tail ks) + q (n - (head ks)) ks
Prelude> q 100 [1,2,5,10,20,50]
4562

[Padawan]

Xaositect
Я так и делал. Сначала на бумажке, потом в екселе

[Xaositect]

Ну, если хочется красиво, то можно производящие функции для $q(n;1)$, $q(n;1,2)$, $q(1,2,5)$, $q(n;1,2,5,10)$, $q(n;1,2,5,10,20)$, $q(n;1,2,5,10,20,50)$ последовательно выписать и получить общее выражение, но оно будет страшное.

[Legioner93]

Ну а я набросал рекурсивную процедуру на Pascal (больше ни на чем не умею). Тоже не шибко умно.

[Padawan]

Xaositect
Это вторая задача в задачнике. $f(\zeta)=\dfrac{1}{(1-\zeta)(1-\zeta^2)(1-\zeta^5)(1-\zeta^{10})(1-\zeta^{20})(1-\zeta^{50})}$. Коэффициент при $\zeta^n$ равен $q(n;1,2,5,10,20,50)$.

Только как это поможет найти конкретно это число? Не понял, что значит последовательно выписать?

[Xaositect]

Padawan в сообщении #328319 писал(а):

Только как это поможет найти конкретно это число? Не понял, что значит последовательно выписать?

Я имел в виду, что это выражение не сразу же получается, а последовательно.
$f_1 = \frac{1}{1-\xi}$, $f_2 = \frac{1}{(1-\xi)(1-\xi^2)}$ и т.д.

Ну а как поможет найти...
$\frac{1}{(1-\xi)(1-\xi^2)(1-\xi^5)(1-\xi^{10})(1-\xi^{20})(1-\xi^{50})} = \frac{P(\xi)}{(1-\xi^{100})^6}$, потому что каждый $1-\xi^{k_i}$ делит $1-\xi^{100}$ Для $\frac{1}{(1-\xi)^m}$ ряд можно явно выписать через "цешки", в результате получим какую-то формулу $P(\xi)\sum c_i \xi^{100i}$, для $c_i$ явное выражение.

[Padawan]

Xaositect в сообщении #328335 писал(а):

Я имел в виду, что это выражение не сразу же получается, а последовательно.
$f_1 = \frac{1}{1-\xi}$, $f_2 = \frac{1}{(1-\xi)(1-\xi^2)}$

Зачем последовательно? Сразу видно...

Xaositect в сообщении #328335 писал(а):

Ну а как поможет найти...
$\frac{1}{(1-\xi)(1-\xi^2)(1-\xi^5)(1-\xi^{10})(1-\xi^{20})(1-\xi^{50})} = \frac{P(\xi)}{(1-\xi^{100})^6}$, потому что каждый $1-\xi^{k_i}$ делит $1-\xi^{100}$ Для $\frac{1}{(1-\xi)^m}$ ряд можно явно выписать через "цешки", в результате получим какую-то формулу $P(\xi)\sum c_i \xi^{100i}$, для $c_i$ явное выражение.

$P(\xi)$ получается $600-50-20-10-5-2-1=512$ -ой степени. Жесть . А разложение $\frac{1}{(1-\xi)^m}$ правда простое -- просто $\frac{1}{1-\xi}$ $m$ раз почленно продифференцировать (и еще на $m!$ поделить).

[Xaositect]

Padawan в сообщении писал(а):

Xaositect в сообщении #328335 писал(а):

Ну а как поможет найти...
$\frac{1}{(1-\xi)(1-\xi^2)(1-\xi^5)(1-\xi^{10})(1-\xi^{20})(1-\xi^{50})} = \frac{P(\xi)}{(1-\xi^{100})^6}$, потому что каждый $1-\xi^{k_i}$ делит $1-\xi^{100}$ Для $\frac{1}{(1-\xi)^m}$ ряд можно явно выписать через "цешки", в результате получим какую-то формулу $P(\xi)\sum c_i \xi^{100i}$, для $c_i$ явное выражение.

$P(\xi)$ получается $600-50-20-10-5-2-1=512$ -ой степени. Жесть .

Ну, от него только свободный член и коэффициент при сотой степени потребуются.

[Padawan]

Свободный член -- $1$. А коэффициент при сотой степени -- тайна... Короче, эти соображения конкретно для $n=100$ задачу не помогают решить.

[Casaubon]

Не такая уж и тайна:

$$ P(\xi)=(\xi +1)^2 \left(\xi ^4+\xi ^3+\xi ^2+\xi +1\right)^2 \left(\xi ^{40}-\xi ^{30}+\xi ^{20}-\xi ^{10}+1\right)^6 \left(\xi ^{50}+2 \xi ^{40}+2 \xi ^{30}+2 \xi ^{20}+2 \xi ^{10}+1\right)^5 \left( \xi ^4-\xi ^3+\xi ^2-\xi +1 \right)^3 $$

Правда, всё одно с цешками придётся повозиться.

[Zealint]

Padawan в сообщении #328299 писал(а):

Сколькими способами можно разменять рубль на монеты достоинством в 1, 2, 5, 10, 20 и 50 копеек?

Это первая задача из задачника Полиа, Сеге "Задачи и теоремы из анализа". Я её решил, как мне кажется, дурацким способом, типа составления таблицы, и сведения задачи к аналогичным более простым. Кто знает способ проще?

Вроде было же.
Правильный ответ 343.

-- Вс июн 06, 2010 19:58:17 --

То есть я хотел сказать, что выписывание производящей функции и разложение её в ряд в Maple - это самый простой способ решения. Самый простой из "ручных" способов описан в книге "Конкретная Математика" где-то рядом со страницей 363. Там надо составлять таблицу по принципу сведения задачи к более простой, как, по-видимому, и сделал автор темы. В общем случае задача не решена за $O(1)$ даже для трех произвольных монет. Решение за $O(n)$, конечно, простое, но не считается решением для этой задачи.

[Padawan]

Zealint в сообщении #328414 писал(а):

Вроде было же.
Правильный ответ 343.

Да, только там отсутствуют 2 копеечные