математика - Сколькими способами можно наклеить марки на 50 коп?

Один из способов подсчёта может быть таков. Обозначим через $%a_n$% количество способов наклеить марки общей стоимостью $%n$% копеек. Нам требуется найти $%a_{50}$%. Очевидно, что $%a_0=1$% (если стоимость равна нулю, то имеется всего один способ наклеить марки, оставив чистый лист). Также удобно считать, что члены с отрицательными индексами равны нулю. Тогда имеет место следующая рекуррентная формула: $%a_n=a_{n-3}+a_{n-5}+a_{n-10}+a_{n-20}$%, справедливая для всех $%n\ge1$%. В соответствии с этой формулой находим последовательно все нужные значения. Они таковы: 0, 0, 1, 0, 1, 1, 0, 2, 1, 2, 3, 1, 5, 4, 4, 9, 5, 11, 14, 12, 23, 20, 29, 41, 37, 62, 66, 79, 118, 117, 167, 205, 230, 330, 363, 468, 606, 683, 930, 1098, 1341, 1761, 2040, 2642, 3259, 3911, 5075, 6061, 7601, 9549. Последнее значение будет ответом.

Общее описание здесь таково: если мы разложим в степенной ряд рациональную функцию $$f(t)=\frac1{1-t^3-t^5-t^{10}-t^{20}},$$ то коэффициент при $%t^n$% будет равен $%z_n$%.

Возможны и другие принципы подсчёта, но они тоже требуют вычислений. Например, можно заметить, что число трёхкопеечных марок кратно пяти. Оно может принимать значения 0, 5, 10, 15. Каждый из этих случаев отдельно разбираем, а получаемые величины суммируем. Для примера: если количество марок по 3 коп. равно, скажем, 10, то далее надо набрать сумму 20 коп. через 5, 10 и 20. Это эквивалентно тому, что мы набираем 4 коп. через 1, 2 и 4 (после сокращения на 5 все величины сильно уменьшаются). Здесь все способы можно перечислить, а затем понять, сколькими способами мы можем вставить трёхкопеечные марки между остальными. Например, если 4 записано как 2+1+1, то сама расстановка этого типа может быть осуществлена 3 способами, так как порядок важен. Добавить же 10 марок к трём имеющимся можно $%C_{10+3}^3$% способами.