Can Generating Functions Simplify the Calculation of Currency Combinations?

[Isaac0427]

TL;DR

A currency consists of a $1 bill, a $2 bill, a $3 bill, etc. up until an $N bill. How many ways can one make d dollars with these bills?

This is an interesting combinatorics problem that I thought of. Oddly, I think I know of an application of said problem to physics, but I could not find any problem like it online (the closest I got was the Knapsack problem, which is just about optimization). My initial instinct was to look for patterns in simpler cases, which I did. For notation, let $f_N(d)$ be the number of ways to make d dollars with $1 through $N bills (using as many of each type of bill as you want). Here are my first results:
$$f_1(d)=1$$
$$f_2(d)=
\left\{\begin{matrix}
\frac{d}{2}+1, & d=2n\\
\frac{d}{2}+\frac{1}{2}, & d=2n-1
\end{matrix}\right.$$
where n and d are natural numbers.

I also came up with this recursion relation:
$$f_{N+1}(d)=f_N(d)+f_N(d-N)+f_N(d-2N)+f_N(d-3N)+...=\sum_{j=0}^{\infty}f_N(d-jN)$$
where $f_N(0)=1$ and $f_N(-d)=0$ for all natural numbers N and d. I believe this recursion relation is correct but I am not 100% positive.

This is not easily usable for calculating $f_N(d)$ for N larger than 4 or 5, which is where my question lies: can one get a simple-ish closed form expression for $f_N(d)$, and if so, what is it? I am especially (though not exclusively) interested in an approximation for large N and an approximation for large d.

Note: A helpful way I found to think about this is having N buckets to place d balls in, with the condition that the number of balls in the 2nd bucket must be divisible by 2 (including zero), the number of balls in the 3rd bucket must be divisible by 3 (again, including zero), etc.

Thank you in advance for any insight you may give on this problem!

 

[pbuk]

Have you tried generating a few terms and searching OEIS?

 

[Isaac0427]

Have you tried generating a few terms and searching OEIS?

Thank you! I just coded a python program using my recursion relation (which I convinced myself was correct), and put it into OEIS for various values of N.

I see now that $f_N(d)$ is asking how many partitions of d are there with no term greater than N. Thank you!

The only remaining question is looking for an approximation for large N and an approximation for large d. I read that for the question of how many partitions exist for an integer n, while there is no closed-form expression, Hardy and Ramanujan came up with an approximation for large n. This would intuitively tell me that my variation of the problem would not have a closed-form solution, but there are likely to be good approximations. I'm doing more research on this-- if anyone has seen anything like this before, please let me know!

Thank you,
Isaac

EDIT: Here is my search for N=12. It shows the following general formula, but that formula does not work, assuming I am using it correctly:
$$f_{12}(x)=\prod_{k=1}^{12} \frac{1}{1-x^k}$$

Plugging in values for x did not get me the right terms of the sequence, even just the ones I put in my search.

 

[Stephen Tashi]

Summary:: A currency consists of a $1 bill, a $2 bill, a $3 bill, etc. up until an $N bill. How many ways can one make d dollars with these bills?

I suggest looking up the keywords: "generating functions, making change".