Calculating number of possible combinations with limited repitition

In summary, the conversation discussed a problem involving drawing marbles from a bag. The problem was described using an example of a bag containing 3 red, 2 blue, and 1 green marble and pulling out 3 marbles at once. The conversation then shifted to finding the mathematical method for solving this type of problem, with the goal of creating an Excel spreadsheet to calculate solutions based on varying inputs. A formula was drafted and discussed, but further exploration and refinement were needed. The conversation ended with the hope that the formula would be finalized and implemented successfully.
  • #1
tsasser
8
0
Hello everyone,

I'm new to the forum and have an engineering problem I've been trying to solve for my job. The actual problem is rather hard to describe but it can best be explained with the following analogous scenario.

Suppose I had a bag containing 3 red, 2 blue, and 1 green marbles. If I were to pull out 3 marbles only once from the bag; what are all the possible color combinations I could pull out?

The answer is 6. RRR,RRB,RRG,RBB,RBG,BBG. In a simple combinations with repetitions problem the answer would be 10. RRR,RRB,RRG,RBB,RBG,RGG,BBB,BBG,BGG,GGG
[(n+r-1)!]/[r!(n-1)!] However, because we have a defined population, the repetition is constrained by that population.

I need to know the mathematical method for how to solve a problem of this type. In the real problem I'm trying to solve, the variables (ie. number drawn, number of colors, qty in bag) would be changing constantly so I'd like to set-up an excel spreadsheet "calculator" that would solve any problem of this type based off the inputs given.

Any help that can be given would be greatly appreciated. Thanks.
 
Physics news on Phys.org
  • #2
tsasser said:
Hello everyone,

Suppose I had a bag containing 3 red, 2 blue, and 1 green marbles. If I were to pull out 3 marbles only once from the bag; what are all the possible color combinations I could pull out?

The answer is 6. RRR,RRB,RRG,RBB,RBG,BBG. In a simple combinations with repetitions problem the answer would be 10. RRR,RRB,RRG,RBB,RBG,RGG,BBB,BBG,BGG,GGG
[(n+r-1)!]/[r!(n-1)!] However, because we have a defined population, the repetition is constrained by that population.

Hi tsasser,

OK, I quickly drafted this formula formula and it seems to work for a few examples including yours, you can check it more thoroughly yourself if you want and then we can discuss:

[tex]\frac{(d+1)(d+2)}{2}-\sum_{i=1}^{n}\frac{(d-c_i)(d-c_i+1)}{2}[/tex]

where d is the number of marbles drawn, n is the number of colors and, if ki is the number of marbles or color i, then [itex]c_i=min(d,k_i)[/itex]
 
  • #3
Viraltux,

Thanks for the reply. I sincerely appreciate your help with this. I've plugged your formula into excel and it seems to work well in most cases, but there are some instances where it does not.

I'll admit that I'm no mathematician and I may have made some mistakes translating your formula, but if I’m correct, the 1st half of the equation: [(d+1)(d+2)]/2 solves for the total possible combinations and then the second half of the equation removed all those combinations that cannot exist due to population constraints. Is this right?

