How Many Permutations of Coins Meet a Specific Value Threshold?

  • Context: Undergrad 
  • Thread starter Thread starter adoado
  • Start date Start date
  • Tags Tags
    Permutation
Click For Summary

Discussion Overview

The discussion revolves around calculating the number of permutations of a set of coins with specific integer values that meet or exceed a given sum threshold. Participants explore both combinatorial and algorithmic approaches to the problem, considering the implications of order and repetition in their calculations.

Discussion Character

  • Exploratory
  • Mathematical reasoning

Main Points Raised

  • Adrian presents a problem involving five coins with assigned values and seeks to determine how many permutations of a chosen size meet a specific sum threshold.
  • One participant questions whether the solution should focus on permutations or combinations, suggesting that a computer algorithm could provide a numerical answer.
  • Another participant proposes using generating functions to derive a symbolic expression for the problem, mentioning a specific expression that could yield the number of combinations for a given sum.
  • It is noted that the generating function initially suggested allows for repeats, prompting a correction to use a different generating function that accounts for distinct selections.

Areas of Agreement / Disagreement

Participants do not reach a consensus on the best approach to solve the problem, with differing opinions on whether to use permutations or combinations and how to apply generating functions effectively.

Contextual Notes

There are unresolved aspects regarding the assumptions about the selection of coins, the handling of repetitions, and the specific requirements for the sum threshold.

adoado
Messages
71
Reaction score
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
 
Physics news on Phys.org
adoado said:
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
 
Stephen Tashi said:
...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)
 
bpet said:
That generating function allows repeats, it should be
(1+yx^1)(1+yx^2)...(1+yx^5)

You're correct!
 

Similar threads

High School Combinatorics and Magic squares
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad How Many Permutations Exist Where M Equals K on Cards?
  • · Replies 31 ·
2
Replies
31
Views
3K
Undergrad How to find the nth binary permutation?
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad How many tosses to flip a coin HHTH?
  • · Replies 41 ·
2
Replies
41
Views
9K
MHB How Do You Categorize Permutations of a 20-Object Set into Distinct Patterns?
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad On the expected value of a sum of a random number of r.v.s.
  • · Replies 3 ·
Replies
3
Views
3K
Undergrad How Many Ways to Arrange Five Colored Balls with Specific Conditions?
  • · Replies 2 ·
Replies
2
Views
2K
Graduate How many permutations leave an element unchanged?
  • · Replies 6 ·
Replies
6
Views
3K
Permutations with possibly repeating letters
  • · Replies 4 ·
Replies
4
Views
3K
Program to list specific permutations of 5 digits
  • · Replies 4 ·
Replies
4
Views
3K