Money Changing Problem - Denumerants Consider partitions of n whose summands are taken (repetitions allowed) from a sequence of integers (a) := (a1, a2, ...), 1 <= a1 < a2 < ... Giving such a partition is equivalent to giving a solution of [1] a1 x1 + a2 x2 + a3 x3 + ... = n, x_i nonnegative integers. Theorem A: The generating function of the number D(n;(a)) = D(n; a1, a2, ...) of solutions of [1], called the denumerant of n with respect to the sequence (a), equals: [2] DGF(t;(a)) := 1 + Sum_{n>=1} D(n;(a)) t^n = Product_{i>=1} 1/(1 - t^{a_i}) Basic Recursion: D(n; a1, a2, a3, ...) = D(n; a2, a3, ...) + D(n-a1; a1, a2, a3, ...) for n > 0 D(0; a1, a2, a3, ...) = 1 D(n; a1, a2, a3, ...) = 0 for n < 0 D(n; ) = 0 for n != 0 Theorem B: [Bell, 1943] Let A be the least common multiple of the integers (a1, a2, ..., a_k). For every integer B such that 0 <= B < A, and every integer m>=0, we have [3] D(Am+B; a1, a2, ..., a_k) = c0 + c1 m + ... + c_{k-1} m^(k-1), where the c_i, i>=0, are constants independent of m. The constants are fully determined when the denumerant is known for k different values of m, say n1, n2, ..., n_k, or, what is the same thing, D(Am + B) may be expressed uniquely in terms of D(A m1 + B), D(A m2 + B), ..., D(A m_k + B). In fact, by Lagrange's interpolation formula D(Am + B) = Sum_{j=1..k} F_j(m)/F_j(m_j) D(A m_j + B) where F(x) = (x - m1)(x - m2)...(x - m_k), and F_j(x) = F(x)/(x - m_j). Putting m_j = j, this becomes D(Am + B) = Binomial(m-1, k) Sum_{j=1..k} (-1)^(k-j) Binomial(k, j) j D(Aj + B) / (m-j) Thus the denumerant is determined for all values of m when it is known for Ak values of m. For three parts a1, a2, a3, this equation becomes 2 D(Am + B) = (m-2)(m-3) D(A + B) - 2(m-1)(m-3) D(2A + B) + (m-1)(m-2) D(3A + B) Example: [Com74, p110, [6g]] Use of the function ||x||, the integer closest to x. D(n;1,2) = ||(2n+3)/4|| Example: [Com74, p110, [6g']] Use of the function ||x||, the integer closest to x. D(n;1,2,3) = ||(n+3)^2/12|| Example: [Com74, p112, [6q]] Use of the function ||x||, the integer closest to x. D(n;1,2,4) = ||((n+2)(n+5) + n*(-1)^n)/16|| Example: [Com74, p120 2.Supp.15] Use of the function ||x||, the integer closest to x. D(n;1,2,5) = ||(n+4)^2/20|| Example: [Com74, p120 2.Supp.15] Use of the function ||x||, the integer closest to x. D(n;1,2,3,5) = ||(n+3)(2n+9)(n+9)/360|| = ||(n+2)(n+8)(2n+13)/360|| For plenty of other such formulas, see [Popoviciu, 1953]. Theorem B gives some shortcuts for the calculation of D(100n;1,2,5,10,20,50,100,200,500). This is the money changing problem for the Euro. Using difference schemes you can switch to step of 10 if you have the values for 0, 10, and 20. Later you can switch to steps of 100. Difference Scheme of D(10n;1,2,5) 0 10 20 30 40 50 60 70 80 90 100 ----------------------------------------- 1 10 29 58 97 146 205 274 353 442 541 9 19 29 39 49 59 69 79 89 99 10 10 10 10 10 10 10 10 10 0 10 20 30 40 50 60 70 80 90 100 10n --------------------------------------------------- 1 10 29 58 97 146 205 274 353 442 541 D(10n;1,2,5) 1 11 40 98 195 341 546 820 1173 1615 2156 D(10n;1,2,5,10) 1 11 41 109 236 450 782 1270 1955 2885 4111 D(10n;1,2,5,10,20) 1 11 41 109 236 451 793 1311 2064 3121 4562 D(10n;1,2,5,10,20,50) Difference Scheme of D(100n;1,2,5,10,20,50) 0 100 200 300 400 500 600 ------------------------------------------------- 1 4562 69118 393119 1420015 3937256 9176292 4561 64556 324001 1026896 2517241 5239036 59995 259445 702895 1490345 2721795 199450 443450 787450 1231450 244000 344000 444000 100000 100000 0 100 200 300 400 500 600 100n ------------------------------------------------- 1 4562 69118 393119 1420015 3937256 9176292 D(100n;1,2,5,10,20,50) 1 4563 73681 466800 1886815 5824071 15000363 D(100n;1,2,5,...,50,100) 1 4563 73682 471363 1960497 6295434 16960860 D(100n;1,2,5,...,100,200) 1 4563 73682 471363 1960497 6295435 16965423 D(100n;1,2,5,...,200,500) References: Ahr18: W. Ahrens; Altes und Neues aus der Unterhaltungsmathematik, Springer Verlag, Berlin, 1918, p 34-40 Bel38: Bell, E.T. Notes on denumerants. (English) J. Indian Math. Soc., n. Ser. 3, 41-45 (1938). Zbl 019.10403 Bell, E.T. Bel43: Bell, E.T.; Interpolated denumerants and Lambert series. American Journal of Mathematics 65, 382-386 (1943) Zbl. 060.09603 Let D(n) = D(n|a1, a2, ..., a_r), the denumerant of the non-negative denote the number of non-negative integer solutions (x1, ..., x_r) of a1 x1 + a2 x2 + a3 x3 + ... = n. In an elementary way it is proved that D(am+b) is a polynomial in m of degree r-1, where a is the least common multiple of the integers (a1, a2, ..., a_r) and b any constant. An application is made on the power series of a special generalized Lambert series. BlF62: Gunnar Blom, Carl-Erik Fr\"oberg; On money changing (swedish) Nordisk Matematisk Tidskrift. Normat. 10, (1962) 55-69 engl. summary 103 Zbl 114.01103 Die Anzahl der Darstellungen eines Geldbetrages n durch M\"unzsorten im Wert von a_1, a_2, ..., a_m sei D(n). Verschiedene Berechningsmethoden von D(n) verden betrachtet, exakte und approximative. n^(m-1) <= (m-1)! a_1 a_2 ... a_m D(n) <= (n+d_m)^(m-1) mit d_1 = 0, d_2 = a_2 und d_k = a_2 + (a_3 + ... + a_k)/2 wenn k>2. Weiterhin wird das bina\"are M\"unzsystem a_k = 2^(k-1) untersucht. Com74: Louis Comtet; Advanced Combinatorics, Reidel Publishing Company, Dordrecht (1974) Chap. 2: Partitions of Integers Chap. 2.6: Partitions with forbidden summands; Denumerants Euro: http://europa.eu.int/euro/ Coins and Notes: the 1-2-5 system 1,2,5, 10,20,50, 100,200,500, ... Gla09a: Glaisher; On the number of partitions of a number into a given number of parts, Quart. J. M. 40 (1909) 57-143 Gla09b: Glaisher; Formulae for partitions into given elements ..., Quart. J. M. 40 (1909) 275-348 GKP90: R. L. Graham, D. E. Knuth and O. Patashnik; Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 316. Count the 50 ways to change the 50 cents. Her18: Herschel; On circulating functions, and on the integration of a class of equations of finite differences into which they enter as coefficients, Philosophical Transactions of the Royal Society, 108 (1818) 144-168 Jeg73: Max Jeger; Einf\"uhrung in die Kombinatorik, Band 1, Klett Studienb\"ucher, Stuttgart, 1973, ISBN 3-12-983200-9 Chap 4.1: Partitionen ..., Geldwechselprobleme Chap 4.2: Frankaturprobleme Jeg76: Max Jeger; Einf\"uhrung in die Kombinatorik, Band 2, Klett Studienb\"ucher, Stuttgart, 1976, ISBN 3-12-983210-6 Chap 4.2: Partitionen Chap 4.5: Frankaturprobleme Jeg86: Max Jeger; Computer Streifz\"uge, eine Einf\"uhrung in Zahlentheorie und Kombinatorik aus algorithmischer Sicht, Birkh\"auser Verlag, Basel, 1986, ISBN 3-7643-1690-X Chap 7.4: Partitionen D(n;1,2,5) = ||(n+4)^2/20|| D(n;1,2,5,10,20,50) = Sum_{n1 + 10n2 = n} D(n1;1,2,5) D(10n2;10,20,50) Pol56: G. Polya; On picture writing American Mathematical Monthly 63 (1956) 689-697 #ZfM 74 p250 (R. Sprague) Mit Hilfe einer Art von Bilderschrift wird die Methode der erzeugenden Funktionen f\"ur folgende Fragen anschaulich entwickelt: 1. auf wieviel Arten man einen Dollar wechseln kann, 2. auf wieviele Arten ein konvexes n-Eck durch n-3 Diagonalen in n-2 Dreiecke zerlegt wird, 3. wieviele B\"aume mit n Knotenpunkten es gibt. #MR 18:458 PoS72: G. P\'{o}lya and G. Szeg\"{o}; Problems and Theorems in Analysis, Springer-Verlag, NY, 2 vols., 1972, Vol. 1, p. 1. Problems 1 - 9. PTW83: G. Polya, R. E. Tarjan, D. R. Woods; Notes on Introductory Combinatorics Birkh\"auser 1983 #MR 85k:05001 (B. M. E. Moret) Pop53: Popoviciu; Asupra unei probleme de partitie a numerelor, Cluf., (1953) 7-58 Rio58: John Riordan; An Introduction to Combinatorial Analysis, New York, John Wiley, 1958 Chap 6: Partitions, Compositions, Trees, and Networks Chap 6.4: Denumerants Wil90: Herbert S. Wilf; generatingfunctionology, Academic Press, 1994, 2nd Edition downloadable at http://www.cis.upenn.edu/~wilf/ Chap 3: Cards, Decks, and Hands: The Exponential Formula Chap 3:15: The money changing problem Wil00: Herbert S. Wilf; Lectures on Integer Partitions, (2000) http://www.math.upenn.edu/~wilf/PIMS/PIMSLectures.pdf YaY64: A. M. Yaglom and I. M. Yaglom; Challenging Mathematical Problems with Elementary Solutions. Vol. I. Combinatorial Analysis and Probability Theory. New York: Dover Publications, Inc., 1987, ISBN 0-486-65536-9 (1st. publ.: San Francisco: Holden-Day, Inc., 1964) problem 23: In how many ways can a total postage of n cents be put together using a. 1-, 2-, and 3-cent stamps? b. 1-, 2-, and 5-cent stamps? problem 24: In how many ways can a 100-dollar bill be changed into 1-, 2-, 5-, 10-, 20-, and 50-dollar bills? solution 23a: ||(n+3)^2/12|| solution 23b: ||(n+4)^2/20|| solution 24: let d(n) = ||(n+4)^2/20|| then Sum(i+j=10, d(10i)*d(j)) = d(0)*d(10) + d(10)*d(9) + d(20)*d(8) + ... + d(80)*d(2) + d(90)*d(1) + d(100)*d(0) = 4562 Lis95: P. Lisonek; Denumerants and their approximations. Journal of Combinatorial Mathematics and Combinatorial Computing 18 (1995), 225-232. Zbl 833.68086 Abstract: Let $a,b,c$ be fixed, pairwise relatively prime positive integers. We investigate the number of non-negative integral solutions of the equation $ax+by+cz=n$ as a function of $n$. We present a new algorithm that computes the ``closed form'' of this function. This algorithm is simple and its time performance is better than the performance of yet known algorithms. We also recall how to approximate the above mentioned function by a polynomial and we derive bounds on the ``error'' of this approximation for the case $a=1$. Encyclopedia of Integer Sequences http://www.research.att.com/~njas/sequences/ A000115: Denumerants: expansion of 1 / (1 - x)(1 - x^2)(1 - x^5) A000008: Ways of making change for n cents using coins of 1, 2, 5, 10 cents. A001300: Ways of making change for n cents using coins of 1, 5, 10, 25, 50 cents. A001312: Ways of making change for n cents using coins of 1, 2, 5, 10, 50, 100 cents. A001313: Ways of making change for n cents using coins of 1, 2, 5, 10, 20, 50 cents. A001364: Ways of making change for n cents using coins of 1, 2, 4, 12, 24, 48, 96, 120 cents (based on English coinage of 1939). More precisely number of ways of making change for n farthings. The coins were farthing, halfpenny, penny, threepence, sixpence, shilling, florin, half-crown. A057537: Ways of making change for n Euro-cents using the Euro currency (coins and bills of size 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000 cents). A002577: Partitions of 2^n into powers of 2. and many other sequences (search for cents). QUESTIONABLE MATHEMATICS. Al Zimmermann reports that: "About three years ago I went to a Citibank ATM in midtown Manhattan to withdraw some cash. The machine rejected my request with the following message: I cannot give you $130 because I only have bills in $50 and $20 denominations. Please choose another amount." Of course $130 = $50 + 4 x $20. -- http://www.mathematik.uni-bielefeld.de/~sillke/ mailto:Torsten.Sillke@uni-bielefeld.de