How many ways can you give change for one dollar?

Answer 1

293 ways.Using pennies, nickels, dimes, quarters, half-dollars and dollar coins, there are 293 ways to make change for one dollar in US currency.

Method 1:

Using pennies, nickels, dimes, quarters, and half-dollars there are 292 ways to make change for one dollar. In general, to make change for h half-dollars using these coins there are (6 + 55*h + 119*h2 + 95*h3 + 25*h4)/6 ways. For example, putting h=1 gives 50 ways of making change for fifty cents, or h=2 gives 292 ways of making change for dollar etc.

[[ The 292 ways computed above, includes fifty-cent pieces but not the dollar coin so, we must add one more in order to agree with the second method shown below. ]]

Method 2:

Take the Taylor expansion of 1 over (1-x)*(1-x5)*(1-x10)*(1-x25)*(1-x50)*(1-x100), and jot down the coefficient of x100. This is the generating function for the ways to partition 100 into subsets of size 1, 5, 10, 25, 50, or 100, so there are 293 ways to make change for one us dollar.

[[ if we use no dollar coins or half dollars (only pennies, nickels, dimes and quarters) the method 2 gives 242 ways to make a dollar. Those 242 ways begin with line 52. ]]

Indisputable Tally of Combinations

1. 1 dollar coin
2. 2 half dollars
3. 1 HD 2Q
4. 1 HD 1Q 2D IN
5. 1 HD 1Q 2D 5P
6. 1 HD 1Q 1D 3N
7. 1 HD 1Q 1D 2N 5P
8. 1 HD 1Q 1D 1N 10P
9. 1 HD 1Q 1D 15P
10. 1 HD 1Q 5N
11. 1 HD 1Q 4N 5P
12. 1 HD 1Q 3N 10P
13. 1 HD 1Q 2N 15P
14. 1 HD 1Q 1N 20P
15. 1 HD 1Q 25P
16. 1 HD 5D
17. 1 HD 4D 2N
18. 1 HD 4D 1N 5P
19. 1 HD 4D 10P
20. 1 HD 3D 4N
21. 1 HD 3D 3N 5P
22. 1 HD 3D 2N 10P
23. 1 HD 3D 1N 15P
24. 1 HD 3D 20P
25. 1 HD 2D 6N
26. 1 HD 2D 5N 5P
27. 1 HD 2D 4N 10P
28. 1 HD 2D 3N 15P
29. 1 HD 2D 2N 20P
30. 1 HD 2D 1N 25P
31. 1 HD 2D 30P
32. 1 HD 1D 8N
33. 1 HD 1D 7N 5P
34. 1 HD 1D 6N 10P
35. 1 HD 1D 5N 15P
36. 1 HD 1D 4N 20P
37. 1 HD 1D 3N 25 P
38. 1 HD 1D 2N 30 P
39. 1 HD 1D 1N 35P
40. 1 HD 1D 40P
41. 1 HD 10N
42. 1 HD 9N 5P
43. 1 HD 8N 10P
44. 1 HD 7N 15P
45. 1 HD 6N 20P
46. 1 HD 5N 25P
47. 1 HD 4N 30P
48. 1 HD 3N 35P
49. 1 HD 2N 40P
50. 1 HD 1N 45P
51. 1 HD 50P
52. 4Q
53. 3Q 2D 1N
54. 3Q 2D 5P
55. 3Q 1D 3N
56. 3Q 1D 2N 5P
57. 3Q 1D 1N 10P
58. 3Q 1D 15P
59. 3Q 5N
60. 3Q 4N 5P
61. 3Q 3N 10P
62. 3Q 2N 15P
63. 3Q 1N 20P
64. 3Q 25P
65. 2Q 5D
66. 2Q 4D 2N
67. 2Q 4D 1N 5P
68. 2Q 4D 10P
69. 2Q 3D 4N
70. 2Q 3D 3N 5P
71. 2Q 3D 2N 10P
72. 2Q 3D 1N 15P
73. 2Q 3D 20P
74. 2Q 2D 6N
75. 2Q 2D 5N 5P
76. 2Q 2D 4N 10P
77. 2Q 2D 3N 15P
78. 2Q 2D 2N 20P
79. 2Q 2D 1N 25P
80. 2Q 2D 30P
81. 2Q 1D 8N
82. 2Q 1D 7N 5P
83. 2Q 1D 6N 10P
84. 2Q 1D 5N 15P
85. 2Q 1D 4N 20P
86. 2Q 1D 3N 25P
87. 2Q 1D 2N 30P
88. 2Q 1D 1N 35P
89. 2Q 1D 40P
90. 2Q 50P
91. 2Q 10N
92. 2Q 9N 5P
93. 2Q 8N 10P
94. 2Q 7N 15P
95. 2Q 6N 20P
96. 2Q 5N 25P
97. 2Q 4N 30P
98. 2Q 3N 35P
99. 2Q 2N 40P
100. 2Q 1N 45P
101. 1Q 7D 1N
102. 1Q 7D 5P
103. 1Q 6D 3N
104. 1Q 6D 2N 5P
105. 1Q 6D 1N 10P
106. 1Q 6D 15P
107. 1Q 5D 5N
108. 1Q 5D 4N 5P
109. 1Q 5D 3N 10P
110. 1Q 5D 2N 15P
111. 1Q 5D 1N 20P
112. 1Q 5D 25P
113. 1Q 4D 7N
114. 1Q 4D 6N 5P
115. 1Q 4D 5N 15P
116. 1Q 4D 4N 20P
117. 1Q 4D 3N 25P
118. 1Q 4D 2N 30P
119. 1Q 4D 1N 35P
120. 1Q 4D 40P
121. 1Q 3D 9N
122. 1Q 3D 8N 5P
123. 1Q 3D 7N 10P
124. 1Q 3D 6N 15P
125. 1Q 3D 5N 20P
126. 1Q 3D 4N 25P
127. 1Q 3D 3N 30P
128. 1Q 3D 2N 35P
129. 1Q 3D 1N 40P
130. 1Q 3D 45P
131. 1Q 2D 11N
132. 1Q 2D 10N 5P
133. 1Q 2D 9N 10P
134. 1Q 2D 8N 15P
135. 1Q 2D 7N 20P
136. 1Q 2D 6N 25P
137. 1Q 2D 5N 30P
138. 1Q 2D 4N 35P
139. 1Q 2D 3N 40P
140. 1Q 2D 2N 45P
141. 1Q 2D 1N 50P
142. 1Q 2D 55P
143. 1Q 1D 13N
144. 1Q 1D 12N 5P
145. 1Q 1D 11N 10P
146. 1Q 1D 10N 15P
147. 1Q 1D 9N 20P
148. 1Q 1D 8N 25P
149. 1Q 1D 7N 30P
150. 1Q 1D 6N 35P
151. 1Q 1D 5N 40P
152. 1Q 1D 4N 45P
153. 1Q 1D 3N 50P
154. 1Q 1D 2N 55P
155. 1Q 1D 1N 60P
156. 1Q 1D 65P
157. 1Q 15N
158. 1Q 14N 5P
159. 1Q 13N 10P
160. 1Q 12N 15P
161. 1Q 11N 20P
162. 1Q 10N 25P
163. 1Q 9N 30P
164. 1Q 8N 35P
165. 1Q 7N 40P
166. 1Q 6N 45P
167. 1Q 5N 50P
168. 1Q 4N 55P
169. 1Q 3N 60P
170. 1Q 2N 65P
171. 1Q 1N 70P
172. 1Q 75P
173. 10D
174. 9D 2N
175. 9D 1N 5P
176. 9D 10P
177. 8D 4N
178. 8D 3N 5P
179. 8D 2N 10P
180. 8D 1N 15P
181. 8D 20P
182. 7D 6N
183. 7D 5N 5P
184. 7D 4N 10P
185. 7D 3N 15P
186. 7D 2N 20P
187. 7D 1N 25P
188. 7D 30P
189. 6D 8N
190. 6D 7N 5P
191. 6D 6N 10P
192. 6D 5N 15P
193. 6D 4N 20P
194. 6D 3N 25P
195. 6D 2N 30P
196. 6D 1N 35P
197. 6D 40P
198. 5D 10N
199. 5D 9N 5P
200. 5D 8N 10P
201. 5D 7N 15P
202. 5D 6N 20P
203. 5D 5N 25P
204. 5D 4N 30P
205. 5D 3N 35P
206. 5D 2N 40P
207. 5D 1N 45P
208. 5D 50P
209. 4D 12N
210. 4D 11N 5P
211. 4D 10N 10P
212. 4D 9N 15P
213. 4D 8N 20P
214. 4D 7N 25P
215. 4D 6N 30P
216. 4D 5N 35P
217. 4D 4N 40P
218. 4D 3N 45P
219. 4D 2N 50P
220. 4D 1N 55P
221. 4D 60P
222. 3D 14N
223. 3D 13N 5P
224. 3D 12N 10P
225. 3D 11N 15P
226. 3D 10N 20P
227. 3D 9N 25P
228. 3D 8N 30P
229. 3D 7N 35P
230. 3D 6N 40P
231. 3D 5N 45P
232. 3D 4N 50P
233. 3D 3N 55P
234. 3D 2N 60P
235. 3D 1N 65P
236. 3D 70P
237. 2D 16N
238. 2D 15N 5P
239. 2D 14N 10P
240. 2D 13N 15P
241. 2D 12N 20P
242. 2D 11N 25P
243. 2D 10N 30P
244. 2D 9N 35P
245. 2D 8N 40P
246. 2D 7N 45P
247. 2D 6N 50P
248. 2D 5N 55P
249. 2D 4N 60P
250. 2D 3N 65P
251. 2D 2N 70P
252. 2D 1N 75P
253. 2D 80P
254. 1D 18N
255. 1D 17N 5P
256. 1D 16N 10P
257. 1D 15N 15P
258. 1D 14N 20P
259. 1D 13N 25P
260. 1D 12N 30P
261. 1D 11N 35P
262. 1D 10N 40P
263. 1D 9N 45P
264. 1D 8N 50P
265. 1D 7N 55P
266. 1D 6N 60P
267. 1D 5N 65P
268. 1D 4N 70P
269. 1D 3N 75P
270. 1D 2N 80P
271. 1D 1N 85P
272. 1D 90P
273. 20N
274. 19N 5P
275. 18N 10P
276. 17N 15P
277. 16N 20P
278. 15N 25P
279. 14N 30P
280. 13N 35P
281. 12N 40P
282. 11N 45P
283. 10N 50P
284. 9N 55P
285. 8N 60P
286. 7N 65P
287. 6N 70P
288. 5N 75P
289. 4N 80P
290. 3N 85P
291. 2N 90P
292. 1N 95P
293. 100P

WHEW!!!