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