How Many Permutations of Coins Meet a Specific Value Threshold?

[adoado]

Hey all,

I recently encountered a problem that I cannot seem to solve...

Let's say I have the following coins A, B, C, D and E, each one with an associated integer value such that:

A = 1
B = 2
C = 3
D = 4
E = 5

Let's say I can pick N of them, and order does matter (so ABC is not equal to BCA, so we are dealing with permutations I would assume). How many combinations (of size N) exist such that the total sum of their values is equal to or greater than some integer J?

For example, how many permutations (pairs of 2) exist such that their sum is equal to or greater than 9? Clearly only two pairs, DE (4+5) and ED (5+4)... I have found a formula to deal with pairs, but I cannot find anyway to generalize it based on permutations of length N..

Any help would be greatly appreciated!

Thanks,
Adrian

 

[Stephen Tashi]

I recently encountered a problem that I cannot seem to solve...

What do you consider a solution? It wouldn't be hard to write a computer algorithm to get the numerical answer. Did you want a symbolic expression?

...so we are dealing with permutations I would assume). How many combinations (of size N) exist...

Is it going to be "permutations" or is it going to be "combinations"?

To get a symbolic expression, I don't know how to solve the problem for either case! My suggestion is to try generating functions.

For example, when the expression:
$$(yx^1 + yx^2 + yx^3 + yx^4 + yx^5)^3$$
is simplified, the coefficient of $y^3 x^9$ would be the number of possible combinations of three distince integers from the set {1,2,3,4,5} whose sum is exactly 9. You can multiply that coefficient by 3! = (3)(2)(1) to get the number of permutations.

If you wanted to see the combinations such as ACE listed explicity, you use
$$(Ayx^1 + Byx^2 + Cyx^3 + Dyx^4 + Eyx^5)^3$$

 

[bpet]

...For example, when the expression:
$$(yx^1 + yx^2 + yx^3 + yx^4 + yx^5)^3$$
is simplified, the coefficient of $y^3 x^9$ would be the number of possible combinations of three distince integers from the set {1,2,3,4,5} whose sum is exactly 9. You can multiply that coefficient by 3! = (3)(2)(1) to get the number of permutations.
...

That generating function allows repeats, it should be
$$(1+yx^1)(1+yx^2)...(1+yx^5)$$

 

[Stephen Tashi]

That generating function allows repeats, it should be
$$(1+yx^1)(1+yx^2)...(1+yx^5)$$

You're correct!

 

[blue_raver22]

I understand your problem and can provide some insight on how to approach it. Firstly, you are correct in identifying that this is a permutation problem since order matters. To find the number of combinations (of size N) that meet the given criteria, we need to consider all possible permutations of N coins and calculate their total values. Then, we can count the number of permutations that have a total value equal to or greater than J.

One approach is to use a recursive algorithm to generate all possible permutations of N coins and calculate their total values. This can be a time-consuming process, especially for larger values of N. Another approach is to use a mathematical formula to calculate the number of permutations.

In your example, for a pair of coins, the formula would be (N-1) + (N-2) + ... + 1, where N is the number of coins. For N=2, this would give us 1+2 = 3, which matches the two permutations you identified (DE and ED). For larger values of N, this formula can be generalized as N(N-1)/2, which can be used to calculate the number of permutations for any given value of N.

To incorporate the condition of the total value being equal to or greater than J, we can use a similar formula but with some modifications. For example, for N=3 and J=9, the formula would be (N-1) + (N-2) + ... + (N-(J-1)), which in this case would give us 1+2+3 = 6 permutations.

I hope this helps you in solving your problem. Remember to always check your solution and consider any potential exceptions or special cases. Good luck!