0,3

There is a unique solution to this puzzle: "There are a prime number of ways that I can make change for n cents using coins of 1, 2, 5, 10 cents; but a semiprime number of ways that I can make change for n-1 cents and for n+1 cents." There is a unique solution to this related puzzle: "There are a prime number of ways that I can make change for n cents using coins of 1, 2, 5, 10 cents; but a 3-almost prime number of ways that I can make change for n-1 cents and for n+1 cents." - Jonathan Vos Post (jvospost2(AT)yahoo.com), Aug 26 2005

X. Gourdon and B. Salvy, Effective asymptotics of linear recurrences with rational coefficients, Discrete Math., 153 (1996), 145-163.

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

G. P\'{o}lya and G. Szeg\"{o}, Problems and Theorems in Analysis, Springer-Verlag, NY, 2 vols., 1972, Vol. 1, p. 1.

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 152.

T. D. Noe, Table of n, a(n) for n = 0..1000

H. Bottomley, Initial terms of A000008, A001301, A001302, A001312, A001313

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 174

Index entries for sequences related to making change.

G.f.: 1/((1-x)(1-x^2)(1-x^5)(1-x^10)). a(n)=a(n-2)+a(n-5)-a(n-7)+a(n-10)-a(n-12)-a(n-15)+a(n-17)+1. a(-18-n)=-a(n).

1/((1-x)*(1-x^2)*(1-x^5)*(1-x^10));

a[n_] := SeriesTerm[1/((1 - x)(1 - x^2)(1 - x^5)(1 - x^10)), {x, 0, n}]

a[n_, d_] := SeriesTerm[1/(Times@@Map[(1-x^#)&, d]), {x, 0, n}] (general case for any set of denominations represented as a list of coin values in cents).

(PARI) a(n)=if(n<-17, -a(-18-n), if(n<0, 0, polcoeff(1/((1-x)*(1-x^2)*(1-x^5)*(1-x^10))+x*O(x^n), n)))

a(n)-a(n-1)=A025810(n).

Adjacent sequences: A000005 A000006 A000007 this_sequence A000009 A000010 A000011

Sequence in context: A029016 A121385 A029015 this_sequence A001312 A001301 A001302

nonn,easy,nice

njas