Calculating number of possible combinations with limited repitition

tsasser

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.

viraltux

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 k_i is the number of marbles or color i, then [itex]c_i=min(d,k_i)[/itex]

tsasser

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!!!

viraltux

You're just right, that was the idea.

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

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

tsasser

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. :).

viraltux

Glad to hear! Good luck!

tsasser

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 dont 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?

Attached Files

Marble Combination Example.xls (38.0 KB, 3 views)

viraltux

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.

tsasser

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!

Mandlebra

Has any one 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

viraltux

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!

tsasser

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".

Mandlebra

Read this : p
http://en.wikipedia.org/wiki/Job_shop_scheduling

tsasser

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

haruspex

Not this time, I'd say. Maybe start with the simplest non-trivial case, k_i = 2 for all i.

tsasser

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

Attached Files

Marble Combination Example.xls (71.5 KB, 5 views)

viraltux

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