- #1
- 716
- 162
- TL;DR 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?
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!
$$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!