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!