434,828 Members | 2,241 Online + Ask a Question
Need help? Post your question and get tips & solutions from a community of 434,828 IT Pros & Developers. It's quick & easy.

Seeking algorithm to compute number of possibilities...

 P: n/a If 3 things can be in one of 2 states, the number of possible combinations is equal to 2^3. But if I have 3 things, 2 of which can be in 2 states and the other in 3 states, what's the simplest expression that will accurately compute the permutationjs possible? Dec 14 '06 #1
22 Replies

 P: n/a That's a bad example because it uses the same number twice, so this might not make sense but the best formula to compute that would be 2X + 3Y, where X = 2 and Y = 1. X + Y = the number of things you're talking about. MLH wrote: If 3 things can be in one of 2 states, the number of possible combinations is equal to 2^3. But if I have 3 things, 2 of which can be in 2 states and the other in 3 states, what's the simplest expression that will accurately compute the permutationjs possible? Dec 14 '06 #2

 P: n/a ManningFan : MLH wrote: :If 3 things can be in one of 2 states, :the number of possible combinations :is equal to 2^3. :> :But if I have 3 things, 2 of which can :be in 2 states and the other in 3 states, :what's the simplest expression that will :accurately compute the permutationjs :possible? Dec 14 '06 #3

 P: n/a MLH wrote: If 3 things can be in one of 2 states, the number of possible combinations is equal to 2^3. But if I have 3 things, 2 of which can be in 2 states and the other in 3 states, what's the simplest expression that will accurately compute the permutationjs possible? (2^2)*3 -- Rick Brandt, Microsoft Access MVP Email (as appropriate) to... RBrandt at Hunter dot com Dec 14 '06 #4

 P: n/a Excuse me. I made a computational error. The number I meant to post was 6,377,292 == not 177,183. Dec 16 '06 #6

 P: n/a "MLH"

 P: n/a On Sat, 16 Dec 2006 16:14:08 GMT, "Rick Brandt" Don't over think this. Possible combinations are derived by multiplying thepossible states of each entity by the possible states of the others. Raising toa power is merely shorthand for the multiplying and is only possible any timethe number of possible states between entities is the same. Gotcha. So, applying the above to the question regarding the marbles, frogs, people and outlaws, whats the number of combinations you come up with? Dec 16 '06 #8

 P: n/a MLH Don't over think this. Possible combinations are derived by multiplying the :>possible states of each entity by the possible states of the others. Raising to :>a power is merely shorthand for the multiplying and is only possible any time :>the number of possible states between entities is the same. : Gotcha. So, applying the above to the question regarding the marbles, : frogs, people and outlaws, whats the number of combinations you come : up with? Using basic I got that 3^8 * 2^2 * 3^3 * 2^4 = 11337408 marbles frogs people outlaws I think that your algorithm with its shortcut is fine. In aircode [even worse than aircode I'm afraid] form: if N=number of EntityTypes()= array of number of Entities of each Type, EntityStates()= array of number of States for each EntityType Combinations = 1 for Type = 1 to N Combinations = Combinations * EntityStates(Type)^EntityTypes(Type) --thelma Dec 16 '06 #9

 P: n/a So we got two different answers. That's what I was afraid of. I haven't a clue who's right. I'm not sure what algorithm Rick was using. Thx for the input. Dec 16 '06 #10

 P: n/a MLH

 P: n/a "MLH"

 P: n/a "Rick Brandt" So we got two different answers. That's what I was afraid of.I haven't a clue who's right. I'm not sure what algorithm Rick wasusing. Thx for the input. 8 marbles that can be red, blue or green, 2 frogs that can be jumping or not, 3 people that can be eating, sleeping or scuba diving and 4-outlaws that can be dead or alive. Not (3^8)*(2^2)*(3^3)*(4^2) 6561*4*27*16 = 11,337,408 I seem to agree with Thelma. How did you get your answer? It's not really a great example and maybe that's why we don't get the same answer as you do. A rolled die can come up with one of 6 different sides on top. A solid colored marble is ALWAYS one color. It has no possibility of being three possible colors as in your example. Did you mean that of the 8 marbles some of them will be this, that, or the other color? That would represent a completely different problem. It would be more realistic and less confusing to just consider these as 8 table fields each if which can have one of three possible entries, 6 fields that each have two possible entries, and 3 fields that each have 3 possible entries. (3^8) * (2^6) * (3^3) 6561 * 64 * 37 = 15536448 Fat-fingered that one. Last line should be 6561 * 64 * 27 = 11,337,408 -- Rick Brandt, Microsoft Access MVP Email (as appropriate) to... RBrandt at Hunter dot com Dec 17 '06 #13

 P: n/a Rick Brandt

 P: n/a "Thelma Roslyn Lubkin"

 P: n/a MLH wrote: If 3 things can be in one of 2 states, the number of possible combinations is equal to 2^3. But if I have 3 things, 2 of which can be in 2 states and the other in 3 states, what's the simplest expression that will accurately compute the permutationjs possible? 4 calling birds that can be eating, soaring or doing nothing 3 french hens French or not 2 turtle doves that are posting to CDMA or not (1 + e + s) ^ 4 * (1 + f) ^ 3 * (1 + p) ^ 2 Total possibilities = 3^4 * 2^3 * 2^2 How can I list all the possibilities? By multiplying out the polynomial. If the birds can be individually distinguished: (1 + e1 + s1) (1 + e2 + s2) (1 + e3 + s3) (1 + e4 + s4) (1 + f1) (1 + f2) (1 + f3) (1 + p1) (1 + p2) Is it possible to determine the coefficient of a specific term without multiplying out the polynomial? Yes E.g., Suppose we only have the two indistinguishable turtle doves. (1 + p) ^ 2 Realize that, in general, the polynomial might have been something like (1 + p + p^2 + p^3) ^ 43 so the following is used: It's necessary to put the polynomial into a more useful form. In general, 1 + r + r^2 + ... + r^n = 1 - r^(n+1) / (1 - r). (1 + p) ^ 2 = [(1 - p^2) / (1 - p)] ^ 2 Note that 1 / (1 - x) = 1 + x + x^2 + ... By differentiating the terms of 1 / (1 - x) and using a dummy variable, along with some clean-up, 1 / (1 - x) ^ (r + 1) = Summation from k = 0 to infinity of C(k + r, r) x ^ k where C(m, n) = m! / n!(m - n)! This is from page 505 of Discrete Mathematics by Jerrold Grossman, ISBN 0-02-348331-8, 1990 Macmillan, Inc. Note that multiplying by x ^ c just shifts the exponent of x by m. I.e., x ^ c / (1 - x) ^ (r + 1) = Summation from k = 0 to infinity of C(k + r, r) x ^ (k + c) So now a way exists to determine the overall contribution a given variable makes to a specific term. What is the coefficient of p^1? (1 - p ^ 2) ^ 2 / (1 - p) ^ 2 contributes 2 to the coefficient of p I.e., C(1 + 1,1) = 2!/ 1!1! = 2, -2 * C(-1 + 1, 1) = 0 and C(-3 + 1, 1) = 0. Use 0 whenever you get a negative number factorial since that indicates that the exponents of the p polynomial are already too large to contribute to p. Thus the first turtle dove can be posting to CDMA with the second turtle dove not posting (perhaps they share the same computer) or the first turtle dove is not posting to CDMA with the second turtle dove posting to CDMA. Of course, since you can't tell the turtle doves apart anyway you can only note that a single turtle dove is posting to CDMA. If you want to cross states and ask how many combinations have a total of 4 calling birds, french hens and turtle doves flying, that's a different kettle of fish, but it's not hard to see how to get those polynomials either. This should give you the information you need to build your algorithm. Note that this answer might contain more detailed than your original request implied. James A. Fortune CD********@FortuneJames.com Disclaimer: With few exceptions, I don't claim to know much about anything unless I've written a computer program to do it. Dec 17 '06 #16

 P: n/a There is a difference between frogs and marbles. If the first marble we pick up is red then it is a different marble than we picked up when the the first marble was blue. If the first frog we pick up was jumping it can be the same frog that we picked up when it was sleeping. two marbles two colors results in the possibilities: RR RB BB 2 frogs jumping or sleeping: F1J & F2J F1J & F2S F1S & F2S F1S & F2J "Rick Brandt" "Thelma Roslyn Lubkin" Rick Brandt

 P: n/a On Sun, 17 Dec 2006 00:37:56 GMT, "Rick Brandt" I seem to agree with Thelma. How did you get your answer? Believe me, I'm not confident uf my answer - not even my arithmetic. Only with small numbers I can do on a sheet of paper do I feel some sort of confidence. Here's where I was coming from... 3-States 2-States ------------- --------------- 8 marbles 2 frogs 3 people 4 outloaws 11 things 6 things (3^11) x (2^6) = 11,337,408 Last time I used (3^11) x (6^2) mistakenly =which = 6,377,292 I didn't differentiate between people & marbles. My thinking was both were just things that could be in 1 of 2 states. Same went for frogs & outlaws. I could have worded my question ==How many combinations are possible with 11 things (2-states) and 6 things (3-states). I'm probably way off on this. Dec 17 '06 #18

 P: n/a David, although I agree with your logic, I'm having difficulty getting your point with the 2 frogs jumping or sleeping illustration. I belive yields 4 (2^2). That's what you have shown. If that's the point, I think we are all in agreement with it. Rick pointed out a few posts up that the exponential expression was a shorthand notation used for calculating possible combinations in a things - states scenario. On Sun, 17 Dec 2006 04:29:08 GMT, "David F Cox" wrote: >There is a difference between frogs and marbles.If the first marble we pick up is red then it is a different marble than wepicked up when the the first marble was blue.If the first frog we pick up was jumping it can be the same frog that wepicked up when it was sleeping.two marbles two colors results in the possibilities:RR RB BB2 frogs jumping or sleeping:F1J & F2JF1J & F2SF1S & F2SF1S & F2J"Rick Brandt" >"Thelma Roslyn Lubkin" >Rick Brandt

 P: n/a Hey, I think you're on to something there, Thelma. Aircode -haircode - looks good to me (now that I realized my arithmetic was slightly bent). Many thx, Thelma. xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx > if N=number of EntityTypes()= array of number of Entities of each Type, EntityStates()= array of number of States for each EntityType Combinations = 1 for Type = 1 to N Combinations = Combinations * EntityStates(Type)^EntityTypes(Type) --thelma Dec 17 '06 #20

 P: n/a Hmmm... you get 2592. I get 2025. More inconsistency. Anyone else have a take on this? xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx On 16 Dec 2006 19:55:33 -0800, CD********@FortuneJames.com wrote: >MLH wrote: >If 3 things can be in one of 2 states,the number of possible combinationsis equal to 2^3.But if I have 3 things, 2 of which canbe in 2 states and the other in 3 states,what's the simplest expression that willaccurately compute the permutationjspossible? 4 calling birds that can be eating, soaring or doing nothing3 french hens French or not2 turtle doves that are posting to CDMA or not(1 + e + s) ^ 4 * (1 + f) ^ 3 * (1 + p) ^ 2Total possibilities = 3^4 * 2^3 * 2^2How can I list all the possibilities? By multiplying out thepolynomial.If the birds can be individually distinguished:(1 + e1 + s1) (1 + e2 + s2) (1 + e3 + s3) (1 + e4 + s4) (1 + f1) (1 +f2) (1 + f3) (1 + p1) (1 + p2)Is it possible to determine the coefficient of a specific term withoutmultiplying out the polynomial? YesE.g.,Suppose we only have the two indistinguishable turtle doves.(1 + p) ^ 2Realize that, in general, the polynomial might have been something like(1 + p + p^2 + p^3) ^ 43 so the following is used:It's necessary to put the polynomial into a more useful form. Ingeneral, 1 + r + r^2 + ... + r^n = 1 - r^(n+1) / (1 - r).(1 + p) ^ 2 = [(1 - p^2) / (1 - p)] ^ 2Note that 1 / (1 - x) = 1 + x + x^2 + ...By differentiating the terms of 1 / (1 - x) and using a dummy variable,along with some clean-up,1 / (1 - x) ^ (r + 1) = Summation from k = 0 to infinity of C(k + r, r)x ^ k where C(m, n) = m! / n!(m - n)!This is from page 505 of Discrete Mathematics by Jerrold Grossman, ISBN0-02-348331-8, 1990 Macmillan, Inc.Note that multiplying by x ^ c just shifts the exponent of x by m.I.e.,x ^ c / (1 - x) ^ (r + 1) = Summation from k = 0 to infinity of C(k +r, r) x ^ (k + c)So now a way exists to determine the overall contribution a givenvariable makes to a specific term.What is the coefficient of p^1?(1 - p ^ 2) ^ 2 / (1 - p) ^ 2 contributes 2 to the coefficient of pI.e., C(1 + 1,1) = 2!/ 1!1! = 2, -2 * C(-1 + 1, 1) = 0 and C(-3 + 1,1) = 0. Use 0 whenever you get a negative number factorial since thatindicates that the exponents of the p polynomial are already too largeto contribute to p.Thus the first turtle dove can be posting to CDMA with the secondturtle dove not posting (perhaps they share the same computer) or thefirst turtle dove is not posting to CDMA with the second turtle doveposting to CDMA. Of course, since you can't tell the turtle dovesapart anyway you can only note that a single turtle dove is posting toCDMA. If you want to cross states and ask how many combinations have atotal of 4 calling birds, french hens and turtle doves flying, that's adifferent kettle of fish, but it's not hard to see how to get thosepolynomials either.This should give you the information you need to build your algorithm.Note that this answer might contain more detailed than your originalrequest implied.James A. FortuneCD********@FortuneJames.comDisclaimer: With few exceptions, I don't claim to know much aboutanything unless I've written a computer program to do it. Dec 17 '06 #21

 P: n/a Oops - no, I get 2592. But I just grouped them into (3^4) x (2^5). First time around, I did (3^4) x (5^2) which was goofy. Dec 17 '06 #22

 P: n/a The point I was trying to make is that there seemed to me to be some confusion in the examples given between cases where order matters (combinations) and does not matter (permutations). Different formulae apply. In this field the slightest imprecision in thought can result in the answer being billions out. http://en.wikipedia.org/wiki/Combinatorics http://www.algebra.com/algebra/homew...rics.wikipedia http://www.stat.berkeley.edu/users/s...i/Text/ch7.htm "MLH" wrote: >>There is a difference between frogs and marbles.If the first marble we pick up is red then it is a different marble thanwepicked up when the the first marble was blue.If the first frog we pick up was jumping it can be the same frog that wepicked up when it was sleeping.two marbles two colors results in the possibilities:RR RB BB2 frogs jumping or sleeping:F1J & F2JF1J & F2SF1S & F2SF1S & F2J"Rick Brandt" >>"Thelma Roslyn Lubkin"

This discussion thread is closed

Replies have been disabled for this discussion. 