Register to reply 
Combinations  order doesn't matter, repetitions allowed 
Share this thread: 
#1
Nov1411, 05:33 PM

P: 66

I'm trying to figure out the formula I need...
ok, say that r=5, so there are 5 items {A,B,C,D,E} And we want to chose 5 of those Order doesn't matter, repitions allowed so for example {A,A,A,B,B} is a feasible solution {A,B,C,D,E} is feasible so on But the formula (n+r1)!/r!(n1)! doesn't work because here n=r so it becomes (2n1)!/(2n1)! = 1. Also, what happens when I want to put certain restrictions. Like for example, say I want an example of the above format with the exception that A and B can only be chosen if C is chosen. I know I would just find all those infeasible solutions and subtract them but I have a hard time finding those infeasibles. I mean, that situation seems obviosu but what if it has to do with ranking. Like say, A chosen > B,C,D,E, are chosen. B chosen > C,D,E chosen. D chosen > E chosen. So what if there are n such rules. Do I make a case for each individually? I suck at these stupid things 


#2
Nov1411, 06:54 PM

Homework
Sci Advisor
HW Helper
Thanks
P: 12,775

You want John Allen Paulos: Innumeracy ... no really: he has a good guide to handling these things using a simple multiplication rule.
It'll be in a library near you. You have 5 slots, which can each have one of 5 possible entries. Thats 5x5x5x5x5 possible combinations. For the restrictions, you do pretty much have to work out the possible combinations with the forbidden configuration and subtract them off. Just go systematically. It takes practise. 


#3
Nov1411, 07:02 PM

P: 66

Sorry about that... complete brain fail on my part!! sorry but i'm confused about how it would be 5X5X5X5X5 I'm talking about a situation where the order is irrelevant and permutations can occur thanks for the reply btw 


#4
Nov1411, 07:31 PM

Sci Advisor
P: 3,285

Combinations  order doesn't matter, repetitions allowed
I think an example of what you are asking is this: If we multiply out the expression [itex] (A + B + C + D + E)^5 [/itex] and combine like terms, how many distinct types of terms will there be? For example [itex] AB^2C^2 [/itex] and [itex] C^2A B^2 [/itex] are like terms. [itex] AB^2C^2 [/itex] and [itex] A^2B^2C [/itex] are unlike terms. So you are asking about the number of different types of terms, not about the numerical coefficients of the various types of terms. 


#5
Nov1411, 07:44 PM

P: 66

I apologize, I completely misspoke. I meant to say "repetitions can occur" I mix up similar sounding words like that all the time and don't realize it.
THe only reason I was confused about the 5X5X5X5X5 thing was because that formula (n+r1)!/r!(n1)! I thought was specifically used for that situation (given n items, you want to chose r so that repetitions can occur and order is irrelevant) 


#6
Nov1411, 07:58 PM

Homework
Sci Advisor
HW Helper
Thanks
P: 12,775

Imagine it was only 2 slots.
You can do that right? Order doesn't matter, and repititions are allowed, so {AB, AA, BA} is three combinations. You get a total of 5x5=25 possible combinations. If you could not get doubles, then it would be 5x4=20 combinations  since whichever of the 5 get the first slot will leave only 4 for the second. Now extrapolate to 5 slots. 


#7
Nov1411, 08:47 PM

P: 66

i see what you are saying, but it seems like by that logic order should matter.
The example you were giving with 2 slots, it seemed like the goal is: there are 5 objects {A,B,C,D,E} and 2 slots. So you were saying there are 5X5 possibilities. But then that would include for example both AB and BA, but I'm talking about order being irrelevant so only one could be included 


#8
Nov1411, 09:17 PM

Mentor
P: 18,240

This is one of more difficult combinatorial problems... Here is how you solve it:
Let's first introduce a notation. I write  all the A's  all the B's  all the C's  all the D's  all the E's  So for example, (A,A,A,B,C) is written as AAABC and (A,C,D,E,E) is ACDEE But we can simplify this notation!! Indeed, under this notation, we don't have to write the A, B, etc. anymore. So I know that ...... represents (A,D,D,D,D). So right now we have 11 spots: ........... and we want choose 6 spots where to put . Under the constraints that the first and the last symbol are . So (disregarding the firsst and last symbol): we have 9 spots, and we want to choose 4 spots where to put  Every choice of spots will induce uniquely one of the permutations you want. So we see that [itex]\binom{9}{4}[/itex] is the required probability. 


#9
Nov1511, 08:04 AM

P: 66

thank you all for the responses. It cleared up the issue!



#10
Nov1511, 08:26 AM

Emeritus
Sci Advisor
PF Gold
P: 5,196

Am I the only one who thinks the OP had the right equation for combination with repetition in the first place, and was just using it wrong?
If I start with (n+r1)! / (r!(n1)!) And I plug in n=r=5, I get (101)! / (5! (51)!) = 9! / (5!4!) Which is just "9 choose 4", the exact same thing as micromass derived. Micromass just showed how to derive the combinatorial equation that the OP had in the first place! People who were telling him/her that it would be 5^5 were way off. That would be for permuation with repetition rather than combination with repetition. I.e. 5^5 would be true if order mattered, but it doesn't. EDIT : I reread the thread and see that nobody was telling him that the *answer* should be 5^5, it just came up as part of the explanation. I also see that Simon Bridge pointed out the same misuse of the equation as I did. OK. EDIT 2: or at least *somebody* pointed it out. It's not clear who, because it's quoted but it doesnt seem to appear in any posts. Unless I am just going crazy. 


#11
Nov1611, 03:25 AM

Homework
Sci Advisor
HW Helper
Thanks
P: 12,775

So you want AB and BA to count as one. By the example I presented: (5x55)/2 +5 ; removing the bottom half of the square but keeping the diagonal. But you have a more elegant description from the very small one. 


#12
Nov1611, 03:29 AM

Homework
Sci Advisor
HW Helper
Thanks
P: 12,775

I'm glad someone pointed it out in the end too :) 


#13
Nov1611, 09:37 AM

P: 685

I like your derivation micromass!
Here are all 126 = [itex]9 \choose 4[/itex] combinations. Note: I've used the notation by micromass. Examples:



Register to reply 
Related Discussions  
Trying to understand what happens when EMR goes through matter (or doesn't)  General Physics  6  
Why doesn't matter overlap?  Quantum Physics  7  
Permutations with repetitions...  Set Theory, Logic, Probability, Statistics  1  
By changing the order would it change the answer? rcombinations  Calculus & Beyond Homework  2  
Dark matter doesn't (or what's the matter with dark matter? or pick your lame pun)  General Physics  4 