login
Number of (unordered) ways of making change for n cents using coins of 5, 10, 20, 50, 100 cents.
2

%I #37 Apr 18 2017 07:02:36

%S 1,0,0,0,0,1,0,0,0,0,2,0,0,0,0,2,0,0,0,0,4,0,0,0,0,4,0,0,0,0,6,0,0,0,

%T 0,6,0,0,0,0,9,0,0,0,0,9,0,0,0,0,13,0,0,0,0,13,0,0,0,0,18,0,0,0,0,18,

%U 0,0,0,0,24,0,0,0,0,24,0,0,0,0,31,0,0,0,0

%N Number of (unordered) ways of making change for n cents using coins of 5, 10, 20, 50, 100 cents.

%C Number of partitions of n into parts 5, 10, 20, 50, and 100. - _Joerg Arndt_, Sep 05 2014

%D R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 316.

%D G. Pólya and G. Szegő, Problems and Theorems in Analysis, Springer-Verlag, NY, 2 vols., 1972, Vol. 1, p. 1.

%H T. D. Noe, <a href="/A001343/b001343.txt">Table of n, a(n) for n = 0..1000</a>

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=185">Encyclopedia of Combinatorial Structures 185</a>

%H <a href="/index/Rec#order_185">Index entries for linear recurrences with constant coefficients</a>, order 185.

%H <a href="/index/Mag#change">Index entries for sequences related to making change.</a>

%F G.f.: 1/((1-x^5)*(1-x^10)*(1-x^20)*(1-x^50)*(1-x^100)).

%p 1/(1-x^5)/(1-x^10)/(1-x^20)/(1-x^50)/(1-x^100): seq(coeff(series(%,x,n+1),x,n), n=0..80);

%t nn = 100; CoefficientList[Series[1/((1 - x^5) (1 - x^10) (1 - x^20) (1 - x^50) (1 - x^100)), {x, 0, nn}], x] (* _T. D. Noe_, Jun 28 2012 *)

%t Table[Length[FrobeniusSolve[{5,10,20,50,100},n]],{n,0,80}] (* very slow, _Harvey P. Dale_, May 19 2012 *)

%o (PARI) a(n)=(n%5<1)*floor(((n\10)^4+38*(n\10)^3+476*(n\10)^2+2185*(n\10)+3734)/2400+(n\10+1)*(-1)^(n\10)/160+(n\10\5+1)*[0,0,1,0,-1][n\10%5+1]/10) \\ _Tani Akinari_, May 14 2014

%K nonn

%O 0,11

%A _N. J. A. Sloane_, _Simon Plouffe_