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

Author

T. D. Noe, Mar 07 2011

Keywords

• nonn
• easy

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)

Examples

			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)
		

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).

Crossrefs

Cf. A001299, A001300, A001306, A169718, A002266, A002620, A245573.

Programs

Mathematica

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

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

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)

a(n) = A002620(A002266(n)+2) = floor((floor(n/5) + 2)^2 / 4). - Hoang Xuan Thanh, Jun 26 2025