Permutation and total values

  • Thread starter adoado
  • Start date
  • #1
72
0
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
 

Answers and Replies

  • #2
Stephen Tashi
Science Advisor
7,544
1,456
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:
[tex] (yx^1 + yx^2 + yx^3 + yx^4 + yx^5)^3 [/tex]
is simplified, the coefficient of [itex] y^3 x^9 [/itex] 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
[tex] (Ayx^1 + Byx^2 + Cyx^3 + Dyx^4 + Eyx^5)^3 [/tex]
 
  • #3
525
5
...For example, when the expression:
[tex] (yx^1 + yx^2 + yx^3 + yx^4 + yx^5)^3 [/tex]
is simplified, the coefficient of [itex] y^3 x^9 [/itex] 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
[tex](1+yx^1)(1+yx^2)...(1+yx^5)[/tex]
 
  • #4
Stephen Tashi
Science Advisor
7,544
1,456
That generating function allows repeats, it should be
[tex](1+yx^1)(1+yx^2)...(1+yx^5)[/tex]
You're correct!
 

Related Threads on Permutation and total values

  • Last Post
Replies
1
Views
3K
  • Last Post
2
Replies
28
Views
2K
  • Last Post
Replies
14
Views
8K
  • Last Post
Replies
6
Views
21K
  • Last Post
Replies
3
Views
2K
Replies
3
Views
6K
Replies
4
Views
904
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
1
Views
6K
  • Last Post
Replies
8
Views
2K
Top