Can Generating Functions Simplify the Calculation of Currency Combinations?

In summary: These keywords are often associated with a similar problem known as the "coin change problem", which deals with finding the number of ways to make change using a set of coins instead of bills. There may be some overlap in the approaches used to solve these types of problems.
  • #1
Isaac0427
Insights Author
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!
 
  • Like
Likes member 587159
Physics news on Phys.org
  • #2
Have you tried generating a few terms and searching OEIS?
 
  • Like
Likes Isaac0427
  • #3
pbuk said:
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.
 
Last edited:
  • #4
Isaac0427 said:
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".
 

Related to Can Generating Functions Simplify the Calculation of Currency Combinations?

1. What is combinatorics?

Combinatorics is a branch of mathematics that deals with counting and arranging objects or events in a systematic way.

2. What is a "weird" combinatorics question?

A "weird" combinatorics question is one that involves a unique or unusual scenario that requires creative thinking and problem-solving skills to solve.

3. How is combinatorics used in real life?

Combinatorics has many practical applications, such as in computer science, cryptography, genetics, and economics. It is also used in everyday tasks like scheduling, voting systems, and game theory.

4. What are some common techniques used in combinatorics?

Some common techniques used in combinatorics include permutations, combinations, binomial coefficients, and the pigeonhole principle.

5. How can I improve my skills in combinatorics?

The best way to improve your skills in combinatorics is to practice solving a variety of problems and familiarize yourself with different techniques and strategies. It can also be helpful to study and understand the underlying principles and theories behind combinatorics.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
9
Views
2K
Replies
1
Views
654
Replies
7
Views
2K
  • Topology and Analysis
Replies
21
Views
2K
Replies
41
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
12
Views
1K
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
16
Views
2K
Back
Top