|
%I #44 Mar 15 2017 19:59:36
%S 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,
%T 16,16,16,16,20,20,20,20,20,25,25,25,25,25,30,30,30,30,30,36,36,36,36,
%U 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
%N Number of ways of making change for n cents using coins of 1, 5, and 10 cents.
%C a(n) is the number of partitions of n into parts 1, 5, and 10. - _Joerg Arndt_, Feb 02 2017
%C From _Gerhard Kirchner_, Jan 25 2017: (Start)
%C There is a simple recurrence for solving such problems given coin values 1 = c(1) < c(2) < ... < c(k).
%C 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).
%C 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".
%C 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.
%C (End)
%H Gerhard Kirchner, <a href="/A187243/b187243.txt">Table of n, a(n) for n = 0..1000</a>
%H Gerhard Kirchner, <a href="/A187243/a187243_1.pdf">Derivation of formulas</a>
%H <a href="/index/Mag#change">Index entries for sequences related to making change.</a>
%H <a href="/index/Rec#order_16">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,0,0,1,-1,0,0,0,1,-1,0,0,0,-1,1).
%F G.f.: 1/((1-x)*(1-x^5)*(1-x^10)).
%F From _Gerhard Kirchner_, Jan 25 2017: (Start)
%F General recurrence: f(n, 1) = 1; j > 1: f(0, j) = 1 or
%F f(n, j) = Sum_{m=0..floor(n/c(j))} f(n-m*c(j), j-1);
%F a(n) = f(n, k).
%F Note: f(n, j) = f(n, j-1) for n < c(j) => f(1, j) = 1.
%F Explicit formula:
%F a(n) = (q+1)*(q+1+s) with q = floor(n/10) and s = floor((n mod 10)/5).
%F (End)
%e From _Gerhard Kirchner_, Jan 25 2017: (Start)
%e Recurrence:
%e a(11) = f(11, 3) = f(11 - 0, 2) + f(11 - 10, 2)
%e = f(11 - 0, 1) + f(11 - 5, 1) + f(11 - 10, 1) + f(1, 2)
%e = 1 + 1 + 1 + 1 = 4.
%e Explicitly: a(79) = (7 + 1)*(7 + 1 + 1) = 72.
%e (End)
%t CoefficientList[ Series[ 1 / ((1 - x)(1 - x^5)(1 - x^10)), {x, 0, 75} ], x ]
%o (PARI) Vec( 1/((1-x)*(1-x^5)*(1-x^10))+O(x^99)) \\ _Charles R Greathouse IV_, Aug 22 2011
%o (PARI) a(n)=(n^2+16*n+97+10*(n\5+1)*(5*(n\5)+2-n))\100 \\ _Tani Akinari_, Sep 10 2015
%o (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
%Y Cf. A001299, A001300, A001306, A169718, A245573.
%K nonn,easy
%O 0,6
%A _T. D. Noe_, Mar 07 2011
|
