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

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

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 1-cent coin. That is because any coin combination is, as in the original problem, fixed by the numbers of 5-cent and 10-cent 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/((1-x)*(1-x^5)*(1-x^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(n-m*c(j), j-1);

a(n) = f(n, k).

Note: f(n, j) = f(n, j-1) 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/((1-x)*(1-x^5)*(1-x^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)+2-n))\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