It seems like the first half of the equation works well when the number of colors stays at 3, but seems incorrect with any other number of colors. (for reference, the real problem I'm trying to solve could contain up to 20 "colors")

Also, assuming we are working with the exact example I stated initially, the second half of the equation seems to calculate fine when the "number of marbles drawn" is changed anywhere between 1 and 5. However, when the number is changed to 6 drawn at a time, there should be only 1 answer, but the formula calculates -3.

This definitely looks great so far though!
 
  • #4
tsasser said:
Viraltux,

I'll admit that I'm no mathematician and I may have made some mistakes translating your formula, but if I’m correct, the 1st half of the equation: [(d+1)(d+2)]/2 solves for the total possible combinations and then the second half of the equation removed all those combinations that cannot exist due to population constraints. Is this right?

You're just right, that was the idea.

tsasser said:
It seems like the first half of the equation works well when the number of colors stays at 3, but seems incorrect with any other number of colors. (for reference, the real problem I'm trying to solve could contain up to 20 "colors")

You're right, I just checked your example, saw a pattern and dump it on the formula without checking for other cases. Anyway, if you check for other cases you will see lots of arithmetic series that you can eventually work out in a formula just as I did for that particular case. I let for you the fun :tongue:

tsasser said:
Also, assuming we are working with the exact example I stated initially, the second half of the equation seems to calculate fine when the "number of marbles drawn" is changed anywhere between 1 and 5. However, when the number is changed to 6 drawn at a time, there should be only 1 answer, but the formula calculates -3.

This definitely looks great so far though!

Yeah, for the trivial case you can simply ignore the formula and return one. Anyhow, if you have problems finding the final formula and since you are going to implement this in a spreadsheet, one easy (and safe) way to calculate this number would be to simply iterate through the valid solutions (this will be very fast as long as you don't expect gigantic numbers, but that does not seem to be a problem in your case)

You simply need to set the colors c1 + c2 + c3 + ... = number of marbles, and the constrains c1<= k1, c2<=k2,... Then you simply iterate the solutions and count them. Not so elegant as a formula but still pretty fast and you know for sure what you're getting is right :wink:
 
  • #5
Thanks viraltux, you've been a huge help. There's no way I could have solved this one without some expertise. Hopefully I'll be able to fill in the blanks. :).
 
  • #6
tsasser said:
Thanks viraltux, you've been a huge help. There's no way I could have solved this one without some expertise. Hopefully I'll be able to fill in the blanks. :).

Glad to hear! Good luck! :smile:
 
  • #7
I've found out why the second half of the equation doesn't always work...

The attached spreadsheet has an example detailing 4 marbles drawn from a bag with 4 different colors.

The method employed thus far has been to count the combinations that cannot exist due to qty constraints for each color and then add them all together.

The problem with this method is that depending on the quantites of each color and the number drawn, some combinations may get counted more than once.

For example, I have 3 red, 2 blue, 1 green, and 1 orange marbles and I want all the color combinations for 4 marbles. Assuming we account for all the possibities with an unlimited population we would have 35 possibities total. If we count all those possibities that exceed the available qty of red marbles we would have 1. 4 for blue, 10 for green, and 10 for orange. This totals 25 non existent possibities by color. This would mean there would be 10 "real" possibities. However there are really 11 possibities. the combination:Green, Green, Orange, Orange. gets counted twice. once for having too many greens and once for having too many oranges Leaving us with an inaccurate count.

Given this information, I don't see how the current method for calculating possibities would work even with modifications. And since I'm actually dealing 20 different "colors" being drawn 8 at a time, listing all the possibities as I did in the attachement would be very infeasible.

Any suggestions on how to move forward?
 

Attachments

  • Marble Combination Example.xls
    38 KB · Views: 340
  • #8
You can Iterate through the solutions and count them. Iterations are one of the fastest operations a processor can make. So you can do exactly the same thing you do by hand but let the computer do it.
 
  • #9
Sounds like my initial dream of having a neat little formula is going up in smoke. lol

For what I'm actually trying to accomplish I will need to write some VB code to have excel generate a list of all the possible combinations.

However, I was hoping to use this marble example to come up with a quicker way to simply identify the number of combinations rather then list them. The idea was to see if my more lofty goal of making excel generate a list is even feasible based on the total number of combinations it would have to go through. If it's a few thousand I can deal with it. If it's several hundred thousand or millions, I may need to go back to the drawing board.

I guess I better brush up on my programming. Thanks for all the help!
 
  • #10
Has anyone set up a generating function yet? Usually those make easy work of counting problems. I have to take the girl to the dentist but I'll check it out later for you. I wonder what your marbles are : p
 
  • #11
tsasser said:
Sounds like my initial dream of having a neat little formula is going up in smoke. lol

For what I'm actually trying to accomplish I will need to write some VB code to have excel generate a list of all the possible combinations.

However, I was hoping to use this marble example to come up with a quicker way to simply identify the number of combinations rather then list them. The idea was to see if my more lofty goal of making excel generate a list is even feasible based on the total number of combinations it would have to go through. If it's a few thousand I can deal with it. If it's several hundred thousand or millions, I may need to go back to the drawing board.

I guess I better brush up on my programming. Thanks for all the help!

A few millions iterations is nothing for a modern computer, you will be able to calculate that in less than a second and the code is reaaaally simple; just nested iterations with constrains and breaks with a counter. And about the formula, well, maybe is simpler than we think, wait for a while and maybe someone comes up with an answer! Good luck tasser! :smile:
 
  • #12
Mandelbra thanks for taking an interest.

Since you're curious, I work for a company that manufactures bonded composite panels. These panels get bonded in a multi-opening press. We have several different part numbers of panels we bond. Different panels may be combined and ran in the same openings and the combined area of these different panel combinations effects all the cycle parameters of the press.

I'm attempting to create a spreadsheet in which you input a production schedule and the spreadsheet claculates the most optimal way to combine the panels on the schedule with the others to maximize efficiency and other criteria while satisfying several other constraints.

I've identified a theoretical method for achieving my goal and one of the steps in the process involves listing all the possible ways a group of different panels on a schedule may be combined to fit in the press openings.

So the composite panels are the "marbles" and each different type of panel represents a different "color".
 
  • #13
tsasser said:
Mandelbra thanks for taking an interest.

Since you're curious, I work for a company that manufactures bonded composite panels. These panels get bonded in a multi-opening press. We have several different part numbers of panels we bond. Different panels may be combined and ran in the same openings and the combined area of these different panel combinations effects all the cycle parameters of the press.

I'm attempting to create a spreadsheet in which you input a production schedule and the spreadsheet claculates the most optimal way to combine the panels on the schedule with the others to maximize efficiency and other criteria while satisfying several other constraints.

I've identified a theoretical method for achieving my goal and one of the steps in the process involves listing all the possible ways a group of different panels on a schedule may be combined to fit in the press openings.

So the composite panels are the "marbles" and each different type of panel represents a different "color".
Read this : p
http://en.wikipedia.org/wiki/Job_shop_scheduling
 
  • #14
Mandlebra that article looks very interesting. I think there may be some similarities here. I just wish I knew more about math and computer programming. Aside from having a good understanding of logic, the only thing I know how to program is a CNC machine.

I believe I should probably just move on to trying to get Excel to generate a list of all the possible combinations. Maybe I'll hit up an Excel forum on how to write the VB code. lol
 
  • #15
Mandlebra said:
Has anyone set up a generating function yet? Usually those make easy work of counting problems.

Not this time, I'd say. Maybe start with the simplest non-trivial case, ki = 2 for all i.
 
  • #16
In case anyone is interested,

I wasn't able to figure out a formula, but I did manage to write the code to have all the possible combinations listed out.

Check out the attached spreadsheet. The marbles in the bag are listed out and you hit ctrl+shift+A. This generates a list of all possible combinations from 1 drawn up to 8 drawn.

Thanks Viraltux I couldn't have done it without the motivation. lol
 

Attachments

  • Marble Combination Example.xls
    71.5 KB · Views: 333
  • #17
tsasser said:
Thanks Viraltux I couldn't have done it without the motivation. lol

Ha! You're welcome! :smile: Maybe I should expand my job search into motivational speaker too :tongue:
 

1. How do you calculate the number of possible combinations with limited repetition?

The number of possible combinations with limited repetition can be calculated using the formula n^r, where n is the number of objects to choose from and r is the number of objects in each combination.

2. What is limited repetition?

Limited repetition refers to the restriction of using an object only a certain number of times in a combination. For example, if we have the numbers 1, 2, and 3 and are allowed to choose 2 numbers with limited repetition, we can have combinations like (1,1), (1,2), (1,3), (2,2), (2,3), and (3,3).

3. Can you give an example of calculating the number of possible combinations with limited repetition?

Sure, let's say we have 4 letters A, B, C, D and we need to choose 3 of them with limited repetition. The number of possible combinations would be 4^3 = 64.

4. How is this different from calculating permutations?

Calculating permutations takes into account the order of the objects in a combination, while calculating combinations with limited repetition does not. In our previous example, the combinations (A, B, C) and (C, B, A) would be considered the same in calculating the number of combinations with limited repetition, but would be considered different in calculating permutations.

5. Why is it important to calculate the number of possible combinations with limited repetition?

Calculating the number of possible combinations with limited repetition is important in many areas of science and mathematics, such as probability, genetics, and data analysis. It allows us to understand and predict the likelihood of certain outcomes and make informed decisions based on that information.

Similar threads

Replies
1
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
4K
  • Precalculus Mathematics Homework Help
Replies
5
Views
5K
  • Calculus and Beyond Homework Help
Replies
17
Views
2K
Replies
4
Views
3K
Replies
4
Views
1K
  • Precalculus Mathematics Homework Help
Replies
7
Views
3K
  • Precalculus Mathematics Homework Help
Replies
9
Views
2K
  • Sci-Fi Writing and World Building
Replies
9
Views
2K
Replies
17
Views
290K
Back
Top