login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A187243 Number of ways of making change for n cents using coins of 1, 5, and 10 cents. 4
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 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 20 02:47 EST 2018. Contains 299357 sequences. (Running on oeis4.)