This site is supported by donations to The OEIS Foundation. 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 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
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified November 18 04:44 EST 2019. Contains 329248 sequences. (Running on oeis4.)