

A187243


Number of ways of making change for n cents using coins of 1, 5, and 10 cents.


5



1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4, 4, 4, 4, 4, 6, 6, 6, 6, 6, 9, 9, 9, 9, 9, 12, 12, 12, 12, 12, 16, 16, 16, 16, 16, 20, 20, 20, 20, 20, 25, 25, 25, 25, 25, 30, 30, 30, 30, 30, 36, 36, 36, 36, 36, 42, 42, 42, 42, 42, 49, 49, 49, 49, 49, 56, 56, 56, 56, 56, 64, 64, 64, 64, 64, 72, 72, 72, 72, 72
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,6


COMMENTS

a(n) is the number of partitions of n into parts 1, 5, and 10.  Joerg Arndt, Feb 02 2017
From Gerhard Kirchner, Jan 25 2017: (Start)
There is a simple recurrence for solving such problems given coin values 1 = c(1) < c(2) < ... < c(k).
Let f(n, j), 1 < j <= k, be the number of ways of making change for n cents with coin values c(i), 1 <= i <= j. Then any number m of c(j)coins with 0 <= m <= floor(n/c(j)) can be used, and the remaining amount of change to be made using coins of values smaller than c(j) will be n  m*c(j) cents. This leads directly to the recurrence formula with a(n) = f(n, k).
For k = 3 with c(1) = 1, c(2) = 5, c(3) = 10, the recurrence can be reduced to an explicit formula; see link "Derivation of formulas".
By the way, a(n) is also the number of ways of making change for n cents using coins of 2, 5, 10 cents and at most one 1cent coin. That is because any coin combination is, as in the original problem, fixed by the numbers of 5cent and 10cent coins.
(End)


LINKS

Gerhard Kirchner, Table of n, a(n) for n = 0..1000
Gerhard Kirchner, Derivation of formulas
Index entries for sequences related to making change.
Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,1,1,0,0,0,1,1,0,0,0,1,1).


FORMULA

G.f.: 1/((1x)*(1x^5)*(1x^10)).
From Gerhard Kirchner, Jan 25 2017: (Start)
General recurrence: f(n, 1) = 1; j > 1: f(0, j) = 1 or
f(n, j) = Sum_{m=0..floor(n/c(j))} f(nm*c(j), j1);
a(n) = f(n, k).
Note: f(n, j) = f(n, j1) for n < c(j) => f(1, j) = 1.
Explicit formula:
a(n) = (q+1)*(q+1+s) with q = floor(n/10) and s = floor((n mod 10)/5).
(End)


EXAMPLE

From Gerhard Kirchner, Jan 25 2017: (Start)
Recurrence:
a(11) = f(11, 3) = f(11  0, 2) + f(11  10, 2)
= f(11  0, 1) + f(11  5, 1) + f(11  10, 1) + f(1, 2)
= 1 + 1 + 1 + 1 = 4.
Explicitly: a(79) = (7 + 1)*(7 + 1 + 1) = 72.
(End)


MATHEMATICA

CoefficientList[ Series[ 1 / ((1  x)(1  x^5)(1  x^10)), {x, 0, 75} ], x ]


PROG

(PARI) Vec( 1/((1x)*(1x^5)*(1x^10))+O(x^99)) \\ Charles R Greathouse IV, Aug 22 2011
(PARI) a(n)=(n^2+16*n+97+10*(n\5+1)*(5*(n\5)+2n))\100 \\ Tani Akinari, Sep 10 2015
(PARI) a(n) = {my(q=n\10, s=(n%10)\5); (q+1)*(q+1+s); } \\ (Kirchner's explicit formula) Joerg Arndt, Feb 02 2017


CROSSREFS

Cf. A001299, A001300, A001306, A169718, A245573.
Sequence in context: A160675 A105674 A130496 * A001299 A001300 A169718
Adjacent sequences: A187240 A187241 A187242 * A187244 A187245 A187246


KEYWORD

nonn,easy


AUTHOR

T. D. Noe, Mar 07 2011


STATUS

approved



